(a) Define An,k = n! k!(nk)! , 0 k n. Prove that the numbers An,k satisfy the recurrence relation An,k = An1,k1 + An1,k. (Recall that in one of the lectures we used this recurrence relation without proof to give an alternative proof of the formula n k = n! k!(nk)! .) (b) The binomial coefficients n k satisfy the well-known formula Xn k=0 n k = 2n (this is saying that the sum of the numbers in each row of Pascal's triangle is a power of 2). Give a combinatorial proof of this identity by interpreting both sides as counting the same thing. Hint. Recall that n k is the number of k-element subsets of {1, 2, . . . , n}. What does the sum of these numbers over k = 0, 1, . . . , n count? And what does 2n count?) Remark. Another, non-combinatorial way of proving this identity is to set x = y = 1 in the binomial theorem (x + y) n = Pn k=0 n k x ky nk

6. (a) Define An,k = k!(n-k)!' n! 0