# Number of Partitions of 𝑛 No Part Appears Exactly Once

So I am having a little trouble here. The question is

"Let $$r_n$$ be the Number of Partitions of $$n$$ No Part Appears Exactly Once. Find the generating function."

I realize there is already an answer here, giving the generating function. But I don't understand how this person got the generating function. The answer can be found:

Number of Partitions of $n$ No Part Appears Exactly Once Equals to $n$ Partitioned into 0,2 ,3 or 4 (Mod 6 )

But, it is somewhat asserted without showing this. I also am having some trouble finding some resources online as well. So, usually I would like to find some type of recurrence but I don't think that would be efficient in this case. So I am a little confused. Furthermore, this isn't a homework question. This is an old qual question I found.

• This is the OEIS sequence A007690 . The sequence entry has some good information. – Somos May 15 at 2:41
• Do you understand why the generating function for $p_n$, the number of partitions of $n$ (with no restrictions), is $$(1+q+q^2+\dots)(1+q^2+q^4+\dots)(1+q^3+q^6+\dots)\dots?$$ – Mike Earnest May 15 at 15:54
• Hey, Mike I am a little sketchy about this. After some work, and a little bit of googling, I found that specific generating you mentioned. I think that's why I am having trouble. I don't quite understand why that's the generating function. I mean I have thought it about throughout the night and I don't get it yet. – E.C. May 15 at 16:18
• @E.C. When expanding out that product, you choose one term from each factor. The choice of term from $(1+q+q^2+\dots)$ determines the number of parts equal to $1$ in the corresponding partition; for example, choosing $q^7$ means there are $7$ parts equal to $1$. Similarly, the summand in $(1+q^2+q^4+\dots)$ determines the number of parts equal to $2$, etc. For some more detail, see this answer. – Mike Earnest May 15 at 16:53

I realize there is already an answer here, giving the generating function. But I don't understand how this person got the generating function.

It might help to add some variables to the generating function:

$$((z_1x)^0 + (z_1x)^2 + (z_1x)^3 + \cdots) ((z_2x^2)^0 + (z_2x^2)^2 + (z_2x^2)^3 + \cdots) ((z_3x^3)^0 + (z_3x^3)^2 + (z_3x^3)^3 + \cdots) \cdots \\ = (1 + (z_1x)^2 + (z_1x)^3 + \cdots) (1 + (z_2x^2)^2 + (z_2x^2)^3 + \cdots) (1 + (z_3x^3)^2 + (z_3x^3)^3 + \cdots) \cdots$$

So, for example, we have a term $$(z_1x)^3 (z_3x^3)^2 = z_1{}^3 z_3{}^2 x^9$$ corresponding to the partition $$1 + 1 + 1 + 3 + 3 = 9$$.

Now set all of the $$z_i$$ to $$1$$ to get the univariate generating function.

Then we can express it more elegantly using $$\prod$$ notation and the well-known expression for a geometric sum: $$\begin{eqnarray} \prod_{i=1}^\infty (1 + (x^i)^2 + (x^i)^3 + \cdots) &=& \prod_{i=1}^\infty \left(1 + (x^i)^2 \frac{1}{1 - x^i}\right) \\ &=& \prod_{i=1}^\infty \left(1 + \frac{x^{2i}}{1 - x^i}\right) \\ &=& \prod_{i=1}^\infty \frac{1 - x^i + x^{2i}}{1 - x^i} \\ &=& \prod_{i=1}^\infty \frac{(1 - x^i + x^{2i})(1+x^i)}{(1 - x^i)(1+x^i)} \\ &=& \prod_{i=1}^\infty \frac{1 + x^{3i}}{1 - x^{2i}} \\ \end{eqnarray}$$

So, usually I would like to find some type of recurrence but I don't think that would be efficient in this case.

Quite a lot of partition-related sequences have nice recurrences, essentially all due to Euler's pentagonal theorem (and its generalisation, Jacobi's triple product).

Euler's theorem is $$\prod_{n=1}^\infty (1 - x^n) = 1 + \sum_{k=1}^\infty (-1)^k x^{k(3k \pm 1)/2}$$

This is useful because the partition numbers $$P(n)$$ have g.f $$\prod_{n=1}^\infty \frac{1}{1 - x^n}$$, or in other words $$\frac{1}{\sum_n P(n) x^n} = 1 + \sum_{k=1}^\infty (-1)^k x^{k(3k \pm 1)/2}$$ which rearranges to $$\sum_n P(n) x^n = 1 - \left(\sum_n P(n) x^n\right) \left(\sum_{k=1}^\infty (-1)^k x^{k(3k \pm 1)/2}\right)$$ and gives rise to the famous recurrence $$P(n) = P(n-1) + P(n-2) - P(n-5) - P(n-7) + \cdots$$

Now, partitions into distinct parts, $$Q(n)$$, have g.f. $$\prod_{n=1}^\infty (1 + x^n)$$ and various recurrences: $$\begin{eqnarray} Q(n) &=& (-1)^j \left[j \in \mathbb{N}, n = \frac{j(3j\pm 1)}{2}\right] - 2 \sum_{k=1}^{\lfloor \sqrt n \rfloor} (-1)^k Q(n - k^2) \\ &=& P(n) + \sum_{k=1}^\infty (-1)^k P(n - k(3k \pm 1)) \\ &=& (-1)^j [j \in \mathbb{N}, n = j(3j\pm1)] - \sum_{k=1}^\infty (-1)^k Q\left(n - \frac{k(3k \pm 1)}{2} \right) \end{eqnarray}$$ where $$[\textrm{expr}]$$ is an Iverson bracket, evaluating to $$1$$ if the expression is true and $$0$$ otherwise. The first two recurrences are in OEIS; the third I derived, but is probably not original.

The point of bringing up $$Q$$ is that our generating function of interest is a product of an inflated version of $$Q$$'s generating function and an inflated version of $$P$$'s generating function. I'm going to call it $$A$$ for "At least two". Then $$\begin{eqnarray} \sum_{n=0}^\infty A(n) x^n &=& \prod_{i=1}^\infty \frac{1 + x^{3i}}{1 - x^{2i}} \\ \left(\sum_{n=0}^\infty A(n) x^n\right)\left(\prod_{i=1}^\infty (1 - x^{2i})\right) &=& \prod_{i=1}^\infty (1 + x^{3i}) \\ \left(\sum_{n=0}^\infty A(n) x^n\right)\left(1 + \sum_{k=1}^\infty (-1)^k x^{k(3k \pm 1)}\right) &=& \sum_{k=0}^\infty Q(k)x^{3k} \\ \sum_{n=0}^\infty A(n) x^n &=& \sum_{k=0}^\infty Q(k)x^{3k} - \left(\sum_{j=0}^\infty A(j) x^j\right)\left(\sum_{k=1}^\infty (-1)^k x^{k(3k \pm 1)}\right) \\ A(n) &=& Q(\tfrac{n}{3}) [\tfrac{n}{3} \in \mathbb{N}] - \sum_{k=1}^\infty (-1)^k A(n - k(3k \pm 1)) \end{eqnarray}$$