1
$\begingroup$

I need to count the possible partitions where sum of it's members is X, but every set has N items.

For example X=5 and N=4:

{ 1,1,1,2 } 

X=5, N=3:

{ 1,2,2 } { 1,1,3 } 

X=5, N=2:

{1,4} {2,3} 

But I have large number of X and N. So I'm looking for best method.

  • 0
    see Sloane's sequence [A0082484](http://oeis.org/A008284).2012-06-22

2 Answers 2

3

To elaborate a little on joriki's and A. De Luca's helpful comments, there is a bijection between what you are seeking (partitions of $X$ into $N$ parts) and partitions of $X - N$ into at most $N$ parts. To see this, you can visualize your partition $\lambda_1 \geq \cdots \lambda_N \geq 1$ as a triangular array of boxes, with $\lambda_1$ boxes in the first row, $\lambda_2$ boxes in the second row, etc. (with the whole diagram left-justified). To say that it is a partition of $X$ means that $\lambda_1 + \cdots + \lambda_N = X$, or equivalently that there are $X$ boxes in the diagram. To say that it has exactly $N$ parts means that the diagram has exactly $N$ rows. You can always remove the first column and that will leave you with $X - N$ boxes in $\leq N$ rows, i.e. a partition of $X - N$ with at most $N$ rows.

For example, if you want to enumerate the partitions of $9$ into $3$ parts, you would consider all partitions of $6$ with at most $3$ parts. This gives $6,51,42,411,33,321,222$ (assuming I haven't missed any), so the partitions of $9$ into exactly $3$ parts, obtained by adding $1$ to each part including "$0$ parts" if there are any, are $711,621,531,522,441,432,333$.

Note that if $N \geq X/2$, then any partition of $X - N$ will have $\leq N$ parts, so in that case the number of partitions of $X$ into $N$ parts will be exactly the number of partitions of $X - N$.

2

Adding a bit to the contributions by joriki and Michael Joyce. Going to the dual partitions implies that the number of paritions into at most $N$ parts equals the number of partitions into parts of size at most $N$ (just take the "transposes" of those triangular arrays of boxes). The latter, call them $P_N(X)$, are enumerated by the generating function $ G_N(T):=P_N(0)+P_N(1)T+P_N(2)T^2+\cdots=\sum_{X=0}^\infty P_N(X)T^X =\prod_{j=1}^N\frac1{1-T^j}. $ See Hardy & Wright for an explanation of this and several other generating functions related to partitions.

The OP asks for the number of partitions into exactly $N$ parts. As explained by Michael Joyce that is given by $P_N(X-N)$.

One way of using this generating function in computing the function $P_N(X)$ is the following. Compute the product giving the reciprocal of the generating function: $ Q(T)=\prod_{j=1}^N(1-T^j)=a_0+\sum_{k>0}a_kT^k, $ where the coefficients $a_k$ are integers. As this is the reciprocal of the generating function it gives a recurrence relation $ P_N(X)=\sum_{k=1}^{\min{X,\deg Q(T)}}(-a_k)P_N(X-k). $

For example, when $N=2$, we have $Q(T)=1-T-T^2+T^3$, so the recurrence relation reads $ P_2(X)=P_2(X-1)+P_2(X-2)-P_2(X-3). $