Transcript Document

Tucker, Applied Combinatorics, Section 5.5 Group G
Binomial Identities
Michael Duquette & Whitney Sherman
7/17/2015
Tucker, Applied Combinatorics
Section 4.2a
1
•Consider the polynomial:
•Which can be expanded to:
(a  x)3
(a  x)(a  x)(a  x)
•Expanding again gives: aaa  aax  axa  axx  xaa  xax  xxa  xxx
•This equation can be written as: a3  3a 2 x  3ax2  x3
There are 2 choices for each term in this example and 3 terms
So 2  2  2  8 formal products.
10
So in (a  x)10 there would be 2  1024 formal products.
The question now becomes… How many formal products in
3
the expansion of (a  x) contain k x ' s and (3  k ) a ' s ?
7/17/2015
Tucker, Applied Combinatorics
Section 4.2a
2
This question is the same as asking for the coefficient
of a3 (3  k ) xk in a3  3a2 x  3ax2  x3 .
How
many three letter sequences with k x ' s and (3  k ) a ' s are there?
_________________________________________________
• The answer is C (3, k ) (3 spaces, choose k of them to be x’s) and so
the (a  x)3 can be written  3 
3 
3 
3 

0
3
a 

1
2
a x 

2
2
 ax  

3
x

3
• We see that the coefficient of a n k x k in (a  x)n will be equal to the
number of n-letter sequences formed by k x’s and (n-k) a’s so C (n, k )
i.e.
7/17/2015
 n  n k k
(a  x)    a x
k
n
Tucker, Applied Combinatorics
Section 4.2a
3
 n  n k k
(a  x)    a x
k
___________________________________________
n
•
If we set a=1 we end up with: The Binomial Theorem
n
(1  x)  
0
n
7/17/2015
 n

 1
 n
 x 
 2
 2
n
 x  ...  

n
Tucker, Applied Combinatorics
Section 4.2a
 n
x

4
Symmetry Identity
___________________________________________
•
Says that the number of ways to select a subset of k
objects out of n objects is equal to the number of ways to
select n-k of the objects to set aside.
n

k
7/17/2015

 n

n!



 k ! n  k !  n  k 
Tucker, Applied Combinatorics
Section 4.2a
5
Another
Fundamental Identity
_________________________________________________
n

k
  n  1   n  1



k
k

1
 
 

PROOF:
• There are C (n, k )committees formed out of k people chosen from a set of n
people.
•They are put into two categories, depending on whether or not the
committee contains a person p.
•If p is not part of the committee, there are C (n  1, k )ways to form the
committee from the other n-1 people.
•On the other hand if p is on the committee, the problem reduces to choosing
the k-1 remaining members of the committee from the other n-1 people.
•This can be done C (n  1, k  1) ways. Thus C (n, k )  C (n  1, k )  C (n  1, k  1)
7/17/2015
Tucker, Applied Combinatorics
Section 4.2a
6
Example 1
_________________________________________________
Show that:
n

k
 k

 m
 n

 m
 n  m 


 k  m 
•The left hand side of the equation counts the ways to select a
group of k people chosen from a set of n people, and then to select
a subset of m leaders within the group of k people.
•The right hand side first selects a subset of m leaders from n
people, and then selects the remaining k-m members of the group
from the remaining n-m people.
•Note that when m=1:
7/17/2015
n
k
k

 n  1  n
  n
 or 

 k  1  k
Tucker, Applied Combinatorics
Section 4.2a
 n  n  1
 

k

1
k



7
Pascal’s Triangle
_________________________________________________
  n  1   n  1



  k
  k  1
•Using  n
k
and C (n,0)  C (n, n)  1 for all
nonnegative n, we can recursively build successive rows in the
table of binomial coefficients: Pascal’s triangle.
•Each number in the table, except for the last numbers in a row,
is the sum of the two neighboring numbers in the preceding row.
K=0
K=1
n=0
1
K=2
n=1
1
1
K=3
n=2
n=4
2
1
n=3
1
1
3
4
1
3
6
K=4
1
4
1
Table of binomial coefficients: kth number in row n is
7/17/2015
Tucker, Applied Combinatorics
Section 4.2a
n

k



8
Pascal’s
Triangle and Interpretation
_________________________________________________
•Look at the map of the streets and label
the start (0,0).
•Label each additional vertex with a ( n, k )
where n indicates the number of blocks
traversed from (0,0) and k is the number
of times the person chose the ‘right’
branch.
(0,0)
(1,0)
•Any route to corner ( n, k )can be written
as a list of the branches (left or right)
chosen at the successive corners on the
path from (0,0) to ( n, k ) .
(2,0)
(3,1)
(4,2)
(5,3)
(6,3)
•This list is just a sequence of k Rights
and (n-k) Lefts.
•Our route from (0,0) shows the sequence
LLRRRL.
•Let s (n, k ) be the number of possible
routes from the start to corner ( n, k ) .
•This is the number of sequences of k R’s
and (n-k) L’s and so s(n, k )  C (n, k )
7/17/2015
Tucker, Applied Combinatorics
Section 4.2a
9
 n   n  1   n  1




k
k
k

1

 
 

_________________________________________________
Proof #2 of
Use our ‘block-walking’ method to prove this by example:
•To get to corner (6,3), the person needs to walk left from either (5,3) or walk
right from (5,2)
•Thus showing that
s(n, k )  s(n  1, k )  s(n 1, k 1)
(0,0)
s(6,3)  s(5,3)  s(5, 2)
(1,0)
(2,0)
(3,1)
(4,2)
(5,2)
(5,3)
(6,3)
7/17/2015
Tucker, Applied Combinatorics
Section 4.2a
10
List of Identities Found on Pg 217
_________________________________________________
Here C (n, r )  0 if 0  n
n

0
r
n

0

n

...




n
  r  1  r  2
n


  ...  
r
r
 
 

r
2
 n
 
 1



7/17/2015
 n

 2

n
2

  n  1  n  2
 n  r   n  r 1


  ...  


1
2
r
 
 


  r

n

0
r

r
 n

 1
r
k 0
m
k 0
m
k 0
2
 n
 
 2
m

k
m

k
2

n

...




n
  n  1


  r  1
2
  2n
 
  n



  n
  m  n

 


r

k
 
  r

  n
  m  n

 


r

k
m

r
 
 

 m  k   n  k   m  n 1




 r
  s
  r  s 1
Tucker, Applied Combinatorics
Section 4.2a
11
Example 2: Page 222 # 14 (b)
_________________________________________________
Question: By setting x equal to the appropriate values in the
binomial expansion (or one of its derivatives, etc. ) evaluate:
n
k  k  1  

k 
k 0
 
n
Solution:
n
n
n
n
 n
k  k  1    0  0  1    1(1  1)    2(2  1)    ...  n(n  1)  

k 
0
1
 2
 n
k 0
 
 
 
 
 
 n  n
 n
 n
 2    6    12    ...  n(n  1)  
 2  3
 4
 n
   
 
 
n
7/17/2015
Tucker, Applied Combinatorics
Section 4.2a
12
Example 2: Page 222 # 14 (b)
_________________________________________________
Compare this summation with the binomial coefficient.
n
 n  n
 n
 n
k  k  1    2    6    12    ...  n(n  1)  

k 
 2  3
 4
 n
k 0
 
   
 
 
n
Binomial coefficient:
 n  n  n 2
 n n n  n k
n
1  x        x    x  ...    x     x
k 0 k
 0  1  2
 n
 
Notice that our summation starts with the third term, therefore
we need to take the second derivative of the binomial
coefficient.
7/17/2015
Tucker, Applied Combinatorics
Section 4.2a
13
Example 2: Page 222 # 14 (b)
_________________________________________________
n  n
n
k
Binomial coefficient: 1  x      x
 
k 0 k
 
First Derivative:
n 1  x 
n 1
 n  k 1
 k   x
k
k 0
 
n
Second Derivative:
n  n  11  x 
7/17/2015
n2
 n  k 2
  k  k  1   x
k
k 0
 
n
Tucker, Applied Combinatorics
Section 4.2a
14
Example 2: Page 222 # 14 (b)
_________________________________________________
Compare the Second Derivative to our summation:
n
 n  k 2
k  k  1   x

k
k 0
 
n
 n  n
 n
 n
k  k  1    2    6    12    ...  n(n  1)  

k 
 2  3
 4
 n
k 0
 
   
 
 
n
 n n
 n  k 2
k  k  1     k  k  1  1
So

 k  k 0
k
k 0
 
 
n
 n
n2
n2


k
k

1

n
n

1
1

1

n
n

1
2
and








k
k 0
 
n
7/17/2015
Tucker, Applied Combinatorics
Section 4.2a
15
Example 2: Page 222 # 14 (b)
_________________________________________________
To Check to see whether our equation works, plug in a specific n.
Let n= 3
n(n 1)2n2  3(3 1)232  12
 3   3
2    6    6  6  12
 2   3
   
7/17/2015
Tucker, Applied Combinatorics
Section 4.2a
16
Problem for Class to Try: Page 222 # 14 (a)
_________________________________________________
Question: By setting x equal to the appropriate values in the
binomial expansion (or one of its derivatives, etc. ) evaluate:
n
 1  

k 0
k 
n
k
Binomial coefficient:
1  x 
7/17/2015
n
 n  n  n 2
 n n n  n k
      x    x  ...    x     x
 0  1  2
 n
 
k 0 k
     
 
 
Tucker, Applied Combinatorics
Section 4.2a
17
Problem for Class to Try: Page 222 # 14 (a)
_________________________________________________
Solution:
 n  n
 n
 n
 n
1
2
n
 1        1     1    ...   1  

k 0
k   0
1
 2
 n
n n n n
n
n
             ...   1  
 0 1  2  3
 n
       
 
n
k
1  x  with x  1
n
1  1  0
n
7/17/2015
Tucker, Applied Combinatorics
Section 4.2a
18