2
$\begingroup$

This problem is the same as number of ways to partition n into exactly m parts.

The recurrence given in Wikipedia has

p(n,k) = the number of partitions of n using only natural numbers ≥ k

How to find no of partitions of n which has exactly k non-zero parts? Is there a recurrence relation to solve this?

$\endgroup$
15
  • 2
    $\begingroup$ Here and here are relevant entries in the Online Encyclopedia of Integer Sequences. Recurrence relations included. $\endgroup$
    – Peter Shor
    Aug 4, 2013 at 14:25
  • 5
    $\begingroup$ This question has nothing to do with computer science and belongs in math.stackexchange. $\endgroup$ Aug 4, 2013 at 22:00
  • 3
    $\begingroup$ @Yuval: ... where it will be closed as a duplicate. $\endgroup$
    – Peter Shor
    Aug 4, 2013 at 22:50
  • 2
    $\begingroup$ @YuvalFilmus Combinatorics are regularly used in algorithm analysis. If we close this one as offtopic, we'd have to close all the asymptotics questions around by the same token. $\endgroup$
    – Raphael
    Aug 11, 2013 at 11:53
  • 2
    $\begingroup$ These comments should be on Computer Science Meta not here. $\endgroup$
    – Kaveh
    Aug 12, 2013 at 23:48

1 Answer 1

2
$\begingroup$

The number of partitions of $n$ with exactly $k$ parts is the coefficient of $x^n y^k$ in the generating series $$ \prod_{l=1}^\infty \frac{1}{1-x^ly}. $$ Asymptotically, this is probably $\Theta_k(n^{k-1})$ (i.e. the constant depends on $k$).

The number of partitions of $n$ in which each part is at least $k$ is $$ \prod_{l=k}^\infty \frac{1}{1-x^l}. $$ Asymptotically, my guess is that it's $\Theta_k(p(n))$, where $p(n)$ is the number of all partitions of $n$.

We can write a recurrence relation for $p(n,k)$: $p(0,k) = 1$ and for $n > 0$, $$ p(n,k) = \sum_{t \leq \lfloor n/k \rfloor} p(n-kt,k+1). $$

$\endgroup$

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