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.

  • $\begingroup$ 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$. $\endgroup$ – 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

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – no_chi Feb 20 at 2:43
  • $\begingroup$ 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$ $\endgroup$ – Henry Feb 20 at 9:02
  • $\begingroup$ 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$.) $\endgroup$ – no_chi Feb 20 at 9:16

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.