Type that maximize the number of permutations

Question

Given a permutation $\sigma \in S_n$, the type of $\sigma$ is the $n$-uple $(c_1,...,c_n)$ where $c_k$ is the number of cycles of $\sigma$ of lenght $k$. It's easy to prove that the number of permutations $\sigma \in S_n$ of type $(c_1,...,c_n)$ is $$\frac{n!}{1^{c_1}c_1!...n^{c_n}c_n!}$$ The exercise 136 (chapter 1) of Stanley's Combinatorics volume 1 asks to find the type that maximizes the number of permutations of that type. The solution in the book just states the answer $(1,0,...,0,1,0)$ (all zero entries except the first one and the second-last one) that was intuitively clear to me, but doesn't give any justification. How do I formally justify this result?

Answer 1

The quotient $n!/(\cdots)$ is maximized when the denominator $1^{c_1}c_1!\cdots n^{c_n}c_n!$ is minimized.

Since $1c_1+\cdots+nc_n=n$, it would be nice if we could find a lower bound for the product using this sum. Indeed, if $a,b>1$ then $(a-1)(b-1)\ge1\implies ab\ge a+b$ with equality iff $a,b=2$; by induction we have $a_1\cdots a_n\ge a_1+\cdots+a_n$, again saturated only for $2\cdot2=2+2$. Since $k^{c_k}c_k!>1$ for all factors where $c_k>0$, except for when $c_1=1$, we have the start of our cases...

• If $c_1\ne1$:

$$ \prod_{k=1}^n k^{c_k}c_k!=\prod_{c_k>0} k^{c_k}c_k!\ge\sum_{c_k>0}k^{c_k}c_k!\ge\sum_{c_k>0}kc_k=\sum_{k=1}^nkc_k=n. $$

• If $c_1=1$ and $c_k>0$ occurs for more than one other index $k$, then the sum below contains more than one term and $k^{c_k}c_k!=2$ is possible at most once (when $c_2=1$), yielding strictly:

$$ \prod_{k=1}^n k^{c_k}c_k!=\prod_{\substack{c_k>0\\k>1}}k^{c_k}c_k!>\sum_{\substack{c_k>0\\k>1}}k^{c_k}c_k!\ge\sum_{\substack{c_k>0\\k>1}}kc_k=\sum_{k=2}^nkc_k=n-1. $$

• If $c_1=1$ and $c_k>0$ occurs for only one other index $k$, then the product is $k^{c_k}c_k!\ge kc_k=n-1$ with equality only if $c_k=1$, in which case $k=n-1$.