![]](http://coweb.math.gatech.edu:8080/files/schemes/math/after.gif)
Binomial Theorem, Permutations and Combinations and Ball and Urn Examples, Brett Fletcher(A5), Leslie Myles(A5), and Tim Sweeney(A1)
THE BINOMIAL THEOREM
This theorem is useful when expanding power series or finding a difficult power (such as 5.12). To guess the theorem, we expand the first few powers of (x+y):
(x+y)^0 = 1
(x+y)^1 = 1x + 1y
(x+y)^2 = 1x^2 + 2xy + 1y^2
(x+y)^3 = 1x^3 + 3(x^2)y + 3xy^2 + 1y^3
(x+y)^4 = 1x^4 + 4(x^3)y + 6(x^2)y^2 + 4xy^3 + 1y^4
Looking at the powers of x and y, it is easy to see the pattern: (x^i)y^j, where i decreases by one each time and j increases. The coefficients are similarly easy to recognize as the entries of Pascal’s Triangle, which can be written as combinations, C(n,k), where n is the row and k the column of the entry.
Using these two facts we can write a general solution for (x+y)^n:
Theorem 1 (page 355): The Binomial Theorem
For all nonnegative integers n,
(X+Y)^n = SUM from k=0 to n of [C(n,k)x X^(n-k) x Y^k]
It should be easy to see that the theorem is the same if you switch the values for x and y:
(X+Y)^n = SUM from k=0 to n of [C(n,k)x X^(n-k) x Y^k]
is equal to
(X+Y)^n = SUM from k=0 to n of [C(n,k)x X^k x Y^(n-k)
A few examples:
Expand (x+5)^5.
Then y = 5 and n = 5 in the Binomial Theorem and we get
(x+5)^5 = 1X^5x5^0 + 5X^4x5^1 + 10X^3x5^2 + 10X^2x5^3 +
5X^1x5^4 + 1X^0x5^5
= X^5 + 25X^4 + 250X^3 + 1250X^2 + 3125X + 3125
Sum: SUM from k=0 to n of [C(n,k)x (-1)^(k-1)x 5^(n-k)]
First, we have to write it in the correct form. Factor out (-1).
SUM from k=0 to n of [C(n,k)x (-1)^(k-1)x 5^(n-k)] is equal to
(-1)x[SUM from k=0 to n of [C(n,k)x (-1)^(k)x 5^(n-k)]]
Now we can use the Binomial Theorem in reverse.
(-1)x[SUM from k=0 to n of [C(n,k)x (-1)^(k)x 5^(n-k)]] is equal to
(-1)x(-1 + 5)^n
which is then equal to (-1)(4^n)
PERMUTATION
Definition: a permutation of n things chosen r at a time is a particular ordering of subset of r chosen from n. The order of the subset matters, so the subset {1, 2} is not the same as the subset {2, 1}.
Notation: n things chosen r at a time,
P(n, r)
P(n, r) = n! / (n-r)!
Example: How many permutations or different arrangements can the set {1, 2, 3, 4} be ordered in taking 2 at a time?
For this problem the n = 4 and r = 2
P(4, 2) =
4! / (4-2)!
4! / 2!
(4x3x2x1) / (2x1)
12
Proof: {1, 2} {2, 1}
{1, 3} {3, 1}
{1, 4} {4, 1}
{2, 3} {3, 2}
{2, 4} {4, 2}
{3, 4} {4, 3}
COMBINATION
Definition: a combination of n things chosen r at a time is any unordered subset of r chosen from n. The order of the subset does not matter, so the subset {1, 2} is the same as {2, 1}
Notation: n things chosen r at a time, or “n choose r”,
C(n,r)
C(n,r) = P(n,r) / r! = n! / [(n-r)! r!]
Example: How many combinations or subset of 2 can there be from the set
{1, 2, 3, 4}?
In this problem n = 4 and r = 2
C(3,2) =
P(4,2) / 2!
4! / [(4-2)! 2!]
(4x3x2x1) / [(2x1) x (2x1)]
6
Proof: {1, 2}
{1, 3}
{1, 4}
{2, 3)
{2, 4}
{3, 4}
BALL AND URNS
There are four standard ball and urn problems.
1) U number of distinguishable urns and B number of distinguishable balls.
2) U number of distinguishable urns and B number of indistinguishable balls.
3) U number of indistinguishable urns and B number of distinguishable balls.
4) U number of indistinguishable urns and B number of indistinguishable balls.
Distinguishable balls and urns are usually labeled with numbers such as Urn1, Urn2 and Urn3. But they can be labeled anyway to make each urn or ball unique compared to the other ones in the problem.
Indistinguishable balls and urns look exactly like any other ball or urn in the problem.
For the first two problem types listed above there are simple formulas for them.
Problem type one has the formula: u^b
Problem type two has the formula: C(b+u-1,b) or C(b+u-1,u-1)
[In the above formulas u= the # of urns and b= the # of balls]
Problem type three has a long and complex formula which is described to you on pages 370-371 in the Discrete Algorithmic Mathematics book the Third Edition. However Professor Morley said that this formula is worthless.
Problem type four has no formula to solve it but is rather easy to figure out. An easy way to do this type of problem will be stepped out below in an example problem.
Examples:
1) How many ways can you put 5 balls into 3 urns if: a) both the urns and balls are distinguishable, b) the urns are distinguishable but the balls are not, and c) both the balls and urns are indistinguishable?
a) 3^5 = 243 different ways
b) C(3+5-1,2)= C(7,2)= 21 or C(3+5-1,5)= C(7,5)= 21
c) To do this problem I like to start with all the balls in one urn and then move them out one at a time. So that my final answer looks like this:
5 _ _ (where the underscores represent urns that contain no balls)
4 1 _
3 1 1
3 2 _
2 2 1
So there are 5 different ways to pu the balls in the urns for this problem. Note: This type of problem always results in the least possible ways.
2) How many ways can this expression be sovled? x+y+z=10
First off you may think to yourself that there is no way that this is a ball and urn problem. It is though. If you think of the variables as your urns, which are distinguishable, then 10 becomes the number of indistinguishable balls. So then this problem becomes rather simple since you can use the eguation from problem type two from above.
So the answer would be:
C(12,2) = 66
Now what would happen if we said that x must be 4? Well then you would have 2 distinguishable urns with 6 indistinguishable balls left. So although we through in a bit of a twist, the problem remains just as easy as it was in the beginning. (The answer would be 6. See if you can do it.)
