On this page
(1 + x + x²)ⁿ looks much harder than a binomial. It isn't: the counting idea behind nCr lets you pull out one coefficient without expanding everything.
What does the multinomial theorem say?
The multinomial theorem says (x₁ + … + x_k)ⁿ is the sum of n!/(n₁! … n_k!) × x₁^n₁ … x_k^n_k over all non-negative integers with n₁ + … + n_k = n, as stated in section 26.4 of the NIST Digital Library of Mathematical Functions.
The number n!/(n₁! … n_k!) is the multinomial coefficient. Picture n brackets multiplied together. You pick one term from each, and the multinomial coefficient counts the ways to decide which n₁ brackets give x₁, which n₂ give x₂, and so on. With two terms it is the ordinary nCr, the same reason binomial coefficients are combinations.
The distinct terms number C(n + k − 1, k − 1) (Wikipedia: Multinomial theorem), which is stars and bars in disguise.
How do you find the coefficient of xⁿ in (1 + x + x²)ⁿ?
Say a brackets give 1, b give x and c give x². Then:
a + b + c = n, since every bracket gives something.
b + 2c = the power you want.
Each solution (a, b, c) adds n!/(a! b! c!).
Worked example: the coefficient of x⁴ in (1 + x + x²)⁴, so b + 2c = 4. Let c run up from 0:
c = 0: b = 4, a = 0, giving 4!/(0! 4! 0!) = 1
c = 1: b = 2, a = 1, giving 4!/(1! 2! 1!) = 12
c = 2: b = 0, a = 2, giving 4!/(2! 0! 2!) = 6
Total: 1 + 12 + 6 = 19.
Loop over c, the count of the highest power, and b and a follow on their own. For xⁿ, b = n − 2c and a = c, so the coefficient is the sum of n!/(c! c! (n − 2c)!) for c from 0 to ⌊n/2⌋.
The coefficient of xⁿ in (1 + x + x²)ⁿ is the central trinomial coefficient, which runs 1, 1, 3, 7, 19, 51, 141, 393, according to OEIS A002426. It is also the largest coefficient in the expansion. The full row for n = 4 is 1, 4, 10, 16, 19, 16, 10, 4, 1 (OEIS A027907).
What changes when the terms have their own coefficients?
Same steps, but each constant is raised to the number of times you picked its term. For x⁴ in (1 + 2x + 3x²)³, a + b + c = 3 and b + 2c = 4:
c = 2: b = 0, a = 1, giving 3!/(1! 0! 2!) × 3² = 3 × 9 = 27
c = 1: b = 2, a = 0, giving 3!/(0! 2! 1!) × 2² × 3 = 3 × 12 = 36
c = 0: b = 4 would need a = −1, so this case is impossible
Answer: 27 + 36 = 63. The usual slip is forgetting the 2² or the 3². For two separate brackets multiplied together, see the coefficient of xⁿ in the product of two binomial expansions.
How does counting non-negative solutions give the coefficient?
In (1 + x + … + x^m)ⁿ, the coefficient of x^r is the number of non-negative solutions of y₁ + … + yₙ = r with each yᵢ at most m, where yᵢ is the power taken from bracket i. Count with stars and bars, then subtract the solutions that break the cap.
Worked example: the coefficient of x⁵ in (1 + x + x² + x³)⁴.
Without caps, y₁ + y₂ + y₃ + y₄ = 5 has C(8, 3) = 56 solutions.
If some yᵢ is 4 or more, write yᵢ = 4 + zᵢ; the remaining 1 can be shared in C(4, 3) = 4 ways, for each of 4 choices of i, so 16.
Two variables cannot both reach 4, since 8 is more than 5.
Answer: 56 − 16 = 40.
Which method should you use?
Three or more terms, small n: list the (a, b, c) solutions and add n!/(a! b! c!).
Constants in front: same list, times each constant's power.
All coefficients 1, as in (1 + x + … + x^m)ⁿ: stars and bars, minus capped cases.
Before the final answer: put x = 1, or try n = 2 by hand.
If your count keeps coming out different, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer, so you can find the line where yours went wrong. If the gap is the idea itself, the Fermi Concept Library has a lesson on every concept in mathematics.
One to try now: find the coefficient of x⁶ in (1 + x + x²)⁶ by looping over c from 0 to 3. You should get 141 (OEIS A002426).
