9
$\begingroup$

How can I find the number of partitions of $n$ into exactly $k$ distinct parts, where each part is at most $M$?

The number of partitions $p_k(\leq M,n)$ of $n$ into at most $k$ parts, each of size at most $M$, is given by the generating function: $$ \binom{M+k}{k}_{x} = \prod_{j=1}^{k}\frac{1-x^{M+k-j+1}}{1-x^j}= \sum_{n=0}^{kM} p_{k}(\leq M,n) x^n $$

For the number of the partitions $p_k(\mathcal{D},n)$ of $n$ into at most $k$ parts there is the recurrence relationship: $$ p_{k}(\mathcal{D},n) = p_{k}(\mathcal{D},n-k) + p_{k-1}(\mathcal{D},n) $$

But what, if I want to count only the partitions with distinct parts and restricted number of parts and restricted part size?

Update: Now I know the generating function for the number of distinct restricted partitions $p_k(\leq M, \mathcal{D},n)$ of $n$ into exactly $k$ distinct parts, all at most $M$ is $$ \prod_{j=1}^{M} (1+xq^{j}) = \sum_{k,n=0}^{\infty}p_k(\leq M, \mathcal{D},n)x^{k}q^{n} $$ and there is also a recurrence relation $$ p_k(\leq M, \mathcal{D},n) = p_{k-1}(\leq M-1, \mathcal{D},n-k) + p_k(\leq M-1, \mathcal{D},n-k) $$ How can I prove this? Could you recommend a book, where I could read about this?

$\endgroup$
  • $\begingroup$ Simul-posted to MO, mathoverflow.net/questions/155315/… without notification to either site. $\endgroup$ – Gerry Myerson Jan 21 '14 at 21:43
  • 3
    $\begingroup$ Say you have a partition $\lambda_1>\lambda_1>...>\lambda_k$ of $n$ with $\lambda_1 \le M$. Then $(\lambda_1-k+1) \ge (\lambda_2-k+2) \ge ... \ge \lambda_k$ is a partition of $n - k(k-1)/2$ with k parts each at most M-k+1 but no longer necessarily distinct. Now you can apply one of the previous results. $\endgroup$ – Nate Jan 21 '14 at 21:46
  • $\begingroup$ Very useful paper, though this gives a good approximation to the number of partitions of n into exactly k parts each no larger than N due to Ratsaby (App. Analysis and Discrete M. 2008): doiserbia.nb.rs/img/doi/1452-8630/2008/1452-86300802222R.pdf $\endgroup$ – Alexander Kartun-Giles Jun 18 '16 at 15:43
5
$\begingroup$

In the "Update" (the day after the Question itself was posted), the OP mentions a recursion for counting the partitions of $n$ into $k$ distinct parts, each part at most $M$:

$$ p_k(\leq M, \mathcal{D},n) = p_{k-1}(\leq M-1, \mathcal{D},n-k) + p_k(\leq M-1, \mathcal{D},n-k) $$

and asks "How can I prove this?".

To see this, separate the required partitions on the basis of whether $1$ appears as a summand. If it does, then subtracting $1$ from each summand produces a partition of $n-k$ with exactly $k-1$ distinct parts (since the original summand $1$ disappears), each part at most $M-1$. These partitions are counted by the first term on the right-hand side of the recursion. Otherwise the summand $1$ does not appear, and subtracting $1$ from each part resulting in a partition of $n-k$ with exactly $k$ distinct parts, each part at most $M-1$. These cases are counted by the second term.

Note that a partition of $n$ with $k$ distinct parts exists if and only if $n \ge \binom{k+1}{2}$, because the ascending summands $m_1 + \ldots + m_k = n$ must satisfy $m_i \ge i$. If $n = \binom{k+1}{2}$, then there is just one such partition with $k$ distinct parts, the largest of which is $k$. Repeated application of the recursion will culminate with terms which we can evaluate "by inspection" as either zero or one.

By itself this recursion doesn't seem to give us an especially attractive way of evaluating $p_k(\leq M, \mathcal{D},n)$. Like the recursion for Fibonacci numbers, as a top-down method it suffers from recalculating terms multiple times (giving exponential complexity), so we would be better off working with it as a bottom-up method (giving polynomial complexity).

Better for large parameters is to close the circle with the ideas presented by @NikosM. by showing how the evaluation of $p_k(\leq M, \mathcal{D},n)$ can be reduced to counting restricted partitions without requiring distinct summands.

Prop. Suppose that $n \gt \binom{k+1}{2}$. Then the following are equal:

$(i)$ the number of partitions of $n$ into exactly $k$ distinct parts, each part at most $M$, i.e. $p_k(\leq M, \mathcal{D},n)$

$(ii)$ the number of partitions of $n - \binom{k}{2}$ into exactly $k$ parts, each part at most $M$

$(iii)$ the number of partitions of $n - \binom{k+1}{2}$ into at most $k$ parts, each part at most $M$

Sketch of proof: Once we know the ordered summands of partitions in $(i)$ satisfy $m_i \ge i$, it is easy to visualize their equivalents in $(ii)$ and $(iii)$ by Young tableaux, also called Ferrers diagrams. We remove a "base triangle" of dots corresponding to the first $i$ dots in the $i$th summand (since $m_i \ge i$) to get case $(iii)$, and remove one fewer dot in each summand to preserve exactly $k$ summands in case $(ii)$. These constructions are reversible, and the counts are equal.

Remark 1 If $n \le \binom{k+1}{2}$, $p_k(\leq M, \mathcal{D},n)=1$ if $n=\binom{k+1}{2}$ and $k \le M$ and otherwise $p_k(\leq M, \mathcal{D},n)=0$.

Remark 2 For fixed $k,n$, suppose $M_0 = n - \binom{k}{2} \gt 0$. Then for all $M \ge M_0$, $p_k(\leq M, \mathcal{D},n) = p_k(\leq M_0, \mathcal{D},n)$. That is, further increasing the upper bound $M$ on the size of parts will not yield additional partitions of $n$ with exactly $k$ distinct parts.


Recommended Reading

Andrews, George E. The Theory of Partitions (Cambridge University Press, 1998)

A modern classic for theory of integer partitions, reviewed by Richard Askey in BAMS.

$\endgroup$
0
$\begingroup$

There is an algorithm to count and generate restricted numerical partitions (both in largest part and number of parts) here p. 93 4.8 Numerical Partitions

Define $P(n; k; s)$ to be the set of all partitions of $n$ into $k$ parts with largest part equal to $s$, and let $p(n; k; s) = \left|P(n; > k; s)\right|$. Clearly, in order to have $p(n; k; s) > 0$ we must have at least one part equal to $s$ and at most $k$ parts equal to $s$. Thus $s + k \le n \le ks$.

By classifying the partitions of $P(n; k; s)$ according to the value of the second largest part, call it $j$, we obtain the following recurrence relation, which has no zero terms; it is a positive recurrence relation.

$$p(n; k; s) = \sum^{min(s;nX¡s¡k+2)}_{j=max(1,\frac{n-s}{k-1})}p(n-s,k-1,j)$$

$\endgroup$
  • $\begingroup$ I follow your reasoning, but this does not seem to impose the required condition that parts are distinct. $\endgroup$ – hardmath Jul 26 '15 at 15:30
  • $\begingroup$ hmm yeah i see. Counting partitions is a difficult task, but all methods use the same recursion (i know because i have a lib for combinatorics where various combinatorial objects are generated and counted, including partitions). So it is do-able in algorithmic form, if you want a closed-form solution am not aware of any $\endgroup$ – Nikos M. Jul 26 '15 at 19:04
  • $\begingroup$ PS answer was posted before new update on additional conditon for unique partition parts (so it covers the first two conditions), still a similar recursion can be found fopr distinct parts as well (in algorithmic form, not closed-form solution) $\endgroup$ – Nikos M. Jul 26 '15 at 19:08
  • $\begingroup$ @hardmath, oops seems i missed that part, still the recursion holds for both inital conditions can be extended to cover distinct parts all partition recursions follow similar logic in this sense it should be do-able, although do not have time to elaborate on this further, hope OP will find even this useful for a start $\endgroup$ – Nikos M. Jul 26 '15 at 20:29

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.