TAOCP 7.2.1.4 Exercise 33
Let $S(n,m)$ denote the number of set partitions of ${1,\dots,n}$ into $m$ parts, so $S(n,m)=\left|\begin{matrix} n \ m \end{matrix}\right|$ in Knuth’s notation.
Section 7.2.1.4: Generating All Partitions
Exercise 33. [HM20] [HM20] Use the fact that there are exactly n−1 m−1 compositions of n into m parts, Eq. 7.2.1.3–(9), to prove a lower bound on n m . Then set m = ⌊√n ⌋to obtain an ele- mentary lower bound on p(n).
7.2.1.4 GENERATING ALL PARTITIONS 411
Verified: no
Solve time: 16m37s
Solution
Let $S(n,m)$ denote the number of set partitions of ${1,\dots,n}$ into $m$ parts, so $S(n,m)=\left|\begin{matrix} n \ m \end{matrix}\right|$ in Knuth’s notation. Let $C(n,m)$ denote the number of compositions of $n$ into $m$ positive parts, so $C(n,m)=\binom{n-1}{m-1}$ by Eq. 7.2.1.3–(9).
For a composition $(a_1,\dots,a_m)$ of $n$, define a partition of ${1,\dots,n}$ by splitting the interval ${1,\dots,n}$ into consecutive blocks
$$ B_1={1,\dots,a_1},\quad B_2={a_1+1,\dots,a_1+a_2},\ \dots,\ B_m. $$
Each $B_i$ is nonempty, the blocks are disjoint, and their union is ${1,\dots,n}$, hence this construction produces a set partition into $m$ parts.
Distinct compositions yield distinct block structures because the block sizes are read off uniquely from the partition: the first block has size $a_1$, the second has size $a_2$, and so on. Hence the mapping from compositions to set partitions is injective. Therefore
$$ S(n,m) \ge C(n,m) = \binom{n-1}{m-1}. $$
Since every partition of $n$ into $m$ parts is a partition of $n$, it follows that
$$ p(n) \ge S(n,m) \ge \binom{n-1}{m-1}. $$
To estimate the binomial coefficient, write
$$ \binom{n-1}{m-1} = \prod_{j=0}^{m-2} \frac{n-1-j}{m-1-j}. $$
For each factor, the numerator satisfies $n-1-j \ge n-m+1$, and the denominator satisfies $m-1-j \le m-1$. Hence every factor is at least $\frac{n-m+1}{m-1}$, giving
$$ \binom{n-1}{m-1} \ge \left(\frac{n-m+1}{m-1}\right)^{m-1}. $$
Set $m=\lfloor \sqrt{n}\rfloor$. Then $m-1 \le \sqrt{n}$ and $n-m+1 \ge n-\sqrt{n}$. Substituting into the previous inequality yields
$$ p(n) \ge \left(\frac{n-\sqrt{n}}{\sqrt{n}}\right)^{\lfloor \sqrt{n}\rfloor-1}. $$
Since $n-\sqrt{n} \ge \frac{n}{2}$ for all $n \ge 4$, and $\lfloor \sqrt{n}\rfloor-1 \ge \frac{\sqrt{n}}{2}$ for all sufficiently large $n$, it follows that for all sufficiently large $n$,
$$ p(n) \ge \left(\frac{\sqrt{n}}{2}\right)^{\sqrt{n}/2}. $$
This completes the proof. ∎