0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is the OEIS sequence A007690 . The sequence entry has some good information. $\endgroup$ – Somos May 15 at 2:41
  • $\begingroup$ 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? $$ $\endgroup$ – Mike Earnest May 15 at 15:54
  • $\begingroup$ 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. $\endgroup$ – E.C. May 15 at 16:18
  • $\begingroup$ @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. $\endgroup$ – Mike Earnest May 15 at 16:53
0
$\begingroup$

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}$$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.