9
$\begingroup$

Question: Find the number of ways of forming 4 letter words using the letters of the word "RAMANA"

This can be solved easily by taking different cases.

  1. All 3 'A's taken: remaining one letter can be chosen in $^3C_1$ ways. Total possibilities $=^3C_1\cdot\frac{4!}{3!}=12$
  2. Only 2 'A's taken: remaining two letters out of {R,M,N} can be chosen in $^3C_2$ ways. Total possibilities $= ^3C_2\cdot\frac{4!}{2!}=36$
  3. Only one A: Number of ways: $4!=24$

Total $=72$.

But my teacher solved it like this. He found the coefficient of $x^4$ in $4!\cdot(1+\frac{x}{1!})^3(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!})$ which also came out to be $72$.

Why does this work? Also, if I avoid the factorials, I get number of combinations. That is, number of combinations $=$ coefficient of $x^4$ in $(1+x)^3(1+x+x^2+x^3)$

$\endgroup$
  • $\begingroup$ The equation which you have written is of multinomial theorem so you got it right $\endgroup$ – Archis Welankar Dec 24 '15 at 16:30
  • $\begingroup$ Can you suggest a book or website where I can learn multinomial theorem? $\endgroup$ – Aditya Dev Dec 24 '15 at 16:40
  • $\begingroup$ Check it out on wikipedia or wolframalpha $\endgroup$ – Archis Welankar Dec 24 '15 at 16:43
  • $\begingroup$ My question was not to check if its correct, but to know why it works or The logic behind it. $\endgroup$ – Aditya Dev Dec 24 '15 at 16:44
  • 1
    $\begingroup$ Your professor is using exponential generating functions. $\endgroup$ – N. F. Taussig Dec 24 '15 at 18:40
6
$\begingroup$

Suppose you have a $4$ letter string composed of, say, $1$ distinct and $3$ identical letters

There would be $\frac{4!}{1!3!}$ permutations, also expressible as a multinomial coefficient, $\binom{4}{1,3}$

Similarly, for $2$ distinct, $2$ identical, and $3$ distinct, $1$ identical,
it would be $\binom{4}{2,2}\;$ and $\binom{4}{3,1}$ respectively.

In the polynomial expression $4!(1+x/1!)^3(1+x+x^2/2!+x^3/3!)$,
the 4! corresponds to the numerator, whatever the combination; the first term in $( )$ corresponds to choosing one or more from $R,M,N$; and the other term corresponds to choosing $1,2,$ or $3 A's$

It will become evident why this approach works if we expand the first term in ( ), and compare serially with your case approach by just using the appropriate coefficients to get terms in $x^4$

$4!(1 + 3x + 3x^2 + x^3)(1 + x + x^2/2! + x^3/3!)$

To find the coefficient of $x^4$, consider the three cases that produce $x^4$

One from $R,M,N, 3A's : 4!\cdot3\cdot\frac{1}{3!} = 12$
Two from $R,M,N, 2A's : 4!\cdot3\cdot\frac1{2!} = 36$
Three from $R,M,N, 1A : 4!\cdot1\cdot 1 = 24$

Coefficient of $x^4 = 12+36+24 = 72$

We can now clearly see why the coefficient of $x^4$ in the expression automatically gives all possible permutations of $4$ letters

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.