Question

Book: A Course in Enumeration. Author: Martin Aigner

Chapter 1 Page:29

1.37 Use the polynomial method to show that sn lkti -o )sni Can you find a combinatorial proof?

Answer 1

LHS is number of subsets of {1,...,n + k + 1} of size n, counted directly. RHS counts same, by rst specifying the smallest element not in subset (if smallest missed element is 1, all n elements must be chosen from {2,...,n + k + 1},k+n n ways, the i= n term; ifsmallest missed element is 2, then 1 is in subset and remaining n−1 elements must be chosen from {3,...,n+k+1},m+n−1 n−1 ways, the i= n−1 term; etc., down to: if smallest missedelement is n + 1, then {1,...,n} is in subset and remaining 0 elements must be chosen from {n + 2,...,i + 1},k+0