Combinatorics and SumsMath 294A: Problem Solving SeminarCombinatorics is the mathematics of counting objects in various ways. One of the basic notions in combinatoricsis the kth binomial coefficient of degree n, or the number of ways to choose k objects out of n objects (a quantityoften called “n choose k”), and is equal tonk=n!(n − k)! k!, where n ≥ k ≥ 0.Note that we have the identitiesnk=nn − kandnk=nkn − 1k − 1if n ≥ k ≥ 1.The following is often useful in finding sums involving binomial coefficients, and is of course why we callnkabinomial coefficient in the first place.The Binomial Theorem. Let x and y be variables, and n ≥ 0 an integer. Then(x + y)n=nXi=0nixn−iyi.Not all of the problems below will use binomial coefficients, but they all deal with some type of enumeration.Example 1. Show that for any integer n ≥ 1,Pni=1ini= n2n−1.Example 2. Let n > 1. How many ways can the set {1, 2, . . . , n} be written as the union of k nonemptydisjoint subsets, each consisting of consecutive integers?Example 3. Give a combinatorial proof that if m, n ≥ 1 and 1 ≤ k ≤ n, thenkXi=0nimk − i=m + nk.Example 4. Consider all 2n− 1 nonempty subsets of {1, 2, . . . , n}. For each of these subsets, we find the productof the reciprocals of each of its elements. Find the sum of all of these products.Problem 1. a) Prove that for n ≥ 0,nXi=0(−1)ini= 0.b) Define µ as a function on the positive integers by µ(1) = 1, or if n > 1 has prime factorization n = pe11· · · pekkbyµ(n) =(−1)kif ei= 1 for each i,0 otherwise.Using part a), prove that for any positive integer n,Xd|nµ(d) = 0.Problem 2. Prove that the product of n consecutive integers is always divisble by n!.Problem 3. Prove that if n ≥ 1, thenn−1Xi=0(−1)ii + 1ni=(−1)n+1+ 1n + 1.Problem 4. How many subsets of {1, 2, . . . , n} have no two successive numbers?Problem 5. What is the probability of an odd number of sixes turning up in a random toss of n fair dice?(Hint: Consider12(x + y)n− (x − y)n. )Problem 6. In the Lotto, six numbers are chosen from {1, 2, . . . , 49}. How many of these six element sub-sets have at least a pair of consecutive numbers?Problem 7. Let 0 < a1< a2< · · · < anbe real numbers, and let ei= ±1. Prove thatPni=1eiaitakes atleastn+12distinct values as the eirange over the 2npossible combinations of signs.Problem 8. Prove that for each positive integer n,1 +1nn<1 +1n + 1n+1.(Hint: Use the Binomial Theorem.)Problem 9. How many ways can you select two disjoint subsets from a set consisting of n elements? We se-lect the two subsets as an unordered pair, so we do not distinguish which order the two subsets are selected.Problem 10. Let 1 ≤ r ≤ n and consider all subsets of r elements of the set {1, 2, . . . , n}. Each of these subsetshas a smallest eleme nt. Let F (n, r) denote the arithmetic mean of these smallest elements. Prove that F (n, r) =n+1r+1.Problem 11. Prove thatnXk=0hn − 2knnki2=2n2n − 2n − 1.Problem 12. Prove thatnXk=0(−1)knk1k + m + 1=mXk=0(−1)kmk1k + n +