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)$.
$\begingroup$
$\endgroup$
7
-
1$\begingroup$ Just to clarify, you want to maximize the number of permutations of a given cycle structure? $\endgroup$– Stefan GeschkeCommented May 11, 2011 at 9:13
-
3$\begingroup$ Alternatively, you want to know the largest conjugacy class in $\mathfrak S_n$. $\endgroup$– Amritanshu PrasadCommented May 11, 2011 at 10:48
-
3$\begingroup$ Compare mathoverflow.net/questions/2888/… $\endgroup$– Philipp LampeCommented May 11, 2011 at 11:40
-
$\begingroup$ I voted to close as off-topic since I think this is a standard exercise in an undergraduate combinatorics or group theory class. $\endgroup$– Douglas ZareCommented May 11, 2011 at 11:42
-
1$\begingroup$ 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. $\endgroup$– Pietro MajerCommented May 11, 2011 at 12:19
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
$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}$.
answered May 11, 2011 at 10:40