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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.