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

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.

• The ratio is certainly bounded above by $k!$, since the map (from the set of compositions to the set of partitions) given by sorting each composition is at most $k!$-to-$1$. – Greg Martin Feb 20 at 2:21

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

• Thanks for the reply. $k!$ would indeed be an upper bound for the ratio. I edited the question since I probably worded it poorly the first time. – no_chi Feb 20 at 2:43
• Perhaps I do not understand your edited question but $c(n,k)$ does not look like a constant to me, as it varies with $n$ – Henry Feb 20 at 9:02
• I want to establish that $p_k(n) \leq \binom{n-1}{k-1}$ by showing that $\dfrac{\binom{n-1}{k-1}}{p_k(n)}\geq c(n,k)\geq 1$. (And eventually, compute for savings in operations when using only $p_k(n)$ elements as opposed to $\binom{n-1}{k-1}$.) $c(n,k)$ need not be a constant since it may vary with $n$ and $k$.) – no_chi Feb 20 at 9:16