I came across a new set of problems while studying combinatorics which involves restrictions to several variables and use of multinomial theoram to evaluate the number of possible combinations of the variables subjected to those restrictions.For example
If we were to pick 6 balls out of a bag which contained 3 red , 4 green and 5 white identical balls then the method i've been taught is as follows :
Suppose
$a$ = red balls , $b$= green balls and $c$=white balls .
Now,
$a +b+c =6$ where $0<=a<=3,0<=b<=4,0<=c<=5.$
Now i am supposed to find the coefficient of $x^6$ in the following product :
$(1+x^1+x^2+x^3)(1+x^1+x^2+x^3+x^4)(1+x^1+x^2+x^3+x^4+x^5)$ and that is the solution.
I want to understand what's actually happening here since finding a coefficient seems to have no link with the possible combinations. THANKS.
Best Answer
Consider for a moment the product
$$\left(x^0+x^1+x^2+x^3\right)\left(y^0+y^1+y^2+y^3+y^4\right)\left(z^0+z^1+z^2+z^3+z^4+z^5\right)\;.$$
When you multiply it out, you get a total of $4\cdot5\cdot6=120$ terms, each of the form $x^ay^bz^c$, where $0\le a\le 3$, $0\le b\le 4$, and $0\le c\le 5$.
Now change the $y$’s and $z$’s back to $x$’s to get the original product; when multiplied out, it’s still a sum of $120$ terms, which are now of the form $x^ax^bx^c=x^{a+b+c}$, where $0\le a\le 3$, $0\le b\le 4$, and $0\le c\le 5$. The lowest power of $x$ in the product is clearly $x^0$, and the highest is $x^{3+4+5}=x^{12}$.
Suppose that $0\le n\le 12$; what’s the coefficient of $x^n$ in this product when we collect like terms? It’s simply the number of products $x^ax^bx^c$ for which $a+b+c=n$. In other words, the coefficient of $x^n$ in this product is the number of solutions to the equation $a+b+c=n$ such that $a,b$, and $c$ are integers satisfying the inequalities $0\le a\le 3$, $0\le b\le 4$, and $0\le c\le 5$. In your ball problem that’s the number of distinguishable combinations of $n$ red, green, and white balls that can be drawn from that particular bag.