Binomial Coefficients: Selected Exercises Preliminaries What is the coefficient of x2y in (x + y)3? (x + y)3 = (x + y)(x + y)(x + y) = (xx + xy + yx + yy)(x + y) = xxx + xyx + yxx + yyx + xxy + xyy + yxy + yyy = x3 + 3x2y + 3xy2 + y3. The answer thus is 3.

There are 8 terms in the formal expansion. Answer: The # of ways to pick the y position in the formal expansion: C(3, 1). 2 Preliminaries How many terms are there in the formal expansion of (x + y)n? How many such terms have exactly 3 ys? This is the coefficient of xn-3y3 in (x + y)n? How many such terms have exactly j ys?

3 The Binomial Theorem Let x & y be variables, and n NN. Partition the set of 2n terms of the formal expansion of (x + y)n into n + 1 classes according to the # of ys in the term: (x + y)n = j=0 to n C( n, j )xn-jyj = C(n, 0)xny0 + C(n,1)xn-1y1 + + C(n, j)xn-jyj + + C(n,n)x0yn. 4

Pascals Identity Let n & k be positive integers, with n > k. Then C(n, k) = C(n - 1, k 1) + C(n - 1, k). Proof by a combinatorial argument: 1. The left hand side counts the number of subsets of size k from a set of n elements. 2. The right hand side counts the same subsets using the sum rule: Partition the subsets into 2 disjoint classes 1. Subsets of k elements that include element 1: 1. Pick element 1: 1 2. Pick the remaining k 1 elements from the remaining n - 1 elements:

C(n - 1, k 1). 2. Subsets of k elements that exclude element 1: 1. Pick the k elements from the n - 1 remaining elements: C(n - 1, k). 5 *30 Give a combinatorial proof that k=1,n kC(n, k)2 = nC( 2n 1, n 1 ). Hint: Show that the equations LHS and RHS are different ways to count the same thing:

The # of ways to select a committee with n members from a group of n math professors & n computer science professors, such that the committee chair is a mathematics professor. 6 *30 Solution Proof by a combinatorial argument The RHS counts the # of such committees by: 1. Pick the chair from the n math professors: n 2. Pick the remaining n 1 members from the remaining 2n 1 professors: C( 2n 1, n 1 )

The LHS counts the same committees by: Partition the set of such committees into disjoint subsets, according to, k, the # of math professors on the committee. For each k, 1. Pick the k math professor members: C(n, k) 2. Pick the committee chair: k 3. Pick the n - k CS professor members: C( n, n k ) = C( n, k ) 7 Combinatorial Identities

Manipulation of the Binomial Theorem Committee arguments Block walking arguments for identities involving sums 8 Manipulation of the Binomial Theorem Prove that C(n, 0) + C(n, 1) + . N. N. N + C(n, n) = 2n. In general,

1. Algebraically manipulate the binomial theorem. 2. Evaluate the resultant equation for suitable values of x & y to get the desired result. Prove that n2n 1 = 1C(n, 1) + 2C(n, 2) + 3C(n, 3) + . N. N. N + nC(n, n). 9

Committee Arguments Show that 1. C(n, k)C(k, m) = C(n, m)C(n m, k m). Hint: committees of k people, m of whom are leaders. 2. k = 0 to r C(m,k)C(n, r - k) = C(m + n, r). Hint: committees of r people taken from m men & n women. 10

Block-Walking Arguments 1. Draw Pascals triangle. 2. Interpret a node in the triangle as the # of ways to walk from the apex to the node, always going down. Show that 1. C(n, k) = C(n 1, k) + C(n 1, k 1) 2. C(n,0)2 + C(n,1)2 + . . . + C(n,n)2 = C(2n,n). 11 Characters

N N . ~ N N N N N N N N N N N N N N N N N

12 *10 Give a formula for the coefficient of xk in the expansion of (x + 1/x)100, where k is an even integer. 13 *10 Solution By the Binomial Theorem, (x + 1/x)100 = j=0 to 100 C(100, j)x100-j(1/x)j

= j=0 to 100 C(100, j)x100-2j. We want the coefficient of x100-2j, where k = 100 2j j = (100 k)/2. The coefficient we seek is C(100, (100 k)/2). 14 20 Suppose that k & n are integers with 1 k < n. Prove the hexagon identity

C(n - 1, k 1)C(n, k + 1)C(n + 1, k) = C(n-1, k)C(n, k-1)C(n+1, k+1), which relates terms in Pascals triangle that form a hexagon. Hint: Use straight algebra. 15 20 Solution C( n 1, k 1 )C( n, k + 1 )C( n + 1, k ) = (n 1)! n! (n+1)! _______________________________________

(k 1)!(n k)! (k + 1)!(n k 1)! k! (n + 1 k)! = C( n 1, k )C( n, k 1 )C( n + 1, k + 1 ). 16