7
$\begingroup$

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.

Edit:

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
    What do you mean by function? Clearly you can define $f(n)$ to be the desired number.2011-06-11
  • 0
    I think he wants a closed formula for the amount of partitions.2011-06-11
  • 0
    Sorry- I'd like to *know* `f`, as opposed to just define it.2011-06-11
  • 3
    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.)2011-06-11
  • 0
    @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.2011-06-11
  • 0
    The partitions that you want to count are usually referred to as partitions with distinct parts. Their number can be shown to be equal to the number of partitions with odd parts.2011-06-11
  • 0
    @DeadMG: Are you looking for an *algorithm* for producing these partitions? Of course, producing *all* partitions and then discarding the "bad" ones would be very inefficient. If a good algorithm is what you are looking for, then yes, there are good algorithms for producing all the partitions of $n$ into distinct parts.2011-06-11
  • 0
    $\sum f(n)x^n=\prod(1+x^n)$2011-06-11
  • 0
    @user6312: I can probably write it myself. I was going to accept your answer, but by the time I finished reading it and the links, you deleted it.2011-06-11
  • 0
    @DeadMG: There is a pretty big literature on partition generating algorithms, people have thought of awfully clever tricks. But if your application is not terribly time sensitive, it's not too hard. Partitions of $n$ into odd parts are easier to program, can't reach dead end, then there is a not hard way to get to partitions into distinct parts of $n$ from there. But I am sure there is already plenty of code out there. Mathematica may have the function. I still don't know whether you want a program or asymptotic information. In either case, do consider posting an answer yourself.2011-06-11
  • 0
    @user6312: Sorry if I wasn't clear- either would have been a perfectly acceptable answer.2011-06-12

2 Answers 2

1

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

0

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.