Proof of the Stirling Number Inequality, $S(m, n-2) \leq \binom{n}{3}S(m,n)$

Question

I came across the following textbook problem: Prove that

$S(m, n-2) \leq \binom{n}{3}S(m,n)$ for $n \geq 3, m \geq 2n - 3$.

I tried to prove the inequality by induction on $n$ using the fact that, by definition, the Stirling number $S(m, j)$ is given by

$S(m, j) = \frac{1}{j!} \sum_{i=0}^{j-1} (-1)^j \binom{j}{i} (j - i)^m$

Nonetheless, I am unable to complete the inductive step. Is there any other way to prove this inequality? I would appreciate any help on this!

Answer 1

Let $P$ be a partition of $[m]$ into $n-2$ parts. If $$m\ge 2n-3=2(n-2)+1\,,$$ there must be a part with at least $3$ members. Among all such parts let $p$ be the one with the smallest minimum element. Let $j,k$, and $\ell$ be the three smallest elements of $p$, and replace $p$ by $p\setminus\{j,k\}$, $\{j\}$, and $\{k\}$ to get a partition $p'$ of $[m]$ and a $3$-element subset $\big\{p\setminus\{j,k\},\{j\},\{k\}\big\}$ of $[n]$. The map

$$p\mapsto\left\langle\big\{p\setminus\{j,k\},\{j\},\{k\}\big\},p'\right\rangle$$

is an injection from the set $\mathscr{P}$ of partitions of $[m]$ into $n-2$ parts to the set $[n]^3\times\mathscr{P}'$, where $[n]^3$ is the set of $3$-element subset of $[n]$, and $\mathscr{P}'$ is the set of partitions of $[m]$ into $n$ parts. Thus,

$${m\brace{n-2}}=|\mathscr{P}|\le\left|[n]^3\times\mathscr{P}'\right|=\binom{n}3{m\brace n}\,.$$

Answer 2

Here is a combinatorial proof: Let $\mathbb{S}(m,n)$ denote the set of partitions of $[m]=\{1,2,\cdots , m\}$ into $n$ non empty disjoint blocks. Denote, also, $\binom{[n]}{k}$ the set of subsets of $[n]$ of size $k.$ Consider the function $\varphi : \mathbb{S}(m,n)\times \binom{[n]}{3}\longrightarrow \mathbb{S}(m,n-2)$ defined as follows:

let $\pi =\{B_1,\cdots ,B_n\}$ be a partition of $[m]$ into $n$ blocks and let $X=\{x_1,x_2,x_3\}$ $$\varphi ((\pi,X)) =\pi \setminus \{B_{x_1},B_{x_2},B_{x_3}\}\cup \{B_{x_1}\cup B_{x_2}\cup B_{x_3}\},$$ so essentially you are replacing $3$ blocks (indexed with elements in $X$) with their union. Notice that this functions is well-defined and try to show that this function is onto (use pidgeon-hole to see that because $m\geq 2n-3=2(n-2)+1$ then there is, necessarily, at least one block with $3$ elements, so you can split it).

This implies your inequality because if a function is onto then the codomain has no more elements than the domain.