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

Mathematics Asked by grompchompz on December 19, 2020

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.

2 Answers

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.

Correct answer by A.J. on December 19, 2020

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)

Answered by Vlad on December 19, 2020

Add your own answers!

Related Questions

Calculate Hessian of a “weird” function

2  Asked on November 12, 2021 by ben-schneider


Integral with an index

1  Asked on November 12, 2021


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP