Fraction $\frac{g_{\mu}}{f_{\lambda}}$ as an Integer

co.combinatoricsenumerative-combinatoricspartitionspermutationsreference-request

Let $\lambda=(\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_{\ell(\lambda)}>0)$ be an integer partition of $n\in\mathbb{N}$; i.e., $\lambda_1+\cdots+\lambda_{\ell(\lambda)}=n$.

One may now associate $f_{\lambda}=\dim(\lambda)=\#SYT(\lambda)$ which is computed by $f_{\lambda}=\frac{n!}{H_{\lambda}}$ where $H_{\lambda}=\prod_{u\in\lambda}h_u$ is the product of the hook-lengths $h_u$ of cells $u$ in the Young diagram of $\lambda$. On the other hand, for the symmetric group $\frak{S}_n$ of permutations on $n$ letters $\{1,2,\dots,n\}$, there is the cycle index formula $g_{\lambda}=\frac{n!}{z_{\lambda}}$ counting the numbers of permutations indexed by cycle-type $\lambda$. If $\lambda$ is expressed in frequency notation as $\lambda=1^{a_1}2^{a_2}\cdots n^{a_n}$ then $z_{\lambda}=1^{a_1}2^{a_2}\cdots n^{a_n}a_1!a_2!\cdots a_n!$ as a product.

Now, consider the two data of multisets (items may be repeated)
$$\mathcal{F}_n=\{f_{\lambda}: \lambda\vdash n\} \qquad \text{and} \qquad
\mathcal{G}_n=\{g_{\lambda}: \lambda\vdash n\}.$$

Observe $\#\mathcal{F}_n=\#\mathcal{G}_n=p(n)$, the number of partitions of $n$.

I would like to ask whether the following is true or not:

QUESTION. For any $f_{\lambda}\in \mathcal{F}_n$, there exists $g_{\mu}\in \mathcal{G}_n$ such that the fraction $\frac{g_{\mu}}{f_{\lambda}}=\frac{H_{\lambda}}{z_{\mu}}$ is actually an integer. We insist the map $\lambda\rightarrow\mu$ to be $1$-to-$1$.

Best Answer

With computer search one finds that the premise is first violated at $n = 19$. The obstruction is as follows: consider $\mu_1 = 1^{19}$, $\mu_2 = 1^{17}2$, $\mu_3 = 1^{16} 3$. We have $g_{\mu_1} = 1$, $g_{\mu_2} = {19 \choose 2} = 9 \cdot 19$, $g_{\mu_3} = 2{19 \choose 3} = 2 \cdot 3 \cdot 17 \cdot 19$. There are only two partitions $\lambda$ such that $f_{\lambda}$ divides any of $g_{\mu_i}$, namely $f_{1^{19}} = f_{19} = 1$. I'm not currently able to present a short proof of the latter fact.

To provide some insight, here are all partitions of $19$ with $f_{\lambda} \leq \max g_{\mu_i}$:

  • $f_{19} = f_{1^{19}} = 1$,
  • $f_{1^{17}2} = f_{1, 18} = 18 = 2 \cdot 3^2$,
  • $f_{1^{16}3} = f_{1^2 17} = 153 = 3^2 \cdot 17$,
  • $f_{1^{15}2^2} = f_{2, 17} = 152 = 2^3 \cdot 19$,
  • $f_{1^{15}4} = f_{1^3 16} = 816 = 2^4 \cdot 3 \cdot 17$,
  • $f_{1^{14}, 2, 3} = f_{1, 2, 16} = 1615 = 5 \cdot 17 \cdot 19$,
  • $f_{1^{13} 2^3} = f_{3, 16} = 798 = 2 \cdot 3 \cdot 7 \cdot 19$.

Next bad value is $n = 25$, with the same $1^n$, $1^{n - 2} 2$, $1^{n - 3}3$ vs $1^n, n$ obstruction. $n = 31$ is the same.

Related Question