Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
What you're looking for are partitions, not sets. (A set can't contain the same object twice.) Specifically, you're looking for the number of partitions of $X$ into $N$ parts. –  joriki Jun 22 '12 at 16:27
    
see Sloane's sequence A0082484. –  A. De Luca Jun 22 '12 at 16:37
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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