Let q(n) be the number of partitions of n so that no part appears three or more

Question

Let q(n) be the number of partitions of n so that no part appears three or more times. For example, q(8) = 13 as illustrated by the partitions: Let r(n) be the number of partitions of n so that no multiple of 3 appears as a part. For example. r(8) = 13 as illustrated by the partitions: (a) Let Q(x) = q(n)xn be the generating function for q(n). Find a form for Q(x) as an infinite product of polynomials. Let R(x) = r(n) xn be the generating function for r(n). Find a form for R(x) as an infinite product of quotients of polynomials. Use the Q(x) and R(x) above to prove that q(n) = r(n) for all n 0.

Explanation / Answer

Note we can have at most 2 of each. Thus, the generating function for the 1s is 1 + x + x^2 The generating function for the 2s is 1 + x^2 + x^4 The generating function for the 3s is 1 + x^3 + x^6 Thus, the function qi(x) = 1 + x^i + x^2i and we can write the generating function as (where Pi is capital pi which indicates product) R(x) = PI i =1 to infinity (1 + x^i + x^2i) b) The number of partitions of R(x) is the generating function for 1s any number of times times the generating function for 2 any number of times times the generating function for any other number not divisible by 3 ... The generating function for 1 + x^i +x^2I = x^3i + ... = 1/1-x^i Thus, the generating function is Q(x) = PI i=1 to infinity, i not divisible by 3 1/(1-x^i) c) Note that if we multiply Q(x) by PI i=1 to infinity (1-x^i) we divide out all the not divisible by 3 terms and end up with PI i=1 to infinity, i divisible by 3 (1-x^i) or PI i =1 to infinity (1 - x^3i) Looking at a), Note that 1 + x^i + x^2i = using the geometric sum formula (1 - x^3i)/(1-x^i) Thus, we may rewrite a) as R(x) = PI i =1 to infinity (1 - x^3i)/(1-x^i) If we multiply R(x) by the same thing as Q(x), PI i=1 to infinity (1-x^i) , we eliminate the denominator on each term and end up with PI i =1 to infinity (1 - x^3i) This is the same as the result with b), so if we redivide by the same term, we have shown that R(x) = Q(x)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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