Proving an Upper Bound on the Number of Partitions of $n$ into $m$ Parts

Question

Question

Show that $$ p(n,m)\le\frac{1}{m!}\binom{n+\binom{m+1}{2}-1}{m-1} $$ where $p(n, m)$ denotes the number of partitions of $n$ into exactly $m$ parts.

The above question is from Comtet's Advanced Combinatorics.

My Attempt

I was able to show the inequality $$ p_{d}(n,m)\leq\frac{1}{m!}\binom{n-1}{m-1}\leq p(n,m)\tag{0} $$ where $p_{d}(n,m)$ denotes the number of partitions of $n$ into $m$ distinct parts. I provide a proof of the inequality at the end.

Now write $p_{d}(n,m)=p(n-\binom{m+1}{2}, \leq m)=\sum_{k=0}^m p(n-\binom{m+1}{2}, k)$ but applying the inequality on each of the summands yields a lower bound of $p(n,m)$.

Any help is appreciated.

Proof of Inqequality (0)

Here is a proof of $(0)$. Indeed, consider the map $\varphi\colon C(n,m )\to P(n,m)$ which sends a composition of $n$ into $m$ parts $(x_{1}, \dotsc, x_{m})$ to the partition obtained by arranging the components in descending order. Then $$ p_{d}(n,m)=\frac{1}{m!}c_{d}(n,m)\leq\frac{1}{m!}\binom{n-1}{m-1} $$ since the map $\varphi $ is $m!$ to one on the compositions of $n$ into $m$ distinct parts. and $c_d(n,m)$ denotes the compositions of $n$ into $m$ distinct parts. Similarly, $$ \frac{1}{m!}\binom{n-1}{m-1}=p_{d}(n,m)+\frac{c_{\text{notdist}}(n,m)}{m!}\leq p(n,m) $$ since the map $\varphi$ is less than $m!$ to one on the "not distinct" partitions.

Answer 1

This is part of Chapter 2, exercise 5, on p116 in the edition I have. Alex R., Comtet is not allowing 0 as a part of a partition (i.e., the exercise refers to $P(n,m)$ in his notation). Because this is a step towards an asymptotic result (namely, $P(n,m) \sim \frac{1}{m!} \binom{n-1}{m-1}$ for certain $m$), the inequalities are not as tight as possible.

The derivation uses the conversion to partitions with distinct parts mentioned by Munchhausen (and in Number of partitions contained within Young shape $\lambda$) and a counting argument I've heard called "stars and bars."

\begin{align} p(n,m) & = p_d\!\left(n+\binom{m-1}{2},m\right) \\ & \le p_d\!\left(n+\binom{m}{2},m\right) \\ & = \frac{1}{m!} \; c_d\!\left(n+\binom{m}{2},m\right) \\ & \le \frac{1}{m!} \; \binom{n+\binom{m}{2}+m-1}{m-1} \\ & = \frac{1}{m!} \; \binom{n+\binom{m+1}{2}-1}{m-1}. \end{align}

The first line uses the "trick" of adding $m-1$ to the largest part of the partition, adding $m-2$ to the second largest part, down to adding 1 to the second smallest part in order to guarantee a partition with distinct parts ($Q(n,m)$ in Comtet's notation).

The second line is clearly true, if unmotivated; see below.

The third line, using Foobaz John's notation, comes from realizing that each partition with $m$ distinct parts corresponds to $m!$ compositions with distinct parts.

The fourth line is the counting argument for compositions with $m$ parts: Imagine a row of $n + \binom{m}{2}$ stars. Insert $m-1$ bars anywhere in the row; these are essentially plus signs between the composition parts. Seen another way, put $m-1$ bars in any of $n + \binom{m}{2} + m - 1$ positions and fill the rest with stars, building an $m$-part composition. This line is an inequality because the counting allows for composition parts 0 (such as $\bullet \bullet||\bullet \sim 2+0+1$); by construction we have no 0 parts, so additional compositions are counted.

The fifth line is algebra.

Why use $\binom{m}{2}$ in the second line rather than the exact statement in the first line? I think it's for the algebraic simplification in the fifth line which makes the subsequent asymptotic argument in the exercise a little cleaner.