5. Give the ordinary generating function for the sequence rn in which rn is the

Question

5. Give the ordinary generating function for the sequence rn in which rn is the number of partitions of n in which each part is odd and occurs atmost three times. (Hint: it will be an infinite product, but what are the factors?) Compute the first seven terms of the generating function by appropriate algebra, and read off r1, r2, ...r7. Draw Ferrers diagrams for all the partitions of 7 whose parts are all odd and occur at most three times to see that this agrees with your answer arrived at via generation functions.

Explanation / Answer

In general, the closed form generating function for the partitions of a non-negative integer nn is given by F(x)=(1+x+x2+)(1+x2+x4+x6+)(1+x3+x6+)F(x)=(1+x+x2+)(1+x2+x4+x6+)(1+x3+x6+). (Can you see why this is?) Now, if we want to restrict this to even summands, we note that if we were to restrict F(x)F(x) to include only parenthetical polynomials which contained terms of even degree, then we would restrict the corresponding sequence in anan to those with non-zero entries only for even indices, hence limiting the partition to even (not necessarily distinct) integers. Thus, the generating function K(x)K(x)corresponding to a partition of nn into even summands is given by K(x)=(1+x2+x4+x6+)(1+x4+x8+)K(x)=(1+x2+x4+x6+)(1+x4+x8+).   By the same reasoning as above, the generating function for partitioning

nn into non necessarily distinct odd summands is Q(x)=(1+x+x2+)(1+x3+x6+)(1+x5+x10+)Q(x)=(1+x+x2+)(1+x3+x6+)(1+x5+x10+). To make this distinct, we note that if we were to restrict each parenthetical polynomial in the product to just its first two terms, we would restrict the corresponding sequence in anan to entries of just 00 or 11, hence limiting each partition to distinct integers. Thus, the generating function N(x)N(x) is: N(x)=(1+x)(1+x3)(1+x5)N(x)=(1+x)(1+x3)(1+x5).

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.