I'm studying for my exams and stuck on this one question.
The way I'm thinking of doing this is by:
$$26^9 – \binom{26}3-\binom{26}2-\binom{26}1-\binom{26}0= 5,429,503,676,728$$
But that seems very, very wrong. Any help would be appreciated. Thanks!
[Math] How many 9 letter strings are there that contain at least 3 vowels
binomial-coefficientscombinatoricsdiscrete mathematics
Related Solutions
Not quite if $x=0$ and $y=3$ then you would have $3^n=y^n$ which is not what you want. If you set $x=0$ and $y=2$ you would have $2^n = y^n$.
Compare this with the general binomial theorem,
$$(x+y)^n = \sum_{k=0}^{n} {n \choose k} x^{n-k}y^k $$
Notice that if $x=1$ and $y=1$ we have,
$$ 2^n = \sum_{k=0}^{n} {n \choose k} $$
Notice that if $x=6$ and $y=-4$ we have,
$$(2)^n = \sum_{k=0}^{n} {n \choose k} 6^{n-k}(-4)^k $$
- What values could $x$ and $y$ have in order to get a $3^n$ on the left?
- What values could $x$ and $y$ have in order to get a $2^k$ in the summation?
If you can find values for $x$ and $y$ which satisfy both those questions then you have solved the problem.
Further Motivation:
You correctly guessed x=1 and y=2.
As far as I know there is no formal algorithmic approach that will solve this type of problem. This is in fact a great tool for teaching problem solving skills because it involves thinking about a problem from different angles without an initially clear path to the solution.
When looking at a problem you should first write it down and examine every piece. We had $$ 3^n = \sum_{k=0}^n { n \choose k } y^k $$
The first thing which strikes me when looking at this is that we have binomial coefficients. This suggests that we may find greater insight by looking at the binomial theorem.
$$ (x+y)^n = \sum_{k=0}^n { n \choose k } x^{n-k} y^k $$
Comparing the statement of the binomial theorem to our problem we notice that both have a summation with binomial coefficients equal to the power of a number. First let us compare the results of the respective summations.
$$ 3^n \qquad (x+y)^n $$
We see that in one case we have the number $3$ raised to the $n$'th power and in the other case we have the number $x+y$ raised to the $n$'th power. We suspect that these numbers will have to be the same for the binomial theorem to be useful in solving the problem. However there are two degrees of freedom in the second number in the form of the variables $x$ and $y$ this means there is not a unique $(x,y)$ pair which will produce a $3$ when added together. Note (-1,4),(0,3),(1,2),(103,-100), etc. all add to three.
This means that we have only partially determined the solution by comparing the results of the summations. To narrow it down to a solution we compare the summands.
$$ {n \choose k } 2^k \qquad { n \choose k } x^{n-k}y^k $$
Both terms have identical binomial coefficients which means that we can ignore them. One has powers of a single number, $2$, the other has powers of our variables $x$ and $y$. We notice that $2$ and $y$ are both raised to the $k$ whereas $x$ is raised to the $n-k$. This suggests to us that it may be useful to associate $y$ with $2$. If we did this we could say that we believe $y=2$ but are not yet confident of the value $x$ should have.
Thinking back we remember that one of the pairs of possible $x$ and $y$ values was $(1,2)$ this is hopeful since it identifies $y=2$ as we desire. If $x=1$ doesn't cause any problems we will have solved the problem.
Examining the binomial theorem with $(1,2)$ we see that,
$$ (x+y)^n = \sum_{k=0}^n { n \choose k } x^{n-k} y^k $$
$$ (1+2)^n = \sum_{k=0}^n { n \choose k } (1)^{n-k} (2)^k $$
$$ 3^n = \sum_{k=0}^n { n \choose k } (2)^k $$
Which is the identity we wanted to establish.
At this point we know the path through the woods. The solution is : Evaluate the binomial theorem for $x=1$ and $y=2$ and the result is the desired identity. This is logically impeccable but contains non of the thought that was necessary to produce it. One advantage of this is that if we are lucky enough to guess the right (x,y) we can solve the problem even if we didn't have a good reason for coming up with the ordered pair. The disadvantage is that we don't learn anything about solving other problems when we see just the bare solution.
You learn to think this way by solving a lot of problems without clearly marked paths to the solution. If you are interested in learning more about how to think in this way you should read "How to Solve It" by George Polya.
We can get around it as follows for the two vowel case:
Represent the word as six blank spots: _ _ _ _ _ _.
Choose two spots for the vowels: ${6 \choose 2}$.
Since order matters, we can fill those two spots in $5^2$ ways.
Since order matters, we can fill the remaining consonants in $21^4$ ways.
For a total of ${6 \choose 2} 5^2 21^4=72930375$ ways.
A similar argument applies to the four vowel case. I get a final total of $77064750$ different words with either exactly two or exactly four vowels.
Best Answer
One way to see that it’s almost certainly wrong is to notice that it doesn’t in any way take into account the fact that there are $5$ vowels. On the other hand, the idea of starting with all $26^9$ strings and throwing out the ones with fewer than $3$ vowels is good. Specifically, you want to throw out the ones that have $0,1$, or $2$ vowels. (You went a step too far.)
There are $5$ vowels and $21$ consonants, so there are $21^9$ strings composed entirely of consonents $-$ i.e., with $0$ vowels.
To make a string with exactly $2$ vowels, you must choose which $2$ of the $9$ positions are to be filled with vowels, then choose vowels for those $2$ positions, and finally choose consonants for the other $7$ positions. You can do that in $\binom92\cdot5^2\cdot21^7$ ways.
How many ways are there to make a string with exactly one vowel?