# number of terms

The following problem maybe tedious if done by hand and requires patience. After factorizing the following variables find the number of terms and the sum of the number of terms. $(a^0),(a+b)^0,(a+b+c)^0,(a+b+c+d)^0,(a+b+c+d+e)^0,(a+b+c+d+e+f)^0$ $(a^1),(a+b)^1,(a+b+c)^1,(a+b+c+d)^1,(a+b+c+d+e)^1,(a+b+c+d+e+f)^1$ $(a^2),(a+b)^2,(a+b+c)^2,(a+b+c+d)^2,(a+b+c+d+e)^2,(a+b+c+d+e+f)^2$ $(a^3),(a+b)^3,(a+b+c)^3,(a+b+c+d)^3,(a+b+c+d+e)^3,(a+b+c+d+e+f)^3$ $(a^4),(a+b)^4,(a+b+c)^4,(a+b+c+d)^4,(a+b+c+d+e)^4,(a+b+c+d+e+f)^4$ $(a^5),(a+b)^5,(a+b+c)^5,(a+b+c+d)^5,(a+b+c+d+e)^5,(a+b+c+d+e+f)^5$ $(a^6),(a+b)^6,(a+b+c)^6,(a+b+c+d)^6,(a+b+c+d+e)^6,(a+b+c+d+e+f)^6$

-
You mean distributing each thing, right? –  Jared Apr 11 '14 at 22:15
Each variables to the power of n. –  user139525 Apr 11 '14 at 22:17
What's going on... –  Shahar Apr 11 '14 at 22:17
@Jared : I'm inclined to use the word "expanding" for the process as a whole; the small steps along the way are "distributing". –  Michael Hardy Apr 11 '14 at 22:18
Pascal's triangle plays a role in this problem. –  user139525 Apr 11 '14 at 22:19

What you are searching for is the multinomial theorem.

The formula is $$(x_1+x_2+...+x_m)^n = \sum_{k_1+...+k_m=n} {n \choose k_1,...,k_m} x_1^{k_1}...x_m^{k_n}$$ where $${n \choose k_1,...,k_m} = \frac{n!}{k_1!k_2!...k_m!}.$$

For a proof take a look at the Wikipedia post: http://en.wikipedia.org/wiki/Multinomial_theorem

-

If you can do one, you can probably do them all. Let's look at $(a + b + d + d)^5$. When you distribute the terms, you choose a variable from each of five factors, each of $(a + b + c + d)$. You will generate all possible permutations of: $xxxxx$ where $x$ can be any of $a$, $b$, $c$, or $d$. You have four possible "digits" and five places to put them, therefore you have $4^5 = 1024$ ways of arranging them.

However, if a term contains the same number of $a$, $b$, $c$, or $d$'s then we say it's a "like term" (since multiplication is commutative). How many distinct groups can we get from the $1024$? We can assign a number to each digit (the exponent). This digit represents the number of times we selected this digit, e.g. $a^2b^2c$ means we chose two $a$'s, two $b$'s, and one $c$. Since we must select five things, these numbers will always add to five.

Determining the number of terms is a partitioning problem

The $a$, $b$, $c$, and $d$ are buckets which each hold a number--added together they must equal $5$. Using the stars and bars method, you can find how many ways four numbers can add to give $5$ (assuming they can be zero):

$$|||*****$$

First notice that we only need three bars (one less than the four digits). This is because these three bars create four regions: one to the left of all three, two in between the first and last, and another to the right of the last bar. This particular configuration would mean the first three buckets held $0$ and the final (fourth) bucket held all five (this could be $d^5$ for example). Since we have $5 + 3 = 8$ places to put things, deciding how many unique partitions is just figuring out how many ways to pick three places from the $8$: $\binom{8}{3} = 56$. So there will be $56$ distinct terms in the expansion of $(a + b + c + d)^5$. In general, there will be $\binom{n + m - 1}{n - 1} = \binom{n + m - 1}{m}$ in the expansion of $(x_1 + x_2 + ... x_n)^m$.

Finding sum for each Term

To find the sum for each term, assume you have found:

$$a^{a_n}b^{b_n}c^{c_n}d^{d_n}, a_n, b_n, c_n, d_n \geq 0, a_n + b_n + c_n + d_n = 5$$

You need to choose $a_n$ from $5$. In this case each choice is which factor it came from: $(a + b + c + d)_1(a + b + c + d)_2(a + b + c + d)_3(a + b + c + d)_4(a + b + c + d)_5$. And then you need to choose $b_n$ from $5$ and so on and so forth, right?

Not quite. Once you choose the $a_n$ factors for $a$, there are only $5 - a_n$ left. So for $b$, you should choose from $5 - a_n$, not $5$! This gives:

$$\binom{5}{a_n}\binom{5 - a_n}{b_n}\binom{5 - a _n - b_n}{c_n}\binom{5 - a_n - b_n - c_n}{d_n}$$

The order you do this in should not matter which means there are $4! = 24$ different ways to write this and they should all be equal. In general, you would get something like:

$$\prod_{i = 1}^{n} \binom{m - \sum_{k = 1}^{i - 1}(x_i)_n}{(x_i)_n}$$

Where $(x_i)_n$ is the exponent of the $i^\text{th}$ variable for this particular term.

Simplifying the inner product

$$\binom{5}{a_n}\binom{5 - a_n}{b_n}\binom{5 - a _n - b_n}{c_n}\binom{5 - a_n - b_n - c_n}{d_n}$$

Writing out the terms explicitly gives:

$$\frac{5!}{a_n!(5 - a_n)!}\frac{(5 - a_n)!}{b_n!(5 - a_n - b_n)!}...$$

You can see that the "bottom" term is canceling the next "top" term until you finally get to $\frac{(5 - a_n - b_n - c_n)!}{d_n!(5 - a_n - b_n - c_n - d_n)!}$. The top cancels with the previous bottom and since $a_n + b_n + c_n + d_n = 5$, the bottom factorial is just $0! = 1$, leaving:

$$\frac{5!}{a_n!b_n!c_n!d_n!}$$

Or, in general:

$$\prod_{i = 1}^{n} \binom{m - \sum_{k = 1}^{i - 1}(x_i)_n}{(x_i)_n} = \frac{m!}{\prod_1^n (x_i)_n!}$$

Which is the term you see in the multinomial theorem.

We could have arrived at this final result by reframing the problem as a permutation problem. Lets say we have a particular sequence (perhaps $aabbb$ which would represent the term $a^2b^3$) and we treat each digit as unique (i.e. $a_1a_2b_1b_2b_3$). There are $5!$ ways to rearrange distinct things. However for each unique ordering there are $2!$ ways to rearrange the $a$'s and $3!$ ways to rearrange the $b$'s. So using that we come up with the equation:

$$x\cdot 2!3! = 5! \rightarrow x = \frac{5!}{2!3!}$$

Hopefully then it's easy to see how to extend this to the general case.

-
LOL, we all came up with different answers!! –  Enjoys Math Apr 11 '14 at 22:43
My calculation for the number of terms of $(a+b+c+d)^5$ gave me 35 terms and 256 for the sum of the terms. –  user139525 Apr 11 '14 at 23:39
it's 56 terms and 1024 for the sum of terms. –  user139525 Apr 11 '14 at 23:46
The sum is easy, as @EnjoysMath stated, it's just $(1 + 1 + ... 1)^n$ which would be $4^5 = 1024$ for that particular problem. I thought you wanted the coefficient for each term. This proves though that the sum of those coefficients is $n^m$ (in general). –  Jared Apr 11 '14 at 23:51
there should be a table of Pascal's triangle and a table of power series for $n^m$ to easily find the number of terms and the sum of the terms without having to know the coefficient for each term.56 terms with the coefficient on a paper is too many. –  user139525 Apr 12 '14 at 0:01