61/2 Discrete Structures Homework 4 Puck Rombach Suggested Exercises from the book, end of Section 6.1. (Do not hand in.) ? 15, 16, 20 27, ?? 44 51, 64 67, 97, ? ? ? 68, 71 73, 77 85, 88 92. Suggested Exercises from Section 6.2. (Do not hand in.) ? 10 24, 33 38, ?? 39 42, 43 59, ??? 73 75, 78, In all of the following problems, use combinatorial counting arguments to show the results. You should not need much algebra to manipulate the expressions. Instead, argue that two quantities are equal because they count the same set of objects. Problem 1 ? Show that the number of ordered k-subsets (subsets that have k elements in them) of a set of cardinality n is ! n k!, k (Do not use the fact that this is equal to n! (nk)! .) ......... Problem 2 ? Show that 2n 1 = n X 2nk . k=1 (Hint: count the nonempty subsets of a set of cardinality n.) ......... Problem 3 ?? Show that, ! ! n n1 k =n . k k1 (Hint: consider counting the number of k-subsets of a set of cardinality n, with each subset having one \"leader\" element.) ......... Problem 4 Show that ?? ! X ! n n i1 = . k k1 i=k (Hint: suppose that we are counting bit-string of length n with k 1s, and the last 1 appears at index i...)