\fMath 510 - HW 2 Due: September 7, 5 PM Problem 1: Let n be a positive integer. How many ordered pairs (A, B) are there such that (i) A and B are both subsets of {1, . . . , n}; (ii) A and B do not share any elements, i.e. A B = . For example: if n = 1 the pairs are (, {1}) ({1}, ) (, ) and the number of pairs is 3. To get credit you must both find the formula and prove that it gives the right answer. [Hint: A is a team, B is a team . . . ] Problem 2: (This problem drawn from Challenging Mathematical Problems with Elementary Solutions, Vol. 1, by Akiva and Isaak Yaglom) Among the integers from 1 to 10, 000, 000, 000 which are there more of: those in which the digit 1 occurs or those in which it does not occur? Problem 3: (Ibid) Find the coefficients of x17 and x18 in the expansion of (1+x5 +x7 )20 without computing the polynomial. No computer allowed, you may leave the answer in form of binomial coefficients. [Hint: 17 = 5 + 5 + 7] Problem 4: (Ibid - this is an old theorem from Leonhard Euler) Prove that the number of partitions of n into at most m parts is equal to the number of partitions of n whose parts are all m. For example, if n = 5 and m = 3, the partitions of the first type are 5, 4 + 1, 3 + 2, 3 + 1 + 1, 2 + 2 + 1, while those of the second type are 3 + 2, 3 + 1 + 1, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1. [Hint: Draw the Ferrers diagrams...look for some operation you can do to them!] 1 Problem 5: Exercise 3.16a in the book (page 46, exercise begins \"Let n = 2k be even, and X a set of n elements . . . \") Problem 6: Use the recurrence relation pk (n) = k X ps (n k) s=1 and the initial values ( 1 k=1 pk (0) = 0 else p1 (1) = 1 to fill out the table of pk (n) for all k = 1, . . . 10, n = 1, . . . 10. (Recall: pk (n) = 0 if k > n) Problem 7: (Taken from an old MIT course called \"The Fine Art of Counting\") A number is called increasing if each digit is greater than the previous one, left to right. So 24589 is increasing but 566 and 8931 are not. How many increasing numbers are there? A number cannot begin with 0. [Hint: What is the maximum possible number of digits in an increasing number? How many increasing numbers are there of each length?] Problem 8: (Ibid) A pi nata containing 10 Tootsie Rolls and 5 Hershey Kisses breaks open and the candy is eagerly collected by 8 children. In how many ways can the candy be distributed among the children? [Note: the Tootsie Rolls are indistinguishable from one another, and the Hershey Kisses are indistinguishable from one another, but the children are distinguishable from one another.] Bonus Problem: Same as problem 1, but find a formula for the number of unordered pairs {A, B} of subsets A, B {1, . . . , n} which have no element in common. [So e.g. {, {1}} = {{1}, }.] 2