( 1 + x ) ( 1 + x + x 2 ) ( 1 + x + x 2 + x 3 ) ( 1 + x + x 2 + x 3 + x 4 ) ( 1 + x + x 2 + x 3 + x 4 + x 5 )
Find the coefficient of x 5 in the above expression.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
I think this problem belongs to Combinatorics more than Algebra... ?
I never thought to apply the generalised binomial theorem. Excellent solution.
"The x 5 coefficient is exactly the number of ways to choose 5 balls among 1 red, 2 green, 3 yellow, 4 black, and 5 white balls where balls of the same color are indistinguishable."
Why? Can somebody explain this for dumb people please?
Log in to reply
This is the idea of generating functions. Given 1 , 2 , 3 , 4 , 5 red, green, yellow, black, and white balls respectively, we can create the expression.
We can choose zero or one red marble. This is 1 + x .
We can choose zero or one or two green marbles. This is 1 + x + x 2 .
We can choose zero or one or two or three yellow marbles. This is 1 + x + x 2 + x 3 .
...
The exponent represents the amount of balls chosen and the coefficient represents the number of ways to do so.
Problem Loading...
Note Loading...
Set Loading...
This is simply ( 1 − x 2 ) ( 1 − x 3 ) ( 1 − x 4 ) ( 1 − x 5 ) ( 1 − x 6 ) k = 0 ∑ ∞ ( 4 k + 4 ) x k so the x 5 coefficient is ( 4 9 ) − ( 4 7 ) − ( 4 6 ) − ( 4 5 ) = 7 1 .
Another way: The x 5 coefficient is exactly the number of ways to choose 5 balls among 1 red, 2 green, 3 yellow, 4 black, and 5 white balls where balls of the same color are indistinguishable. Let a c o l o r denote the number of balls that are chosen for the color. We see that a r + a g + a y + a b + a w = 5 We will use PIE and Stars and Bars.
By stars and bars this is ( 4 9 ) ways.
If a r ≥ 2 , then we have ( 4 7 ) ways.
If a g ≥ 3 , then we have ( 4 6 ) ways.
If a y ≥ 4 , then we have ( 4 5 ) ways.
If a b ≥ 5 , then we have ( 4 4 ) ways.
If a r ≥ 2 and a g ≥ 3 , we have ( 4 4 ) ways.
The rest are zero. Therefore by PIE, the total valid ways are ( 4 9 ) − ( 4 7 ) − ( 4 6 ) − ( 4 5 ) − ( 4 4 ) + ( 4 4 ) which is exactly what we got above.