How to use stars and bars to count how many terms there are in a polynomial expansion?

Question

So here's what I understand from this.
The number of terms in the expansion (before combining like terms) of any polynomial is given by ${k^{n}}$ where ${k}$ is the number of variables and ${n}$ is the degree of the polynomial. For example, ${(x + y + z)^4}$ is given by ${3^{4}=81}$.
To find the number of terms after combining, I can use the binomial theorem. This gives me ${n + 1}$ terms for an ${n}$th-degree binomial. For example, ${(x+y)^{12}}$ has 13 terms.
But the thing is, this doesn't work with trinomials and higher. My teacher instructed me to use the stars and bars method to find terms for such problems. I understand how to plug values in but don't quite understand how it works.
For example, the number of terms in the trinomial ${(x+y+z)^{7}}$ is given by ${n + k - 1 choose k - 1 }={9 choose 2} = {36}$. How exactly does this work? It seems relatively simple if you use the whole "distribute ${n}$ pieces of candies among ${k}$ number of children" type of problems, but I don't quite get it for this specific case.

A.J. · Accepted Answer

When you expand $(a+b+c+....)^n$, the sum of the exponents in every term must be $n$, and every possible term whose exponents have a sum of $n$ will be present. For example, in$(x+y+z)^7$, some possible terms are $x^2y^3z^2, xy^4z^2, x^7, y^2z^5$, plus every other term whose exponents add to $7$. Thus you are "distributing" the exponent $n$ among the $k$ terms in the bracket, which is why the calculation is the same as for distributing $n$ candies among $k$ children.

Vlad · Answer

When you expand $(x_1+x_2+...+x_k)^n$ and combine the terms, the sum will look like this: $$sum_{0leqlambda_1,lambda_2,...,lambda_kleq n, lambda_1+lambda_2+...+lambda_k=n}x_1^{lambda_1}x_2^{lambda_2}...x_k^{lambda_k}cdot c_i$$ where $c_i$s are random constants.
So the number of terms after you expand and combine is the number of ordered triplets $(lambda_1,lambda_2,...,lambda_k)$ with the property that $0leqlambda_1,lambda_2,...,lambda_kleq n$ and $lambda_1+lambda_2+...+lambda_k=n$ which gives you stars and bars. (you distribute $n$ candies to $k$ children)

How to use stars and bars to count how many terms there are in a polynomial expansion?

2 Answers

Add your own answers!

Ask a Question