What is the coefficient of the term $a^i b^j c^k$ in the expansion of $(a+b+c)^n$?

What is the coefficient of the term $a^i b^j c^k$ in the expansion of $(a+b+c)^n$ ?

Given solution:

Before collecting like terms, each term in the expansion is a product of $n$ factors each of which is $a, b,$ or $c$. Those terms which have exactly i a’s, j b’s and k c’s can be combined into the single term $a^i b^j c^k$ and the number of such terms will be equal to the number of n letter strings containing i a’s, j b’s and k c’s, which by the Mississippi rule is $\frac{n!}{(i!\times j! \times k!)}$.

I understand that this problem is actually about the derivation of the coefficient of the multinomial theorem,but I am not sure about the combinatoric reasoning,what I mean is that I understand the analogy problem but what I couldn't is how the analogy holds here,Could anybody explain this to me?

Solution 1:

The combinatorics is not just an analogy; it's what actually goes on. When you expand $(a+b+c)^n$ fully, without using the commutative law for multiplication, what you get is the sum of all $n$-ary products where each factor is one of $a$, $b$, and $c$, and each such product occurs exactly once.

Therefore, when you apply the commutative law and collect like terms, what you're asking is exactly: "how many $n$-letter words from the alphabet $\{a,b,c\}$ contain exactly $i$, $j$, $k$ of each letter. So when you collect like factors in each term, you get exactly $\frac{n!}{i!j!k!}$ instances of the term $a^ib^jc^k$, and that is directly where the coefficient comes from.

Solution 2:

Writing $(a+b+c)^n=(x+c)^n$ for $x=a+b$, one sees this is the coefficient of $a^ib^j$ in $x^{n-k}=(a+b)^{n-k}$, times the coefficient of $c^k$ in $(x+c)^n$.

Hence, if $n\ne i+j+k$ the answer is zero and, if $n=i+j+k$ the answer is $$ {i+j\choose i}{n\choose k}=\frac{n!}{i!j!k!}={n\choose i,j,k}. $$

Solution 3:

You have $i$ $a$'s,$j$ $b$'s and $k$ $c$'s where $i+j+k = n$. An example of a term contributing to $a^i b^j c^k$ is $$\underbrace{abaccaba \ldots bc}_{\mbox{n terms}}$$ containing $i$ $a$'s,$j$ $b$'s and $k$ $c$'s. Each such finite sequence containing $i$ $a$'s,$j$ $b$'s and $k$ $c$'s appears exactly once when you expand $(a+b+c)^n$ and due to commutativity of multiplication all these finite sequences contribute to the term $a^i b^j c^k$. Conversely, by making use of commutativity of multiplication, all terms which yield $a^ib^jc^k$ are just a finite sequence of length $n$ containing $i$ $a$'s,$j$ $b$'s and $k$ $c$'s.

So it boils down to the number of ways you can arrange $i$ identical $a$'s, $j$ identical $b$'s and $k$ identical $c$'s where $i+j+k = n$.

If you have $n$ objects where $r$ are colored red, $b$ are colored blue and $g$ are colored green where $r+b+g = n$, how will you go about finding the number of permutations?

Your first hunch would be $n!$. But you have $r$ indistinguishable red balls. Hence you need to divide by $r!$ to take into account the repetitions. Similarly, you have $b$ indistinguishable blue balls. Hence you need to divide by $b!$ to take into account the repetitions and you have $g$ indistinguishable green balls. Hence you need to divide by $g!$ to take into account the repetitions.

Hence, the total number is $\displaystyle \frac{n!}{r!b!g!}$.

In your case, the number of such finite sequence of $i$ $a$'s,$j$ $b$'s and $k$ $c$'s where $i+j+k = n$ is $$\frac{n!}{i!j!k!}$$