# a simple combinatorial problems

what sequence $C=(c_1,\cdots,c_n)\in \mathbb{N}^n$ with $\sum ic_i=n$ maximizes the number of $\omega\in\mathfrak{S}_n$ of type $C$? For instance,when $n=4$ the maximizing sequence is $(1,0,1,0)$.

• Just to clarify, you want to maximize the number of permutations of a given cycle structure? May 11 '11 at 9:13
• Alternatively, you want to know the largest conjugacy class in $\mathfrak S_n$. May 11 '11 at 10:48
• May 11 '11 at 11:40
• I voted to close as off-topic since I think this is a standard exercise in an undergraduate combinatorics or group theory class. May 11 '11 at 11:42
• On a side note: when posting a question, please use a more meaningful title. Just a few words that briefly tell the subject of the question. May 11 '11 at 12:19

$c_1=c_{n-1}=1$, other $c_i$ are equal to 0. Indeed, the number of permutations with class $C$ equals $$\frac{n!}{\prod i^{c_i} c_i!},$$ so we need to minimize $\prod i^{c_i} c_i!$. Let's prove that such product exceeds $(n-1)$ unless $c_1=c_{n-1}=1$. It is easy: $i^{c}c!\geq ic$, so the product is not less then the product of non-zero terms in the sequence $c_1,2c_2,\dots,nc_n$, which sums up to $n$. If $a$, $b$ are integers, $a\geq 2$, $b\geq 3$ then $ab> a+b$, repeating this inequality we get $\prod_{i\geq 2, c_i> 0} ic_i\geq 2c_2+\dots+nc_n=n-c_1$, so our product is at least $n$ for $c_1=0$ and at least $c_1(n-c_1)$ if $c_1>0$. If $c_1=n$, then the product equals $n!$, which is too much, in other cases $c_1(n-c_1)\geq n-1$ and all inequalities become equalities iff $c_1=1=c_{n-1}$.