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.

  • $\begingroup$ Could you clarify if order matters in these partitions, and whether 0 is allowed? $\endgroup$ – Alex R. Jun 18 '18 at 23:34
  • 1
    $\begingroup$ Consider the Ferrers diagram of a partition of $n$ into exactly $m$ parts, each of which are distinct. Provided $n\geq {m\choose 2}$, this diagram will have a triangle with side length $m-1$ in the corner. If we remove this triangle, we get a partition of $n-{m\choose 2}$ into exactly $m$ parts (no longer distinct). Furthermore, this process is easily reversible, so $p(n,m)=p_d(n+{m\choose 2},m)$. Hopefully this helps $\endgroup$ – munchhausen Jun 19 '18 at 6:48

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.

| cite | improve this answer | |

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.