On Applications of Murnaghan Nakayama Rule

Question

This question is crossposted at math.stackexchange here and may be beyond the usual scope of the site. The question is located below. In short, I am looking for an accessible explanation of the Murnaghan Nakayama rule in relation to the following problem. Pardon the long setup.

Let $Y$ be a standard Young tableau of shape $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_n)$. At the risk of being pedantic, standard here means $\lambda_1\geq\lambda_2\geq \ldots \geq \lambda_n$ and the entries are strictly increasing rightward along rows and downard along columns (with each number from $1$ to $\left|\lambda\right|$ occuring only once). Let $f_\lambda$ denote the number of standard Young tableaux of shape $\lambda$. It is well known that $f_\lambda$ can be calculated via the Hook formula:

$$f_\lambda=\frac{|\lambda|!}{\prod_{i,j}h(i,j)}.$$

Now suppose I remove some boxes on the outer edge of the shape (i'll call this a pattern from now on), giving a new shape $\delta_i$ (I'll explain the $i$ in a moment). Here's an example: let $\lambda$ be the triangular shape $(n-1,n-2,\ldots,1)$. Now I want to remove three adjacent boxes in an "L" shape:

Here I've indexed the location of the left box as $i$ which gives the $x$ coordinate of the box ($i=3$ in this example). To repeat, I'm calling the new shape $\delta_i$, and one easily finds $f_{\delta_i}/f_\lambda$ as the ratio of the particular hooks that change. I'm interested in the following. In the above example, I removed three adjacent boxes at location $i$. I want to evaluate sums of the form:

$$\sum_{i=1}^{n-2}\frac{f_{\delta_i}}{f_\lambda}$$.

In full generality, I am interested in removing any pattern of boxes indexed by $i$ (the sum's range changes appropriately depending on the pattern). Going along with my example, one can show that

$$f_{\delta_i}/f_\lambda=\frac{1}{3N(N-1)(N-2)}a_ia_{n-i-1},$$

where $N:=\binom{n}{2}$ and $a_i:=\frac{(2i+1)!!}{(2i-2)!!}$. One can then evaluate the sum using relatively straightforward generating functions for $a_i$, giving a tidy answer of $\frac{1}{2(N-2)}$.

Question: I have heard that calculating $\sum\limits_{i=1}^{n-2}\frac{f_{\delta_i}}{f_\lambda}$ can be done via the Murnaghan Nakayama rule. In particular, I've been told my $L$ example gives $-\frac{\chi^{\lambda}(\pi)}{\chi^\lambda(\mbox{id})}$ where $\pi$ is a 3-cycle. Can someone provide an accessible reference for this rule in the context above? I am not an expert in representation theory and the usual references I've seen (Enumerative Combinatorics, Vol II by Stanley) are somewhat beyond me at the moment (and in much greater generality). In short, I am looking for an accessible explanation of the Murnaghan Nakayama rule for these types of questions.

Answer 1

For a very nice bijective proof of the Murnaghan-Nakayama rule I recommend Section 3.3 of Nick Loehr's article Abacus proofs of Schur function identities, SIAM J. Disc. Math. 24 (2010) 1356-1370. Chapter 11 of Loehr's recent textbook Bijective combinatorics gives an expanded version of his article with minimal prerequisites.

To explain the connection: the Murnaghan-Nakayama rule states that if $\lambda$ is a partition of $m$, $\pi$ is a $k$-cycle and $\sigma$ is a permutation of the remaining $m-k$ points then

$$\chi^\lambda(\pi \sigma) = \sum (-1)^{\ell(\lambda/\mu)} \chi^\mu(\sigma) $$

where the sum is over all partitions $\mu$ obtained from $\lambda$ by removing a $k$-hook from the border of $\lambda$, and $\ell(\lambda/\mu)$ is leg-length of the hook (i.e. the number of rows of the Young diagram occupied by the hook, minus one). In particular, if $\lambda = (n-1,n-2,\ldots,1)$, $\sigma = 1$ and $\pi$ is a $3$-cycle, then we get

$$\chi^{(n-1,\ldots,1)}(\pi) = -\sum \chi^{\delta_i}(1) $$

since every $3$-hooks that can be removed from $(n-1, \ldots, 1)$ is an $L$-shape of leg-length $1$. Now divide by $\chi^{(n-1,\ldots,1)}(id)$ and use the hook formula to get the sum in the question.

For the intended application we only need the Murnaghan-Nakayama rule for cycles. However my feeling is that any proof of the rule for cycles will do almost all the work needed for the general version. For instance, stated using symmetric polynomials, the Murnaghan-Nakayama rule for cycles is $s_\mu p_k = \sum_\lambda (-1)^{\ell(\lambda/\mu)} s_\lambda$, where the sum is over all partitions $\lambda$ obtained from $\mu$ by adding a $k$-hook. Given this, the full result follows in a few lines by taking $\mu = \varnothing$ and repeatedly multiplying by power-sum symmetric polynomials.

There is however an alternative route to the final answer that might be of interest, using explicit formulae for the characters of symmetric groups on cycles. These can be deduced from the Frobenius formula for character values: see 4.10 and Exercise 4.15 of Fulton & Harris, Representation theory: a first course for the method. The relevant formula for $3$-cycles is (5.2) in R. E. Ingham, Some characters of the symmetric group, Proc. Amer. Math. Soc. 1 (1950) 358-369. It states that

$$\frac{\chi^{\lambda}(\pi)}{\chi^\lambda(id)} m(m-1)(m-2) = 3K_3 (\lambda) - \frac{3m(m-1)}{2} $$

where $\lambda$ is a partition of $m$ and $\pi$ is a $3$-cycle. Here $K_3(\lambda)$ can be defined as follows: put zeros in the boxes in the leading diagonal of the Young diagram of $\lambda$. In each row, put $1^2$, $2^2$, $\ldots$ in the boxes right of the $0$. In each column, put $1^2$, $2^2$, $\ldots$ in the boxes below the $0$. Then $K_3(\lambda)$ is the sum of all the numbers in the boxes of the Young diagram. Calculation shows that

$$K_3(n-1,\ldots,1) = \frac{(n+1)n(n-1)(n-2)}{12} = \frac{N(N-1)}{3} $$

where $N = \binom{n}{2}$, as in the question. Therefore

$$\frac{\chi^{(n-1,\ldots,1)}(\pi)}{\chi^{(n-1,\ldots,1)}(id)} N(N-1)(N-2) = -\frac{N(N-1)}{2} $$

and so

$$\sum_{i=1}^{n-2} \frac{f_{\delta_i}}{f_{(n-1,\ldots,1)}} = -\frac{\chi^{(n-1,\ldots,1)}(\pi)}{f_{(n-1,\ldots,1)}} = \frac{1}{2(N-2)}. $$

This differs from the answer claimed in the question but seems to be correct at least for $n=3,4,5$. (For example, if $n=3$ then we have $\delta_1 = \varnothing$ and the sum in the question is $1/f_{(2,1)} = 1/2$.)