5
$\begingroup$

Asymptotic formula for all the partitions of a number is given by

$p(n) \sim \frac{1}{4n\sqrt{3}} e^{\pi \sqrt{\frac{2n}{3}}}$

Only fraction of those will be $k$-partitions. What is asymptotic formula for $k$-partitions of a number?

$p(n,k) \sim ?$

  • 1
    I think it will be something bell shaped.$\sim e^{-(\pi x)^2}$ ?2011-06-18

1 Answers 1

5

The growth rate is $\Theta(n^{k-1})$. The total number of $k$-combinations (partitions where order matters) is $\binom{n-1}{k-1}$. Therefore $ \frac{1}{k!} \binom{n-1}{k-1} \leq p(n,k) \leq \binom{n-1}{k-1}. $

It's also easy to obtain a generating series by considering the conjugate partitions: $ P_k = \frac{1}{1-x} \cdot \frac{1}{1-x^2} \cdots \frac{1}{1-x^k}. $ The root with highest multiplicity is $1$, with multiplicity $k$. Partial fraction decomposition gives $ P_k = \frac{1}{k!(1-x)^k} + \cdots. $ The coefficient of $x^n$ in $(1-x)^{-k}$ is $\binom{n+k-1}{k-1}$. Therefore we have $p(n,k) = \frac{1}{k!} \binom{n+k-1}{k-1} + O(n^{k-2}) = \frac{n^{k-1}}{k!(k-1)!} + O(n^{k-2}). $