Partitions without repetition

Question

I want to know how many partitions without repetition 19 has. I know I should see the coefficient of $x^{19}$ in $$\prod_{k=1}^\infty(1-x^k),$$ but i'm having trouble finding it. Ay hint?

Answer 1

The number of partitions of $1$ is just $1$. The number of partitions of $2$ is going to be given by the coefficient of $x^2$ in

$$(1+x+x^2)(1+x^2),$$

since

$$(1+x+x^2)(1+x^2) = 1 + x + 2x^2 + x^3 + x^4.$$

One way of reasoning this out is the following: the term on the left represents adding ones, so $1$ means we add $0$ ones, $x$ means we add $1$ one, and $x^2$ means we add $2$ ones. The term on the right represents adding twos, so $1$ means we add $0$ twos, $x^2$ means we add $1$ two. When we multiply them together, we are getting the mixed terms. For example, $1 + 2 = 3$, and $x \cdot x^2 = x^3$. Notice we don't have repetitions here.

Of course, adding more ones won't change anything when it comes to partitioning $2$, and this lines up with multiplying these series. If I check

$$(1+x+x^2+x^3)(1+x^2),$$

the coefficient of $x^2$ remains unchanged. So using formal series, I could say that the number of ways of partitioning two is given by the coefficient of $x^2$ in the series

$$ \left(\sum_{i=0}^\infty x^i \right)\left(\sum_{i=0}^\infty x^{2i} \right).$$

This will come in handy later.

If we want to figure out how many different ways to uniquely partition $19$, we want to find the coefficient of $x^{19}$ in the following series:

$$\left(\sum_{i=0}^{19} x^i \right) \left(\sum_{i=0}^{9} x^{2i} \right) \left( \sum_{i=0}^{6} x^{3i}\right) \left(\sum_{i=0}^{5} x^{4i} \right)\left(\sum_{i=0}^{3} x^{5i} \right) \left(\sum_{i=0}^{3} x^{6i} \right)\left(\sum_{i=0}^{2} x^{7i} \right)\left(\sum_{i=0}^{2} x^{8i} \right)\left(\sum_{i=0}^{2} x^{9i} \right)\prod_{j=10}^{19}(1+x^{ji}).$$

If you want to be a little less optimal but a little more concise, you can find the coefficient of $x^{19}$ in the series

$$ \prod_{j=1}^{19} \left(\sum_{i=0}^{19} x^{ij} \right).$$

If you don't feel like doing that by hand, notice that this is the same thing as calculating the coefficient of $x^{19}$ of the Taylor series at $x=0$ of

$$\prod_{j=1}^{19} \frac{1}{1-x^j}.$$

We plug this into Wolfram: https://www.wolframalpha.com/input?i=series+at+x%3D0+of+product+from+j%3D1+to+19+of+1%2F%281-x%5Ej%29

We get $490$ different partitions without repetition.

In fact, we can say that the number of partitions without repetition of $m$ is given by the coefficient of $x^m$ in the series expansion of

$$ \prod_{j=1}^\infty \frac{1}{1-x^j}$$

at $x=0$. This lines up with what Wolfram tells us: https://www.wolframalpha.com/input?i=series+expansion+of+the+product+from+j%3D1+to+infinity+of+1%2F%281-x%5Ej%29

Answer 2

I understand "without repetition" in the question to mean partitions into distinct parts. There are 490 partitions of 19, but only 54 have distinct parts.

For the generating function, you want the product of terms $(1 + x^i)$ for each positive $i$. In the product, that contributes 1 if $i$ is not a part and $x^i$ if $i$ is a part. Any term that contributes to the coefficient of $x^{19}$ (like $x^2\cdot x^7 \cdot x^{10}$) corresponds to a partition of 19 into distinct parts (e.g., $2 + 7 + 10 = 19$).

So it's the coefficient of $x^{19}$ in $\displaystyle \prod_{k=1}^\infty (1+x^k)$, not $\displaystyle \prod_{k=1}^\infty (1-x^k)$. To actually find the coefficient 54, here's a Wolfram Alpha link (you'll need to click "more terms" a few times to have it show you $54x^{19}$): https://www.wolframalpha.com/input?i=series+expansion+of+the+product+from+j%3D1+to+infinity+of+%281%2Bx%5Ej%29