Skip to main content
fixed typo
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

$c_1=c_{n-1}=1$, other $c_i$ are equal to 0. Indeed, the number of permutations with class $C$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}$.

$c_1=c_{n-1}=1$, other $c_i$ are equal to 0. Indeed, the number of permutations with class $C$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}$.

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

Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

$c_1=c_{n-1}=1$, other $c_i$ are equal to 0. Indeed, the number of permutations with class $C$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}$.