I wrote this up for a friend this morning. Hopefully someone else can benefit from it.
Part 1 – The relationship between the expansion of (x+y)^n and the binomial distribution
The binomial distribution for n coin flips and i heads is the probability of getting i heads with n independent coin flips assuming the probability of getting one head with one coin toss is p. (In the explanations below, we will always assume that the coin flips are independent.)
There is a very strong relationship between the binomial distribution and the expansion of (x+y)^n.
For example, for n=1 if we set x=1/3 and y=2/3, then
(x+y)^1 = x+ y = 1/3 + 2/3.
If a person flips a biased coin once and the probability of heads is 1/3, then the two possible outcomes are
– one head with probability 1/3, or
– one tail with probability 2/3.
For n=2 if we set x=1/3 and y=2/3, then
(x+y)^2
= (x+ y)*(x+y)
= x*(x+y) + y*(x+y)
= x*x + x*y + y*x + y*y
= x^2 + 2*x*y + y^2
= (1/3)^2 + 2*(1/3)*(2/3) + (2/3)^2.
(I am using * to indicate multiplication which is common for programmers. Mathematicians tend to omit the * and write x y to indicate x times y.)
If a person flips a biased coin twice and the probability of each heads is 1/3, then there are the following possible outcomes:
– two heads HH with probability (1/3)^2,
– one head and tail, HT or TH 2*(1/3)*(2/3), or
– two tails TT with probability (2/3)^2.
For n=3 if we set x=1/3 and y=2/3, then
(x+y)^3
= (x+y)*(x+y)^2
= (x+y)*(x*x + x*y +y*x + y*y)
= x*(x*x + x*y +y*x + y*y) + y*(x*x + x*y +y*x + y*y)
= x*x*x + x*x*y + x*y*x + x*y*y + y*x*x + y*x*y + y*y*x + y*y*y
= x^3 + 3*x^2*y + 3*x*y^2 + y^3
= (1/3)^3 + 3*(1/3)^2*(2/3)^2 + 3*(1/3)*(2/3)^2 + (2/3)^3.
If a person flips a biased coin three times and the probability of heads is 1/3, then there are the following possible outcomes:
– three Heads HHH with probability (1/3)^3,
– two heads and one tail, HHT, HTH, THH with probability 3*(1/3)^2*(2/3),
– one head and two tails, HTT, THT, TTH with probability 3*(1/3)*(2/3)^2, or
– three tails TTT with probability (2/3)^3.
Notice that every possible sequence of H’s and T’s for 3 flips can be obtained by fully expanding (x+y)^3 and replacing the x’s and y’s with H’s and T’s. This shows that there is a very strong correspondence between the results of n coin flips and the expansion of (x+y)^n. Note also that ( 1/3 + 2/3)^n = 1^n = 1, so all these probabilities will add up to 1.
Part 2 -Pascal’s Triangle
If we look more closely at the expansion of (x+y)^n, we see a pattern.
(x+y)^0 = 1
(x+y)^1 = 1*x+1*y
(x+y)^2 = 1*x^2 + 2*x*y + 1*y^2
(x+y)^3 = 1*x^3 + 3*x^2*y + 3*x*y^2 +1* y^3
(x+y)^4 = 1*x^4 + 4*x^3*y + 6*x^2*y^2+ 4*x*y^3 + 1*y^4
(x+y)^5 = 1*x^5 + 5*x^4*y + 10*x^3*y^2+ 10*x^2*y^3 + 5*x*y^4 + 1*y^5.
…
Looking just at the numbers in each expansion gives us a triangle which is knows as Pascal’s triangle:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
Every number is the sum of the two numbers “above” it. These numbers can be obtained from the formula
(n choose i) = n!/ ( i! * (n-i)!)
where n is the row number and i=0,1,2,…, n.
For example, in the 5th row the third entry corresponds to i=2.
b(5,1) = 5!/( 2! * 3!) = 120/( 2 * 6) = 120/12=10.
Where does the formula for (n choose i) come from? It comes from the fact that there are exactly n! ways to order the numbers 1,2,3, …, n. For example, for n=5, there are 5!=120 ways to order the numbers 1,2,3, 4, and 5.
12345 12354 12435 12453 12534 12543 13245 13254 13425 13452 13524
13542 14235 14253 14325 14352 14523 14532 15234 15243 15324 15342
15423 15432 21345 21354 21435 21453 21534 21543 23145 23154 23415
23451 23514 23541 24135 24153 24315 24351 24513 24531 25134 25143
25314 25341 25413 25431 31245 31254 31425 31452 31524 31542 32145
32154 32415 32451 32514 32541 34125 34152 34215 34251 34512 34521
35124 35142 35214 35241 35412 35421 41235 41253 41325 41352 41523
41532 42135 42153 42315 42351 42513 42531 43125 43152 43215 43251
43512 43521 45123 45132 45213 45231 45312 45321 51234 51243 51324
51342 51423 51432 52134 52143 52314 52341 52413 52431 53124 53142
53214 53241 53412 53421 54123 54132 54213 54231 54312 54321
We could call these 120 orderings.
If we look at the first two numbers in every 5 digit ordering above, there are only 10 possible prefixes: 12, 13, 14, 15, 23, 24, 25, 34, 35, and 45. So there are 10 ways to choose two numbers from a list 1,2,3,4, 5. Mathematicians would say that
(5 choose 2) = 10.
After you choose 2 numbers, there are 3 remaining. We can get every one of the 120 ordering by
a) taking each of the 10 choices of 2 numbers from 5,
b) looking at how many ways each of the chose numbers can be ordered. In this case the chosen can be ordered 2!=2 ways. (For example, 13 could ordered as 13 or 31.), and
c) looking at how many ways the unchosen numbers can be ordered. In this case each choice can be ordered 3!=6 ways. (For example, if we chose 13, then 2, 4, and 5 remain and those numbers can be ordered as 245, 254, 425, 452, 524, and 542.)
So there were 2! orderings for the first 2 and 3! orderings for the remaining 3. All 120 orderings can be found by
a) one of 10 choices, (10 = 5 choose 2),
b) one of the 2 ways to order the chosen, (2=2!) and
c) one of the 6 ways to order the unchosen (6=3!).
The resulting formula is
Number of orderings of 1,2,3,4, and 5 = 5! = 120 = 10*2*6 = (5 choose 2)*2!*3!.
In general, if you have the numbers 1,2,…, n, and you choose i numbers, then every one of the n! orderings can be reproduced from
a) (n choose i) ways to select i numbers from the list 1,2,3,…,n,
b) i! ways to order the i chosen numbers, and
c) (n-i)! ways to order the unchosen.
The resulting formula is
n! = (n choose i) * i! * (n-i)! .
If we divide both sides by i! * (n-i)!, we get
n! / ( i! * (n-i)! ) = (n choose i).
Part 3 – Conclusion
We showed that there is a very strong relationship between the expansion of (x+y)^n and the binomial distribution of n coin flips. The coefficient for each term of (x+y)^n has the formula
(n choose i) = n!/( i! * (n-i)! ).
We derived this formula. The final result is that the probability of getting i heads when flipping n coins each of which has probability p of heads is
“the number of ways of choosing which of the n coins are heads” * “the probability of flipping i heads in a row” * “ the probability of flipping (n-i) tails in a row”
= (n choose i) * p^i * (1-p)^(n-i)
= n!.( i! * (n-i)! ) * p^i * (1-p)^(n-i).