Ratio between number of compositions and partitions of an integer $n$ into $k$ parts

149 Views Asked by At

Let $p_k(n)$ denote the number of partitions of $n$ into exactly $k$ parts. It is known that $p_k(n)$ satisfies the recurrence

$p_k(n) = p_{k-1}(n-1) + p_k(n-k)$,

where $p_k(n)=0$ for $k>n$, $p_n(n)=1$, and $p_1(n)=1$. It is also known that there are $\binom{n-1}{k-1}$ compositions of $n$ into $k$ parts. Clearly, $p_k(n) \leq \binom{n-1}{k-1}$. Let $c(n,k)>0$ be a positive constant such that $c(n,k)\cdot p_k(n) \leq \binom{n-1}{k-1}$.

What are known upper bounds for the value of $c(n,k)$? I'm looking for a tight upper bound such that $c(n,k)\cdot p_k(n)$ does not exceed $\binom{n-1}{k-1}$.

I have read about upper bounds for $p_k(n)$. However, some of these are greater than $\binom{n-1}{k-1}$, which is not desirable.

EDIT: early replies of $k!$ led me to edit this question.

1

There are 1 best solutions below

3
On

The upper bound for the ratio is $k!$, which is approached as $n$ increases without limit.

For example:

  • $p_5(10000)= 3475694791250$
  • ${9999 \choose 4}=416250145812501$
  • making the ratio about $119.76$
  • compared with $5!=120$

$k!$ is a an upper bound because you can order the $k$ parts of the partition in no more than $k!$ different ways to make different compositions; exactly $k!$ ways if all the parts are distinct but fewer if some are equal.

For large enough $n$ given $k$, the proportion of partitions with equal parts can be arbitrarily small. See this by considering $q_k(n)$ as the number of partitions of $n$ into $k$ distinct positive parts; then $q_k(n)= p_k\left(n-\frac{k(k-1)}{2}\right)$ so $\frac{q_k(n)}{p_k(n)} \to 1$ as $n$ increases