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?