Is there a function, equivalent to the partition function, that does not allow duplication? Or, alternatively, for any N, how many partitions would there be- disallowing any that have the same integer appearing more than once.


Sorry, to be more accurate, I'd like to know a function, or even just it's asymptotic complexity, which will produce the partitions of the input, excepting those which have integers that occur more than once. I've only just realized that this is the actual logical equivalent to my problem; I appreciate that I haven't exactly posted much effort into finding it myself. Unless someone comes back and posts a solution relatively quickly, you can expect more from me soon.

  • 1
    $\begingroup$ What do you mean by function? Clearly you can define $f(n)$ to be the desired number. $\endgroup$ – Dennis Gulko Jun 11 '11 at 17:03
  • $\begingroup$ I think he wants a closed formula for the amount of partitions. $\endgroup$ – Listing Jun 11 '11 at 17:05
  • $\begingroup$ Sorry- I'd like to know f, as opposed to just define it. $\endgroup$ – DeadMG Jun 11 '11 at 17:08
  • 3
    $\begingroup$ What does it mean to know a function? (Not a rhetorical question. This is really not an obvious notion and there are various practical things one could mean by this.) $\endgroup$ – Qiaochu Yuan Jun 11 '11 at 17:53
  • $\begingroup$ @DeaDMG: The problem has been much studied. There are asymptotic estimates for the number of such partitions, dating back to Hardy and Littlewood, and I had posted a short answer with a link to references. I deleted the answer when your edit seemed to show that you want something else. $\endgroup$ – André Nicolas Jun 11 '11 at 18:16

The number of partitions of $n$ into distinct parts is OEIS A000009, which gives a pile of references. It is sometimes called the partition function $Q$ (in contrast to $P$ for all partitions). As Gerry Myerson has said, it generating function is $\prod_{m\ge 1} (1+x^m)$.

As for actually generating the partitions, you could use something already prepared such as the package partitions in R which for example gives for partitions of $12$

> library(partitions)
> Q(12)
[1] 15
> diffparts(12)
[1,] 12 11 10 9 9 8 8 7 7 7 6 6 6 5 5
[2,]  0  1  2 3 2 4 3 5 4 3 5 4 3 4 4
[3,]  0  0  0 0 1 0 1 0 1 2 1 2 2 3 2
[4,]  0  0  0 0 0 0 0 0 0 0 0 0 1 0 1

If you want to do this yourself, I find one way (if you can generate ordinary partitions) is to note that the partitions of $n$ into $k$ different positive parts are equivalent to the partitions of $n-\frac{k(k-1)}{2}$ into $k$ positive parts (possibly equal), just by adding $k-1, k-2,\ldots,1,0$ respectively to each part. For example to find partitions of $12$ into $4$ different parts, look at partitions of $6$ into $4$ parts: there are two, namely $3+1+1+1$ and $2+2+1+1$; now add $3+2+1+0$ to these term by term to get $6+3+2+1$ and $5+4+2+1$.


I believe that it is quite instructive to derive the above generating function using species, in spite of it being very simple, as it showcases some standard tricks in the manipulation of cycle indices.

Observe that the species $\mathcal{Q}$ that represents partitions with unique constitutents is simply $$\mathcal{Q} = \mathfrak{P}\left(\sum_{k\ge 1} \mathcal{Z}^k\right).$$

Now recall the recurrence by Lovasz for the cycle index $Z(P_n)$ of the set operator $\mathfrak{P}_{=n}$ on $n$ slots, which is $$Z(P_n) = \frac{1}{n} \sum_{l=1}^n (-1)^{l-1} a_l Z(P_{n-l}) \quad\text{where}\quad Z(P_0) = 1.$$

Let $$F_n(z) = Z(P_n)\left(\frac{z}{1-z}\right)$$ where the second parenthesis on the right represents cycle index substitution and introduce the generating function $$G(y) = \sum_{n\ge 0} F_n(z) y^n,$$ so that we are interested in $G(1).$

The recurrence yields $$n Z(P_n) = \sum_{l=1}^n (-1)^{l-1} a_l Z(P_{n-l}).$$

Substitute for $a_l$, multiply by $y^{n-1}$ and sum over $n\ge 1$ to get $$G'(y) = \sum_{n\ge 1} y^{n-1} \sum_{l=1}^n (-1)^{l-1} \frac{z^l}{1-z^l} F_{n-l}(z) \\= \sum_{l\ge 1} (-1)^{l-1} \frac{z^l}{1-z^l} \sum_{n\ge l} y^{n-1} F_{n-l}(z).$$ This is $$\sum_{l\ge 1} (-1)^{l-1} \frac{z^l}{1-z^l} y^{l-1} \sum_{n\ge l} y^{n-l} F_{n-l}(z) = G(y) \sum_{l\ge 1} (-1)^{l-1} \frac{z^l}{1-z^l} y^{l-1}.$$ Therefore $$(\log G(y))' = \sum_{l\ge 1} (-1)^{l-1} \frac{z^l}{1-z^l} y^{l-1}.$$ Integrating we have $$\log G(y) = C + \sum_{l\ge 1} (-1)^{l-1} \frac{z^l}{1-z^l} \frac{y^l}{l} = C + \sum_{k\ge 1} \sum_{l\ge 1} (-1)^{l-1} z^{kl} \frac{y^l}{l} \\= C - \sum_{k\ge 1} \log \frac{1}{1+yz^k}.$$ The conclusion is that $$G(y) = e^C \exp\left( - \sum_{k\ge 1} \log \frac{1}{1+yz^k} \right) = e^C \exp\left( \sum_{k\ge 1} \log(1+yz^k) \right) \\= e^C \prod_{k\ge 1} (1+yz^k).$$

Now $G(0)=1$ and hence the constant obeys $e^C=1$, for a final answer of $$G(y) = \prod_{k\ge 1} (1+yz^k).$$

In particular the generating function of partitions into unique parts is $$G(1) = \prod_{k\ge 1} (1+z^k),$$ precisely as it ought to be.


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.