How many 10-letter words are there in which each of the letters e,n,r,s occur at most once?

1.2k Views Asked by At

Solve with a generating function. My solution was $$g(x)=\left(\frac{x^0}{0!} + \frac{x^1}{1!}\right)^4 \left(\frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + ... \right)^{26-4}$$ $$g(x) = (1 + x)^4e^{22x}$$ $$g(x) =\left( \binom{4}{0}x^0 + ... +\binom{4}{r}x^r... + \binom{4}{4}x^4\right)\sum\nolimits 22^r \frac{x^r}{r!}$$

Then we are trying to find the coefficient of the tenth term I denote as $a_{10}$ $$g(x) = h(x)f(x)$$ where $h(x) = (1 +x)^4$ and $f(x) = e^{22x}$ $$g_{10} =h_0f_{10} + h_1f_{9} + h_2f_{8} + h_3f_{7} + h_4f_{6} $$

$$ = \binom{4}{0}22^{10} + \binom{4}{1}22^{9} + \binom{4}{2}22^{8} + \binom{4}{3}22^{7} + \binom{4}{4}22^{6} $$

Now this is not correct and instead is supposes to be: $$ = \binom{4}{0}\frac{10!}{10!}22^{10} + \binom{4}{1}\frac{10!}{9!}22^{9} + \binom{4}{2}\frac{10!}{8!}22^{8} + \binom{4}{3}\frac{10!}{7!}22^{7} + \binom{4}{4}\frac{10!}{6!}22^{6} $$

1) The correct expression seems to include $\binom{4}{r}\frac{10!}{(10-r)!}$ for evaluating the coefficients of $h(x)$ but why is this?

2) If this if correct, why are we using two different values for $n$? We make $n=4$ for evaluating the coefficient of $(1+x)^4$ but then somehow incorporate $n=10$ for $P(n,r)$

2

There are 2 best solutions below

3
On

In your computation you are missing the factor $\frac{1}{i!}$ for $f_i$ coefficients. Fixing this, what you should be looking for is: $P(n=10,r=4)$ (this should answer your second question)that is:

$$\sum_{i=0}^{r}h_i f_{n-i}x^n= \sum_{i=0}^{r} \binom{r}{i} \frac{22^{n-i}}{(n-i)!}x^n$$

substituting for $r=4$ and $n=10$ you will get the expected result you mentioned except for the $10!$ factor, which is the result of the permutation of 10 letters.

So the final answer would be:

$$ = 10!\bigg( \binom{4}{0}\frac{1}{10!}22^{10} + \binom{4}{1}\frac{1}{9!}22^{9} + \binom{4}{2}\frac{1}{8!}22^{8} + \binom{4}{3}\frac{1}{7!}22^{7} + \binom{4}{4}\frac{1}{6!}22^{6})\bigg) $$

0
On

Hint: does $f(x)*h(x)$ give you the coefficient of $\frac{x^{10}}{10!}$?

Consider $f_1h_9$, if you perform the product without much consideration, you get

$$ {4 \choose 1} x^1 * 22^9 * \frac{x^9}{9!} = {4 \choose 1} * 22^9 \frac{x^{10}}{9!} $$

but you want $10!$ in the denominator.

So you need to multiply with $\frac{10}{10}$ to get $${4 \choose 1} * 22^9 * \frac{10}{10} * \frac{x^{10}}{9!} = {4 \choose 1} * 22^9 * 10 * \frac{x^{10}}{10!}$$