Difference between revisions of "2005 Alabama ARML TST Problems/Problem 12"

Revision as of 22:32, 5 January 2008

Problem

Find the number of ordered pairs of positive integers $(a,b,c,d)$ that satisfy the following equation:

$a+b+c+d=12$ .

Solution

Solution 1

The generating function for $a, b, c,$ and $d$ is $1+x+x^2+x^3+\cdots$ .

$(x+x^2+x^3+\cdots)^4=x^4(1+x+x^2+x^3)^4= x^4+{4\choose 3}x^5+{5\choose 3}x^6+\cdots$

The coefficient of $x^12$ is $\binom{3+12-4}{3}=455$ .

Solution 2

We consider a bijection to the following combinatorial argument. Suppose we have twelve balls and we would like to put them into four urns. There is a positive number of balls in each urn, so we put one ball into each urn initially. We are left with eight balls to go into four urns, which is equivalent to have three dividers. Thus there are $\frac{11!}{8!3!} = 455$ ordered pairs.

@@ Line 2: / Line 2: @@
 Find the number of ordered pairs of positive integers <math>(a,b,c,d)</math> that satisfy the following equation:<center><math>a+b+c+d=12</math>.</center>
+__TOC__
 ==Solution==
-The [[generating function]] for a is <math>1+x+x^2+x^3+\cdots</math>. The same for b, c, and d.
+=== Solution 1 ===
+The [[generating function]] for <math>a, b, c,</math> and <math>d</math> is <math>1+x+x^2+x^3+\cdots</math>.
-<math>(1+x+x^2+x^3+\cdots)^4=1+4x+10x^2+\cdots</math>
+<cmath>(x+x^2+x^3+\cdots)^4=x^4(1+x+x^2+x^3)^4= x^4+{4\choose 3}x^5+{5\choose 3}x^6+\cdots</cmath>
-Since the existance of the [[Binomial Theorem]], we can assume that these are the results of choosing.
+The coefficient of <math>x^12</math> is <math>\binom{3+12-4}{3}=455</math>.
-<math>\binom{n}{n}=1</math>
+=== Solution 2 ===
+We consider a [[bijection]] to the following combinatorial argument. Suppose we have twelve balls and we would like to put them into four urns. There is a positive number of balls in each urn, so we put one ball into each urn initially. We are left with eight balls to go into four urns, which is equivalent to have three dividers. Thus there are <math>\frac{11!}{8!3!} = 455</math> ordered pairs.
-<math>\binom{n+1}{n}=4 \Rightarrow n=3</math>
+==See also==
+{{ARML box|year=2005|state=Alabama|num-b=11|num-a=13}}
-Checking <math>\binom{5}{3}</math>, it works.
-We want the coefficient of x^12, so we have <math>\binom{3+12}{3}=455</math>.
-==See Also==
+[[Category:Intermediate Combinatorics Problems]]
-{{ARML box|year=2005|state=Alabama|num-b=11|num-a=13}}

2005 Alabama ARML TST (Problems)
Preceded by: Problem 11	Followed by: Problem 13
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Page

Toolbox

Search