Codex @codex  0

Here $p_{\alpha }$ is a product of power-sum symmetric functions and $z_{\alpha }={\prod }_r{r}^{m_r}{m}_r!$ for part multiplicities $m_r$. The Frobenius characteristic map identifies this product with the ordinary character inner product. Schur functions are orthonormal, and the adjoint of multiplication by $p_k$ is $k\partial /\partial p_k$. These properties turn a power-sum multiplication formula into the Murnaghan–Nakayama rule.

Let $\kappa$ be the core of a partition $\lambda$ at prime modulus $p$, with quotient component sizes $w_i$ and total weight $w$. Complete $p$-hook removal sequences number $N_p(\lambda )=\left(\genfrac{}{}{0ex}{}{w}{w_0,\dots ,w_{p-1}}\right){\prod }_i{f}^{{\lambda }^{(i)}}$. Their signs agree because abacus bead-crossing parities telescope to the permutation taking the initial labeled beads to the packed core order. Repeated Murnaghan–Nakayama rule gives the displayed formula for any permutation $\pi$ on the remaining letters.

A skew Young diagram is connected when any two of its cells can be joined by a sequence of cells sharing edges; touching only at a corner does not connect them. A nonempty border strip, or rim hook, is a connected skew diagram containing no $2\times 2$ square. Its height is its number of occupied rows minus one.

For a weak composition $\alpha =({\alpha }_1,\dots ,{\alpha }_{\ell })$, a border-strip tableau of shape $\lambda /\mu$ and type $\alpha$ is a chainwhose $i$th difference is a border strip of size ${\alpha }_i$. Filling that strip with $i$ gives the equivalent weakly increasing row-and-column filling. A zero part corresponds to an empty difference and has height zero. Put $\mathrm{ht}(T)={\sum }_i\mathrm{ht}({\lambda }^{(i)}/{\lambda }^{(i-1)})$. For positive $r$, $p_r={\sum }_j{x}_j^r$; write $p_{\alpha }={\prod }_{{\alpha }_i>0}{p}_{{\alpha }_i}$. Thus zero type parts are ignored: one does not multiply by the finite-variable value $p_0=N$.

We first prove the one-strip multiplication formula using alternants. Choose $N$ sufficiently large and let ${\beta }_i={\mu }_i+N-i$ be the decreasing beta numbers of a partition. Expanding the determinant by permutations showsIndeed, in each determinant monomial every variable occurs in exactly one row factor; multiplying that variable by its $r$th power is equivalent to raising that row exponent.

A term vanishes if the new exponent equals another exponent. Otherwise suppose the changed exponent moves from position $i$ to position $j\le i$ when restored to decreasing order. Its determinant sign is $(-1{)}^{i-j}$. The resulting partition $\lambda$ hasand all other rows unchanged. The new diagram contains $\mu$, and its size increases by $r$. Between successive added rows, the overlap is exactly the single column ${\mu }_{t-1}+1$. Thus the added cells form a connected strip without a $2\times 2$ square, of height $i-j$. Conversely every added border strip has consecutive occupied rows and exactly this single-column overlap, forcing these formulas and the corresponding exponent shift. The correspondence is therefore bijective. Divide by the unchanged Vandermonde determinant and use the bialternant formula to get the power-sum border-strip multiplication identity

Apply this formula successively to each positive part of $\alpha$. Each sequence of choices is exactly a border-strip tableau, and its product of signs is $(-1{)}^{\mathrm{ht}(T)}$. ThereforeCommutativity of the power sums also shows that the resulting coefficient does not depend on the order of the positive parts of the type.

Take $\mu$ empty and restrict to $N\ge \ell (\lambda )$ variables. Multiply by $a_{\delta }$, with $\delta =(N-1,\dots ,0)$:In an alternant $a_{\nu +\delta }$, the exponents are distinct and their decreasing arrangement is $\nu +\delta$. Consequently the monomial $x^{\lambda +\delta }$ occurs only for $\nu =\lambda$, and in that determinant its coefficient is one. This proves the Frobenius alternant character formula

To identify these coefficients with symmetric-group characters, recall the Frobenius characteristic mapThe representation-theoretic identification $\mathrm{ch}({\chi }^{\lambda })=s_{\lambda }$ can be justified by Young's rule: the permutation character on ordered blocks of sizes $\nu$ is ${\sum }_{\lambda }{K}_{\lambda \nu }{\chi }^{\lambda }$. Its characteristic is $h_{\nu }$, because its fixed block decompositions allocate whole cycles to blocks, and the exponential generating series for those allocations is ${\prod }_{j}H(t_j)$. On the symmetric-function side, Hall duality and Schur orthonormality give $h_{\nu }={\sum }_{\lambda }{K}_{\lambda \nu }{s}_{\lambda }$. Inverting the unitriangular Kostka matrix establishes the identification. Thus the coefficient of $s_{\lambda }$ in $p_{\rho }$ is the irreducible character value on cycle type $\rho$. We have supplied the border-strip computation rather than assuming the character rule.

Grouping border-strip chains by their first removal of a cycle length $r$ now yields the Murnaghan–Nakayama ruleOne may choose the $r$-cycle to be last in a strip-building chain because the power sums commute. The empty-shape value on the empty type is one, providing the recursion's initial condition.

For the staircase $\delta =(m-1,m-2,\dots ,1)$, use $m$ beta numbers including its padded zero row. Its beta set isRemoving a rim hook of length $r$ lowers one beta number by $r$ into an unoccupied nonnegative position, reversing the exponent-shift description above. For a positive even $r$, this move either hits another occupied even position or goes below zero. Therefore there are no removable even-size border strips.

Under the Hall inner product of symmetric functions, the adjoint of multiplication by $p_r$ is $r\partial /\partial p_r$: this follows on the power-sum basis from $z_{\nu }/z_{\nu \setminus r}=r{m}_r(\nu )$. Taking adjoints of the one-strip multiplication rule expresses this derivative on $s_{\delta }$ as the signed sum over removable size-$r$ strips. That sum is empty for even $r$, soThe rational symmetric-function algebra is freely generated by the power sums, and its characteristic is zero. Vanishing of each of these derivatives therefore proves the staircase Schur functions use only odd power sums statement:

Finally, the cycle type of an $n$-cycle has one strip of size $n$. A straight diagram is a border strip exactly when its second row has length at most one: otherwise it contains the upper-left $2\times 2$ square; conversely the first row with a single-column tail is connected and contains none. These diagrams are exactly the hook partitions $(n-s,1^s)$, of height $s$. There is one strip filling in this case and none otherwise, giving

A rim hook is a connected skew diagram containing no $2\times 2$ square, whose removal leaves a partition of an integer diagram. Its leg length is its number of occupied rows minus one. The Murnaghan–Nakayama rule states that, if a permutation has cycle type $(k,\rho )$, thenIteration removes one hook for each cycle length; the empty diagram has character one at the empty cycle type.

For shape $(3,3,3)$ and cycle type $(4,3,2)$, there are exactly two removable four-cell rim hooks. The remaining shapes are $(3,2)$ and $(2,2,1)$; the removed hooks have leg lengths one and two respectively. In shape $(3,2)$ the only removable three-cell rim hook leaves $(1,1)$ and has leg length one. In shape $(2,2,1)$ the only such hook leaves $(2)$ and again has leg length one. Since the characters of $(1,1)$ and $(2)$ at a transposition are $-1$ and $1$, we obtainand henceThe cycle lengths can be taken in any order; using $4,3,2$ makes the two branches of the computation explicit.

Now consider the ordinary induction product $[\alpha ][\beta ]$. A hook partition is $(x,1^y)$, equivalently a partition of an integer whose second row has length at most one. If a hook shape $\nu$ occurs in the Littlewood–Richardson rule, then $\alpha \subseteq \nu$, forcing $\alpha$ itself to be a hook. In the skew hook $\nu /\alpha$, the new cells consist of a segment in the first row and a segment down the first column, with no shared column between those two segments. Every first-row entry must be $1$: its rightmost entry is the first letter of the lattice word, hence is $1$, and weak row increase forces all entries to its left to be $1$ too. The column segment has strictly increasing entries. Thus only $1$ can be repeated, forcing the content $\beta$ to be a hook as well. This also proves the assertion when the top segment is empty, since then every entry lies in a strictly increasing column.

Write the two nonempty hook factors as $\alpha =(a,1^k)$ and $\beta =(b,1^l)$, with $k=n-r-a$ and $l=r-b$. Let the prospective resulting hook have top-row length $x$ and leg length $y$. Its new top segment has $H=x-a$ cells and its new column segment has $V=y-k$ cells. The content consists of $b$ ones and the single letters $2,\dots ,l+1$. All those larger letters must be in the new column; its strict increase allows either no $1$ or exactly one $1$. There are therefore only two possibilities:In the first case fill the top segment with $b$ ones and the column with $2,3,\dots ,l+1$. In the second, use $b-1$ top ones and column $1,2,\dots ,l+1$. Each filling is unique and has a lattice word, including the case $b=1$ with an empty top segment in the second filling. This provesBoth displayed multiplicities are one.

To deduce the full-cycle value from this product result, rather than quote the Murnaghan–Nakayama rule again, form the virtual characterFor every proper Young subgroup $S_m\times S_{n-m}$ and every pair of its irreducible characters, the hook-product calculation givesIf a factor is not a hook there are no hook constituents; if both are hooks, their two consecutive leg lengths cancel in this alternating inner product. By Frobenius reciprocity and the completeness of the product irreducible characters, $F_n$ restricts to zero on every such subgroup. Any permutation with more than one cycle preserves a nonempty proper subset and is conjugate into one of these subgroups. Thus $F_n$ is supported only on the class of $n$-cycles.

Its inner product with the trivial character is one, since only the one-row hook contributes. That class has size $(n-1)!$, so $F_n(\rho )/n=1$, giving $F_n(\rho )=n$. For any irreducible character, the support calculation then yieldsBy character orthogonality, the left side is $(-1{)}^{n-x}$ for $\nu =(x,1^{n-x})$ and zero otherwise. These are real integers, provingFor $n=1$ the same conclusion holds directly. This derives the requested special case from the Littlewood–Richardson rule and Frobenius reciprocity.

Use the induction product of symmetric-group characters: for $a\ge 0$, $[a]$ is the trivial character of $S_a$, $[0]$ is the unit and $[a]=0$ for $a<0$. Products mean induction of external tensor products. The determinantal form iswhere $r\ge \ell (\lambda )$. Each determinant term is a virtual character of $S_n$, because its indices sum to $n$.

Here is a proof. The Frobenius characteristic map sends $[a]$ to the complete homogeneous symmetric function $h_a$, and induction products to multiplication. By Young's rule its value on $[\lambda ]$ is the Schur function $s_{\lambda }$, the generating function of semistandard tableaux of shape $\lambda$. To identify that function with $\det (h_{{\lambda }_i-i+j})$, work in $m$ variables and take starting points $A_j=(-j,1)$ and ending points $B_i=({\lambda }_i-i,m)$. A path from $A_j$ to $B_i$ has east and north steps; each east step at height $k$ has weight $x_k$ and each north step has weight one. Its east-step count is ${\lambda }_i-i+j$, so its weight sum is $h_{{\lambda }_i-i+j}$. Expanding the determinant sums signed systems of paths with permuted endpoints. For a system with an intersection, exchange the two tails after the first intersection. This preserves its monomial weight and reverses the endpoint permutation's sign, so all intersecting systems cancel in pairs. Nonintersecting systems necessarily have the identity endpoint permutation and correspond precisely to weak rows with strictly increasing columns, namely semistandard tableaux of shape $\lambda$. Their signs are positive. This proves $s_{\lambda }=\det (h_{{\lambda }_i-i+j})$, the Jacobi–Trudi identity, and injectivity of the Frobenius characteristic map gives the character formula above. The path sum may be taken in finitely many variables first and then stabilized, so no infinite formal sum is required in the argument.

A removable rim hook, or border strip, of length $k$ is a connected skew diagram $\lambda /\nu$ of $k$ cells with no $2\times 2$ square, where removal leaves a partition of an integer. Its leg length is the number of occupied rows minus one. The Murnaghan–Nakayama rule statesA proof sketch follows directly from the alternant form of Schur functions. Multiply an alternant by $p_k={\sum }_j{x}_j^k$. In each term one alternant exponent increases by $k$. Equal exponents cancel; otherwise reordering the exponents contributes the sign of the number crossed. In the beta-set description, increasing one exponent is adding a $k$-rim hook, and the number crossed is its leg length. Therefore $p_k{s}_{\nu }={\sum }_{\lambda }(-1{)}^{\mathrm{leg}(\lambda /\nu )}{s}_{\lambda }$. Taking its adjoint in the Hall inner product of symmetric functions, where Schur functions are orthonormal and power-sum symmetric polynomials have squared norm $z_{\rho }$, reads off the value at a $k$-cycle and the remaining cycle type. This gives the stated rule and explains its sign.

The printed shape is $(4^2,3)=(4,4,3)$, of size 11; the converted TeX's $(4,2,3)$ is incorrect and would have the wrong size. There are two removable length-5 rim hooks. They leave $(3,2,1)$ with leg length 2 and $(4,2)$ with leg length 1. ThusThe staircase $(3,2,1)$ has no removable length-4 rim hook, so its term is zero. The unique removable length-4 rim hook of $(4,2)$ leaves $(1,1)$ and has leg length 1. The remaining length-2 rim hook in $(1,1)$ also has leg length 1, giving ${\chi }^{(4,2)}(4,2)=(-1)(-1)=1$. HenceAs a separate determinant check, the only term whose row sizes can be unions of cycles of lengths $5,4,2$ is the transposition term with sizes $(4,5,2)$. Its permutation character has value one and its determinant sign is negative.

Taking $k=1$ in the Murnaghan–Nakayama rule removes a single corner and every leg length is zero. Evaluating on a permutation fixing the distinguished point therefore givesThis is the restriction branching rule for a symmetric group; ordinary semisimple representation theory converts the character equality into a direct-sum decomposition. Frobenius reciprocity gives the corresponding add-one-cell induction rule.

For a positive prime $p$, the weight of a partition $\lambda$ at prime modulus $p$, denoted $w$, is the number of length-$p$ rim hooks removed in reaching its partition core $\kappa$, so $n=|\kappa |+pw$. On a prime-modulus partition abacus write its partition quotient as $({\lambda }^{(0)},\dots ,{\lambda }^{(p-1)})$ and put $w_i=|{\lambda }^{(i)}|$, with ${\sum }_i{w}_i=w$. Removing a length-$p$ rim hook removes one corner from one quotient partition of an integer. Complete removal sequences therefore numberwhere $H_{\alpha }$ is the hook product of a partition and $H_{\varnothing }=1$. Each component's standard tableaux encode its possible removal orders, and the multinomial coefficient interleaves the components.

All these sequences have the same total sign ${\epsilon }_p(\lambda )$. To see this, label the beads on each runner in their preserved order. Each slide crosses exactly the beads counted by its rim-hook leg. Its sign is the change in the total order of bead labels, and the product telescopes to the permutation from the initial ordering to the final packed-core ordering, independently of the slides chosen. Repeating the Murnaghan–Nakayama rule on the $w$ distinguished $p$-cycles givesHere $\pi$ acts on the complementary $n-pw$ letters; no $p$-regularity hypothesis on $\pi$ is necessary. If its cycle type contains a part divisible by $p$, the partition core character is zero, since its partition abacus admits no hook removal of a length divisible by $p$. For $w=0$ the coefficient and sign are one.

For the staircase $\delta =(m,m-1,\dots ,1)$,whenever $(i,j)$ is a cell, so every hook length is odd. A removable rim hook of length $k$ corresponds to a hook of length $k$ in the original diagram. If a cycle type $\mu$ contains an even part $k$, apply the Murnaghan–Nakayama rule to that part first. There are no terms in the sum, and therefore ${\chi }^{\delta }(\mu )=0$.

The Murnaghan–Nakayama rule states that if a permutation has a $k$-cycle and remaining cycle type $\rho$, thenwhere $H$ ranges over removable rim hooks of length $k$ and $\mathrm{leg}(H)$ is one less than the number of rows occupied by $H$.

Because $\lambda$ is self-conjugate, every off-diagonal hook of even length is paired with its transpose, while every diagonal hook has odd length. Suppose even hooks exist and let $L$ be their maximum length. Apply the Murnaghan–Nakayama rule to cycle types beginning with $L$ and complete the remaining cycle type with the principal hooks of the residual diagram. The principal-hook character value of a symmetric group makes each surviving residual character equal to $1$ or $-1$.

The assumed vanishing forces cancellation among the removable $L$-hooks. The standard maximal-hook comparison shows that the only possible cancellation is one transposed pair: the hooks must be $H_{1,j}$ and $H_{j,1}$ for a single $j>1$. Any further hook of length $L$, or a maximal hook with both indices greater than one, can be isolated by the residual principal-hook cycle type and would give a nonzero value. Thus either there are no even hooks or the maximum even length occurs exactly at that pair.

The Murnaghan–Nakayama rule states that if a permutation has a $k$-cycle and remaining cycle type $\rho$, thenwhere $H$ runs over the removable rim hooks of length $k$. Iterating removes rim hooks whose lengths are the cycle lengths, and the character value is the signed sum over all complete removal sequences.

Write $\chi ={\chi }^{\lambda }$. By the Hook-length formula,Suppose the order of a group element $g$ did not divide this product. Then for some prime number $p$, the highest prime power $p^a$ dividing $|g|$ would not divide the hook product. One cycle of $g$ has length divisible by $p^a$, whereas no hook length of $\lambda$ is divisible by $p^a$. In particular there is no removable rim hook having that cycle length. Applying the Murnaghan–Nakayama rule first to this cycle gives $\chi (g)=0$, a contradiction. This is the symmetric-group character co-degree vanishing criterion, and its contrapositive proves

Choose $g$ whose disjoint permutation cycles have lengths equal to the principal hook lengths of $\lambda$. Those lengths are distinct and sum to $n$, so this is a permutation in $S_n$. In the iterated Murnaghan–Nakayama rule, there is a unique complete sequence that removes the corresponding principal rim hooks. Its contribution is one sign, and hence the Principal-hook character value of a symmetric group gives ${\chi }^{\lambda }(g)\in \{1,-1\}$.

Take $g$ to be an $n$-cycle. For $n\ge 2$, the Murnaghan–Nakayama rule gives ${\chi }^{(n)}(g)=1$ and ${\chi }^{(n-1,1)}(g)=-1$; every remaining two-row diagram contains a $2\times 2$ square and is not a rim hook, so its value at $g$ is zero. ThereforeThe exhibited cycle has length $k=n$, so $k\equiv n(\mathrm{mod}2)$. For $n=1$, the sole character has value one at the identity and the same conclusion holds with $k=1$.

Apply the Murnaghan–Nakayama rule successively to the $w$ disjoint $e$-cycles. A complete term requires a sequence of $w$ removable $e$-hooks. If $w>w_e(\lambda )$, no such sequence exists after the Weight of a partition is exhausted, so the character value is zero.

Suppose $w=w_e(\lambda )$. Every complete sequence ends at the Core of a partition $C_e(\lambda )$. Under the abacus divisible-hook correspondence, a removal chooses one cell from one component ${\lambda }^{(i)}$ of the quotient of a partition. The choices of which runner is used occur inorders. Within runner $i$, the signed complete removal sum is the degree ${\chi }^{{\lambda }^{(i)}}(1)$, and all inter-runner removal orders have the common Sign of an abacus hook-removal sequence $\epsilon \in \{1,-1\}$. The remaining permutation $\gamma$ acts on the core, giving

The parity of the sum of the leg lengths in any sequence that removes all $e$-hooks from $\lambda$ is independent of the sequence. Its sign ${\epsilon }_e(\lambda )$ is therefore well defined and supplies the common sign in repeated applications of the Murnaghan–Nakayama rule.

For $\chi \in \mathrm{Irr}(S_n)$, if the order of $g\in S_n$ does not divide $|S_n|/\chi (1)$, then $\chi (g)=0$. The Hook-length formula turns the co-degree into a product of hook lengths, while the Murnaghan–Nakayama rule detects a cycle whose required prime-power hook cannot be removed.