程序代写代做 Math 422 Homework # 2

Math 422 Homework # 2
(due Tuesday, February 11)
1. Prove directly that 􏰁∞ p(n)xn converges for |x| < 1 by comparing p(n) with c(n), 2 2. Let pu(n) be the number of partitions of n whose largest summand occurs exactly once. (For example, pu(4) = 3 from the partitions 4 = 3+1 = 2+1+1.) Find and prove an identity for pu(n) in terms of the partition numbers. n=0 the number of compositions of n. 3. (a) For n ≥ 0, let sn denote the number of partitions of n with summands in {2, 3}. Show (directly) that (b) Explain how the identity 􏰀⌊n/6⌋ if n ≡ 1 (mod 6), sn = ⌊n/6⌋ + 1 otherwise. 1−x6 1 (1 − x2)(1 − x3) = −x + 1 − x leads to the same formula. 4. Let dn denote the number of derangements of n distinct objects. (a) Prove the recurrence dn = ndn−1 + (−1)n for n ≥ 1. (b) Show that the exponential generating function for dn is e−x 1 . 1−x 5. How many linear arrangements of the symbols x1, x1, x2, x2, . . . , xn, xn satisfy the prop- erty that no two identical symbols are adjacent? 6. For positive integers m and n, let f(m,n) be the number of words of length n over the alphabet [m] which do not equal any of their own cyclic shifts. Use Mobiu ̈s inversion to find a formula for f(m,n). (For example, 131221 is counted by f(3,6), but 133133 is not.) 7. Let A1, . . . , An be finite sets, and define Sk as the sum of their k-wise intersection sizes. In terms of the Sk, how many elements belong to an even number of the sets Ai?