Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Number of Terms in a Polynomial Expansion

Date: 12/01/2005 at 21:06:47
From: Frank
Subject: Number of Terms in an Expansion (a+b+c+d)^n

Hi.  I would like to know how you would calculate the total number of 
terms in the simplified expansion of (a+b+c+d)^10.  Also, what's the 
general formula in case something similar ever shows up?

With a binomial (x+y) the number of terms is one more than the power

  (x+y)^0 = 1 term
  (x+y)^1 = 2 terms

But with a larger polynomial there are many more like terms to 
combine.  If it were not simplified it would just be (number of terms 
in the polynomial)^(power the polynomial is raised to).  But there
would be many similar terms so the actual number of terms would be 
much smaller after simplifying.



Date: 12/01/2005 at 22:27:01
From: Doctor Greenie
Subject: Re: Number of Terms in an Expansion (a+b+c+b)^n

Hi, Frank --

In the expansion of (a+b+c+d)^10, every term has a combination of the 
four variables of the form

  (a^i)(b^j)(c^k)(d^l)

where i, j, k, and l are non-negative integers and

  i+j+k+l = 10

So our problem is to find the number of solutions to this equation.  

Note that a similar classic problem is the following:

  How many ways can 10 pieces of candy be divided among 4 children?

This problem is exactly analogous to yours, because in both cases we 
need to find the number of solutions to the equation

  i+j+k+l = 10

where i, j, k, and l are non-negative integers.  I will use this 
analogous problem to describe the method of solution to your problem, 
because it is easier to talk about dividing candy among kids than it 
is to talk about dividing exponents among variables.

For either of these problems, we can find the answer using a technique 
popularly known as "stars and bars".  The idea behind this method is 
the following:

(1) We represent the objects to be divided by "stars": ****
(2) To indicate dividing the object into groups, we use bars 
as "divider" symbols:  |||

For our problem, we have ten pieces of candy:

  **********

To divide these ten objects into four groups, we need three dividers:

  **********|||

The particular arrangement of the "stars and bars" shown above 
specifically represents the case where the first child gets all ten 
pieces of candy.  (In your actual problem, it would represent the 
"a^10" term.)  Each different arrangement of these stars and bars 
represents a distinct distribution of the ten pieces of candy among 
the four children.  For example, the arrangement

  ***|*|**|****

represents the case where the first child gets 3 pieces, the second 
child 1, the third child 2, and the fourth child 4.

So the number of different ways of distributing 10 pieces of candy 
among 4 children is the number of distinct arrangements of the stars 
and bars.  With 10 stars and 3 bars, this number is, as you probably 
know,

   (10+3)!                    13*12*11
  --------- = "13 choose 3" = -------- = 13*2*11 = 286
  (10!)(3!)                    3*2*1

So the number of terms in the expansion of (a+b+c+d)^10 is 286.

If we are raising an expression with "m" terms to the "n"th power, 
then we have n "stars" and (m-1) "bars"; the number of terms in the 
expansion is then

  (n+(m-1))!
  ---------- = "(n+m-1) choose (m-1)"
  (n!)(m-1)!

Note this agrees with what you noted about the number of terms in the 
expansion of (a+b)^n.  Here the number of terms, "m", is 2; so the 
number of terms in the expansion of (a+b)^n is

  "(n+m-1) choose (m-1)" = "n+1 choose 1" = n+1

Here is a link to another page in the Dr. Math archives where a 
similar problem is discussed:

  Trinomial Expansion
    http://mathforum.org/library/drmath/view/62331.html 

And here is a link to a page in the archives containing information on 
finding not only the number of terms of such an expansion, but also 
the coefficients of each term:

  Polynomial Expansion
    http://mathforum.org/library/drmath/view/62231.html 

I hope all this helps.  Please write back if you have any further 
questions about any of this.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 05/30/2007 at 08:09:22
From: Ben
Subject: Number of solutions to an equation with restrictions

My problem is similar to the one above, but with the addition that each
of the four children must get an odd number of candies and there are 16
pieces of candy instead of 10.

I cannot figure out how to calculate the number of solutions where at
least one variable is even.

I know the total number of possible distributions of the 16 pieces to 
the 4 kids is 19 choose 3 by your earlier answer.  So I'm thinking I 
can obtain the answer by subtracting that universal set by the set 
where at least one of the variables is an even integer if I can figure
that out.



Date: 05/30/2007 at 13:07:28
From: Doctor Greenie
Subject: Re: Number of solutions to an equation with restrictions

Hi, Ben --

Subtracting the two answers is an interesting idea, but it's easier
to just calculate the all-odd distributions directly.  It is 
9 choose 3 = 84.  Because the numbers are relatively small, this can
be verified by enumeration without too much difficulty.

  combination   # of arrangements
  ---------------------------------
  (1,1,1,13)    (4!)/(3!) =        4
  (1,1,3,11)    (4!)/(2!) =       12
  (1,1,5,9)     (4!)/(2!) =       12
  (1,1,7,7)     (4!)/((2!)(2!)) =  6
  (1,3,3,9)     (4!)/(2!) =       12
  (1,3,5,7)     (4!) =            24
  (1,5,5,5)     (4!)/(3!) =        4
  (3,3,3,7)     (4!)/(3!) =        4
  (3,3,5,5)     (4!)/((2!)(2!)) =  6
  ----------------------------------
                         total  = 84

Here is how to get this result using the method described above.

In order to make sure each of the four children gets an odd number of 
pieces of candy, we first give each child one piece; that leaves 12 
pieces of candy to be distributed.

To make sure every child ends up with an odd number of pieces, we 
now distribute the remaining 12 pieces in 6 groups of 2; with the 
one piece each child got at the beginning, we are thus assured that 
each child will end up with an odd number.

So the problem becomes one of distributing 6 objects among 4 
children; by the method described on the referenced page, the number 
of ways that can be done is

  C(6+(4-1),(4-1))

or

  C(9,3) = 84

I hope this helps.  Please write back if you have any further 
questions about any of this.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
High School Permutations and Combinations
High School Polynomials

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/