According to Wikipedia, the number of terms in $(x+y+z)^{30}$ is $496$. I'm assuming this is before like terms are added up. How many terms would there be if like terms were combined? How would I go about figuring that out?
Number of terms in a trinomial expansion
-
0Oops sorry that should be 496.. – 2010-11-08
2 Answers
No, the 496 is the number of terms after like terms are combined. Before like terms are combined there are $3^{30}$ terms. This is because you have 30 different factors, and so the number of terms you get before combining is the number of ways to choose 30 elements when there are three choices for each.
Zaricuse's answer is hinting at how to derive the formula on the Wikipedia page.
Here's another way to look at the formula on the Wikipedia page: The number of terms in the expansion of $(x+y+z)^n$ after combining is the number of ways to choose $n$ elements with replacement (since you can choose $x,y,z$ more than once) in which order does not matter from a set of 3 elements. This formula is known to be $\binom{3+n-1}{n} = \binom{n+2}{n} = \frac{(n+1)(n+2)}{2}.$ See, for example, MathWorld's entry on Ball Picking.
-
0What I did does give 496, which is the correct answer to what he is asking. – 2010-11-08
First note that every $x^ay^bz^c$ with $a + b + c = 30$ appears. One way of seeing this is observing ${\partial^{30}(x+y+z)^{30} \over \partial_x^a\partial_y^b\partial_z^c} $ at $(0,0,0)$ is $30!$, which is not zero. So for a given value of $a$, every possible $(b,c)$ with $b + c = 30 - a$ can happen. Since $b$ goes from $0$ to $30 - a$, there are $31 - a$ possibilities for $b$, each of which forces $c$ to have the single value $30 - a - b$. Thus for a given $a$ there are $31 - a$ different possible $(b,c)$. Adding this over all $a$ from 0 to 31 this gives the sum of $31 + 30 + ... + 0 = 496$.
-
0okey, modified. – 2010-11-08