My combinatorics class is learning about generating functions and partitions of numbers into summands. One exercise we are working on for tomorrow's lecture to better understand the concept is to find the generating function for the partition of $r$ into distinct parts.

I went through the work using Ferrer's Diagrams to show that the sum can also be expressed as a sum of differences of all of the parts. For example $$e_1+e_2+e_3+e_4...=r$$ where $e_1>e_2>e_3>e_4>...$ Then, $r$ can be expressed as a sum of differences where $f_1=e_1-e_2\geq1$, $f_2=e_2-e_3\geq1$, and so on. Since each $e_i$ is distinct, every $f_i$ will be at least 1. Thus, $$r=1*f_1+2*f_2+3*f_3+4*f_4+...$$ So, there would be at least 1 of each of the differences since they are all $\geq1$, which implies the generating function would be $$(x^1+x^2+x^3+...)(x^2+x^4+x^6+...)(x^3+x^6+x^9+...)...$$ $$\implies \left(\frac{x}{1-x}\right)\left(\frac{x^2}{1-x^2}\right)\left(\frac{x^3}{1-x^3}\right)...$$

However, when looking at the answer in the back of the book, it shows that the answer is, in fact, $$(1+x)(1+x^2)(1+x^3)...$$ Can someone explain how this is the answer?

  • $\begingroup$ The parts in your generating function aren't distinct. Look, I could pick $x^2$ from both the first and second term. The answer in the book guarantees they are all distinct. $\endgroup$ – M. Nestor Nov 15 '18 at 17:18
  • $\begingroup$ Okay, I see what you mean. So, there can only be one or no values of each digit. I see now. $\endgroup$ – lmckal45 Nov 15 '18 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.