4
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ Just to clarify, you want to maximize the number of permutations of a given cycle structure? $\endgroup$ – Stefan Geschke May 11 '11 at 9:13
  • 3
    $\begingroup$ Alternatively, you want to know the largest conjugacy class in $\mathfrak S_n$. $\endgroup$ – Amritanshu Prasad May 11 '11 at 10:48
  • 3
    $\begingroup$ Compare mathoverflow.net/questions/2888/… $\endgroup$ – Philipp Lampe May 11 '11 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 Zare May 11 '11 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 Majer May 11 '11 at 12:19
12
$\begingroup$

$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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.