Should you simplify?

( 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 ) (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 x^5 in the above expression.


The answer is 71.

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.

2 solutions

Alan Yan
Dec 3, 2015

This is simply ( 1 x 2 ) ( 1 x 3 ) ( 1 x 4 ) ( 1 x 5 ) ( 1 x 6 ) k = 0 ( k + 4 4 ) x k (1-x^2)(1-x^3)(1-x^4)(1-x^5)(1-x^6)\sum_{k = 0}^{\infty}{{k+4 \choose 4}x^{k}} so the x 5 x^5 coefficient is ( 9 4 ) ( 7 4 ) ( 6 4 ) ( 5 4 ) = 71 {9 \choose 4} - {7 \choose 4} - {6 \choose 4} - {5 \choose 4} = \boxed{71} .

Another way: The x 5 x^5 coefficient is exactly the number of ways to choose 5 balls among 1 1 red, 2 2 green, 3 3 yellow, 4 4 black, and 5 5 white balls where balls of the same color are indistinguishable. Let a c o l o r a_{color} 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 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 ( 9 4 ) {9 \choose 4} ways.

If a r 2 a_r \geq 2 , then we have ( 7 4 ) {7 \choose 4} ways.

If a g 3 a_g \geq 3 , then we have ( 6 4 ) {6 \choose 4} ways.

If a y 4 a_y \geq 4 , then we have ( 5 4 ) {5 \choose 4} ways.

If a b 5 a_b \geq 5 , then we have ( 4 4 ) {4 \choose 4} ways.

If a r 2 a_r \geq 2 and a g 3 a_g \geq 3 , we have ( 4 4 ) {4 \choose 4} ways.

The rest are zero. Therefore by PIE, the total valid ways are ( 9 4 ) ( 7 4 ) ( 6 4 ) ( 5 4 ) ( 4 4 ) + ( 4 4 ) {9 \choose 4} - {7 \choose 4} - {6 \choose 4} - {5 \choose 4} - {4 \choose 4} + {4 \choose 4} which is exactly what we got above.

I think this problem belongs to Combinatorics more than Algebra... ?

Jessica Wang - 5 years, 6 months ago

I never thought to apply the generalised binomial theorem. Excellent solution.

Jake Lai - 5 years, 6 months ago

"The x 5 x^{5} coefficient is exactly the number of ways to choose 5 5 balls among 1 1 red, 2 2 green, 3 3 yellow, 4 4 black, and 5 5 white balls where balls of the same color are indistinguishable."

Why? Can somebody explain this for dumb people please?

Patrick Engelmann - 5 years, 6 months ago

Log in to reply

This is the idea of generating functions. Given 1 , 2 , 3 , 4 , 5 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 1+x .

We can choose zero or one or two green marbles. This is 1 + x + x 2 1 + x + x^2 .

We can choose zero or one or two or three yellow marbles. This is 1 + x + x 2 + x 3 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.

Alan Yan - 5 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...