Transcript Tucker, Applied Combinatorics, Sec j

Applied Combinatorics, 4th Ed.
Alan Tucker
Section 5.5
Binomial Identities
Prepared by Jess Scheld and Amanda Dargie
5/18/05
Tucker, Sec. 5.5
1
Binomial Theorem
 n  n  n 2
 n k
 n n
(1  x)       x    x  ...    x  ...    x
 0  1  2
k
 n
n
• The coefficients represent choosing k x’s
out of n choices
(1  x)3  (1  x)(1  x)(1  x )
 3   3
 3  2  3 3
   x x  x
 0 1
 2
 3
 1  3x  3x 2  x3
5/18/05
Tucker, Sec. 5.5
2
Properties of Binomial
Coefficients
n
 n 
n!

 

 k  k !(n  k )!  n  k 
• This says that the number of ways to
select a subset of k objects out of a set of
n objects is equal to the number of ways
to select a group of (n-k) of the objects to
set aside (the objects not in the subset).
5/18/05
Tucker, Sec. 5.5
3
Binomial Properties
 n   n  1  n  1 
 


k
k
k

1
  
 

• One Proof:
– Committee of n people and you need to choose k, based
on whether person P is there or not.
– 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
– If P is part of the committee, then we choose k-1
remaining members from the other n-1 people. Thus,
we get the identity above.
5/18/05
Tucker, Sec. 5.5
4
Binomial Properties
 n   n  1  n  1 
 


 k   k   k  1
• Another Proof:
 n  1
(n  1)!



 k  k !(n  1  k )!
 n  1
(n  1)!



k

1

 (k  1)!(n  k )!
(n  1)!
(n  k )
(n  1)!
k
*

*
k !(n  1  k )! (n  k ) (k  1)!(n  k )! k
n
(n  1)![(n  k )  (k )]
(n)!


 
(k )!(n  k )!
(k )!(n  k )!  k 
5/18/05
Tucker, Sec. 5.5
5
Example 1
 n  k   n  n  m 
     

 k  m   m  k  m 
• The left side counts the ways to select a group of k
from a group of n, and to then select a group of m
leaders from the group k.
• The right side selects the m leaders from n people
first, and then selects the k - m people from the n m group
5/18/05
Tucker, Sec. 5.5
6
Example 1 Algebraically
 n  k   n  n  m 
     

k
m
m
k

m
    

n
n!

 
 m  m !(n  m)!
n  m
(n  m)!



k

m

 (k  m)!(n  k )!
n!
(n  m)!
n!
k!
*

*
m !(n  m)! (k  m)!(n  k )! m !(k  m)!(n  k )! k !
 n  k 
n!
k!

*
   
(n  k )!k ! m !(k  m)!  k  m 
5/18/05
Tucker, Sec. 5.5
7
Example 1 cont.
 n  k   n  n  m 
     

 k  m   m  k  m 
• When m=1, there is a special form of the
equation
 n
 n  1
 n  n  n  1
k    n
 or    

k 
 k  1
 k  k  k  1
5/18/05
Tucker, Sec. 5.5
8
Behavior of Binomial Coefficients
• For a fixed integer n, the values of the
binomial coefficients C(n,k):
– Increase as k increases as long as k ≤ n/2
– Decrease as k increases as long as k ≥ n/2 + 1
5/18/05
Tucker, Sec. 5.5
9
Pascal’s Triangle
n=0
n=1
n=2
n=3
n=4
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
n=n
• Each number in the table except the first and last numbers in a row, is
the sum of the two neighboring numbers in the preceding row. The n’s
represent how far down you are, and the k’s are how many rights you
have taken.
5/18/05
Tucker, Sec. 5.5
10
Block-Walking using Pascal’s
Triangle
• Begin at point (0,0), move down the page.
• Label each street corner in the network with a pair of
numbers (n,k), where n indicates the number of
blocks traversed from (0,0) and k the number of times
the person chose the right branch at intersections.
• Write the route taken by a sequences of R’s (right
branches) and L’s (left branches).
• s(n,k) = number of possible routes from (0,0) to
corner (n,k)
• s(n,k)=C(n,k)
5/18/05
Tucker, Sec. 5.5
11
Block-walking
Start (0,0)
(4,2)
 4
4!
4 *3*2* 1


6
 
 2  2!(4  2)! 2 * 1 * 2 *1
5/18/05
Tucker, Sec. 5.5
12
Binomial Identities
 n  n  n
 n
(6)          ...     2 n
 0  1  2
 n
 n   n  1  n  2 
 n  r   n  r  1
(7)    

  ...  


r
0  1   2 
 r  

 r   r  1  r  2 
 n   n  1
(8)    

  ...     

r
r
r
r
r

1
  
 

  

2
2
2
2
n  n  n
 n   2n 
(9)          ...      
0 1  2
n  n 
5/18/05
Tucker, Sec. 5.5
13
Binomial Identities cont.
 m  n   m  n 
(10)   


k  0  k  r  k 
 r 
r
 m  n   m  n 
(11)   


k  0  k  r  k 
mr
m
 m  k  n  k   m  n  1
(12)  



r  s   r  s  1 
k 0 
m
5/18/05
Tucker, Sec. 5.5
14
Proof (Identity 6)
 n  n  n
 n
n



...


2
     
 
0
1
2
     
 n
• Committee argument:
– 2 ways to count all subsets of any size of n
people
• Summing number of subsets of size 0, 1, 2… (left
side of equation)
• Counting all subsets by whether or not the first
person is in the subset, whether the second person
was in the subset, and so on, which gives
2*2**...*2 (n times)  2n
5/18/05
Tucker, Sec. 5.5
15
Example 2
Verify identity (8) by block-walking and
committee-selection arguments.
 r   r  1  r  2 
 n   n  1
(8)    

  ...     

r  r   r 
 r   r  1
• Consider the case where r = 2 and n = 6.
5/18/05
Tucker, Sec. 5.5
16
Example 2
•the corners (k, 2), k = 2,3,4,5,6 are marked with a * and corner (7,3) is marked with
an o
•Observe that the right branches at each starred corner are the locations of last
possible right branches on routes from (0,0) to (7,3)
•In general, if we break all routes
from (0,0) to (n+1, r +1) into
subcases based on the corner where
the last right branch is taken, we
obtain identity (8)
*
*
*
*
*
o
5/18/05
Tucker, Sec. 5.5
17
Example 2
•
•
•
•
Restate the block-walking model as a committee selection: if the kth turn is
right, this corresponds to selecting the kth person to be on the committee; if the
kth turn is left, the kth person is not chosen
Break the ways to pick r +1 members of a committee from n +1people into
cases depending on who is the last person chosen: (0,0)
the (r +1)st, the (r +2)nd,…, the (n +1)st
If the (r + k + 1)st person is the last
*
chosen, then there are C(r + k, r)
*
ways to pick the first r
*
members of the committee
*
Identity (8) now
*
follows.
o
(7,3)
5/18/05
Tucker, Sec. 5.5
18
Example 3
Verify identity (9) by a block-walking argument.
2
(9)
5/18/05
2
2
2
n n n
 n   2n 
         ...      
 0 1  2
 n  n 
Tucker, Sec. 5.5
19
Example 3
•
•
•
•
The number of routes from (n, k) to (2n, n) = number of routes from (0, 0) to (n, n
– k)
[since both trips go a total of n blocks with n – k to the right (and k to the left)]
So number of ways to go from (0, 0) to (n, k) and then on to (2n, n) is C(n, k) x
C(n, n –k)
By theorem (2), C(n, n- k) = C(n, k)
Thus, the number of routes from (0, 0) to (2n, n) via (n, k) is C (n, k )2
• Summing over all k – that is, over all
intermediate corners n blocks from the
start – we count all routes from (0, 0) to
(2n, n)
• So this sum equals C(2n, n) and
identity (9) follows.
n
2n
5/18/05
Tucker, Sec. 5.5
20
Example 4
Evaluate the sum 1  2  3
+
2  3  4 + …+  n  2 n 1 n
• The general term in this sum, (k – 2)(k – 1)k, is equal to
P(k ,3) 
k!
(k  3)!
•Recall that the numbers of r-permutations and of r-selections
differ by a factor of r!
k!
C (k ,3) 
 P(k ,3)  3!C (k ,3)
(k  3)!3!
5/18/05
Tucker, Sec. 5.5
21
Example 4
• So the given sum can be rewritten as
  3  4 
 3
 4
 n
 n
3!   3!   ...  3!   3!       ...    
 3
 3
 3
 3
  3  3 
By identity (8)  r    r  1   r  2   ...   n    n  1
r  r   r 
 r   r  1
this sum equals
5/18/05
 n  1
3!

4


Tucker, Sec. 5.5
22
Example 5
Evaluate the sum
1  2  3  ...  n .
2
2
2
2
•A strategy for problems whose general term is not a
multiple of C(n, k) or P(n, k) is to decompose the term
algebraically into a sum of P(n, k) or C(n, k)-type terms.
2
•In this case, the general term k can be written as
k  k (k  1)  k
2
5/18/05
Tucker, Sec. 5.5
23
Example 5 cont.
So the given sum can be rewritten as
[(1 0)  1]  [(2 1)  2]  [(3  2)  3]  ...  [ n( n  1)  n]
 [(2 1)  (3  2)  ...  n(n  1)]  (1  2  3  ...  n)
  2  3
 n    1   2 
 n 
  2    2    ...  2           ...    
 2    1   1 
 1 
  2  2
 n  1  n  1
 2


 3   2 
by identity (8).
5/18/05
Tucker, Sec. 5.5
24
Example
• By setting x equal to the appropriate values in the
binomial expansion (or one of its derivatives, etc.)
evaluate:
n
k (k  1)  

k 0
k 
n
5/18/05
Tucker, Sec. 5.5
25
Solution
• Take 2nd derivitive:
• So x =1
k (k  1)( x)
k 2
 n(n  1)(1  x)
n2
n
 
k 
 n(n  1)(2) n  2
5/18/05
Tucker, Sec. 5.5
26
For the class to try…
• 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
5/18/05
Tucker, Sec. 5.5
27
Solution
n
k
x    1  x 

k 0
k 
n
k
n
k
(1)    1  (1) 

k 0
k 
n
So, letting x  1 ..
k
 (1  1) k
0
5/18/05
Tucker, Sec. 5.5
28