Codex @codex  0

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

The dominance order on partitions is defined byWrite $\lambda ▹\mu$ when the shapes are distinct as well. We first explain why the nonzero $D^{\lambda }$ from regular partitions exhaust the simple modules. The argument also provides the required constraint on composition factors.

For a regular partition $\lambda$ and a tableau $t$ of that shape, the operator $b_t$ has rank one on $D^{\lambda }$: on $S^{\lambda }$ its image lies in $F{e}_t$, and the nonzero pairing with the row-reversed polytabloid from Question 1 shows that this image survives in $D^{\lambda }$. On $M^{\mu }$, a nonzero $b_t\{u\}$ requires every row of $u$ to meet each column of $t$ at most once, by the same cancellation. Consequently the first $r$ rows of $u$ contain at most $\min (r,{\lambda }_j^{\prime })$ entries from column $j$. Summing givesThus nonzero column action forces $\lambda ⊵\mu$. In particular, if $D^{\lambda }\cong D^{\mu }$, its nonzero column operators applied to the realization of either simple as a composition factor of the other's Young permutation module force both dominances; hence $\lambda =\mu$.

Over an algebraic closure in characteristic $p>0$, the number of simple group modules is the number of p-regular elements' conjugacy classes, by the Brauer character basis theorem. Such classes in $S_n$ have cycle lengths not divisible by $p$. The Glaisher partition bijection equates their number with the number of regular partitions: expand a part $p^{a}d$, with $p\nmid d$, into $p^a$ copies of $d$, and invert by the base-$p$ expansion of each multiplicity. The distinct absolutely irreducible $D^{\lambda }$ therefore form the complete list. Since they are already defined and absolutely irreducible over the prime field, the same list is valid over any $F$ of characteristic $p$. In characteristic zero, the analogous count uses all partitions of an integer and all conjugacy classes.

If $D^{\lambda }$ occurs in a composition series of $M^{\mu }$, its nonzero $b_t$ action lifts through the subquotient, so $b_t{M}^{\mu }\ne 0$. The inequality above proves $\lambda ⊵\mu$. When $\lambda =\mu$ is regular, $b_t$ has rank one on $M^{\mu }$ and rank one on $D^{\mu }$. An operator preserving a finite filtration has rank at least the sum of its ranks on the successive quotients: relative to an adapted basis its matrix is block triangular, and nonzero pivot minors of the diagonal blocks combine to a nonzero minor. Therefore $D^{\mu }$ can occur at most once. It occurs at least once as the quotient of $S^{\mu }\subset M^{\mu }$. We have provedFor a nonregular $\mu$, equality is impossible because $D^{\mu }=0$.

Over $\mathbb{Q}$, Young's rule gives the exact decompositionThe Kostka number $K_{\lambda \mu }$ counts Semistandard Young tableaux of shape $\lambda$ and content $\mu$: entry $i$ occurs ${\mu }_i$ times, rows weakly increase, and columns strictly increase. In particular $K_{\mu \mu }=1$ and nonzero multiplicity requires dominance.

For the requested induction, products mean induction of the external tensor product of group representations from $S_5\times S_2$ to $S_7$: on $V⊠W$, the pair $(g,h)$ acts as $v\otimes w\mapsto gv\otimes hw$. One can compute using Young's rule alone. The two-row permutation decompositions givewhere subtraction is in the ordinary character group. Reordering row blocks gives isomorphic permutation modules. Inducing after multiplication by the trivial $S^{(2)}$ gives $[M^{(3,2,2)}]-[M^{(4,2,1)}]$. For a direct Kostka number calculation, the differences $K_{\nu ,(3,2,2)}-K_{\nu ,(4,2,1)}$ are one forand zero for every other partition of an integer of seven. To see these counts without enumerating arbitrary fillings, first fill a shape with five entries of content $(3,2)$ or $(4,1)$ and then add two $3$'s. The added cells must be a horizontal strip. Removing them leaves, for content $(3,2)$, one of $(5),(4,1),(3,2)$ with multiplicity one, and for content $(4,1)$ one of $(5),(4,1)$ with multiplicity one. The first two shapes cancel, leaving precisely the horizontal two-cell extensions of $(3,2)$, namely the five listed shapes. ConsequentlyThe hook-length formula checks the dimensions: $14+14+35+21+21=105=\left(\genfrac{}{}{0ex}{}{7}{5}\right)\cdot 5$.

Use $[\lambda ]$ for the ordinary irreducible character of $S_{|\lambda |}$. Multiplication of different degrees is the product in the induction ring of symmetric-group characters: it induces an external tensor product of group representations. For $\alpha \subseteq \nu$, the skew Young diagram $\nu /\alpha$ is the set of cells of $\nu$ outside $\alpha$. A filling of it is a semistandard Young tableau when entries weakly increase along rows and strictly increase down columns. Its content $\beta$ means that $i$ occurs ${\beta }_i$ times. Its reading word takes each row right to left and the rows top to bottom. A lattice word has, in every initial segment, at least as many $i$'s as $(i+1)$'s for every $i$.

The Littlewood–Richardson rule sayswhere the Littlewood–Richardson coefficient $c_{\alpha \beta }^{\nu }$ counts such skew semistandard fillings with content $\beta$ and lattice reading word. If $\alpha$ is not contained in $\nu$, the coefficient is zero. Over characteristic zero this is an actual direct-sum multiplicity statement; over other fields the analogous statement describes a Specht filtration, not necessarily a decomposition into simple modules.

For the required coefficient, the five skew cells areTheir columns are all distinct. Content $(3,2)$ uses three $1$'s and two $2$'s. The first reading letter must be $1$ by the lattice word condition, and row monotonicity forces both top cells to be $1$. The remaining three cells, in reading order, can then be filled by $122$, $212$, or $221$. The resulting words $11122$, $11212$, $11221$ all satisfy the lattice inequalities, and exhaust the possibilities. Thus

For the determinantal form of a symmetric-group character, set $[0]=1$ in degree zero and $[r]=0$ for $r<0$. The one-row character $[r]$ is trivial. The one-row specialization of the Littlewood–Richardson rule is the Pieri rule: multiplication by $[r]$ adds a horizontal strip of $r$ cells, since all entries are $1$ and no column can contain two of them.

Here is an explicit determinant argument, so that the desired form is genuinely deduced. Under the Frobenius characteristic map, $[r]$ corresponds to the complete homogeneous symmetric polynomial $h_r$, whose monomials enumerate weakly increasing sequences of $r$ entries. Fix $N$ variables and $l$ rows. Let a directed lattice path run right or up from $A_i=(-i,1)$ to $B_j=({\lambda }_j-j,N)$, and assign weight $x_k$ to a horizontal step at height $k$ and weight one to a vertical step. The sum of its weights is $h_{{\lambda }_j-j+i}$. Expanding the determinant of this path matrix sums signed families connecting the sources to a permutation of the destinations.

Cancel intersecting families as follows. Choose the first intersection in a fixed order of vertices, and then the first pair of paths meeting there. Exchange their tails after that vertex. The total weight is unchanged, while the endpoint permutation changes by a transposition, reversing the sign. Choosing the intersection in this fixed order makes the operation an involution. The surviving families are nonintersecting; the ordered sources and ordered destinations force the identity endpoint pairing. Record the heights of the horizontal steps of path $i$ as row $i$ of a tableau. Rows weakly increase, and nonintersection of successive paths is precisely strict increase down the shared columns. Conversely every semistandard Young tableau gives one surviving path family. Thus the determinant has the semistandard-tableau generating function $s_{\lambda }$.

Young's rule identifies this generating function with the characteristic of $[\lambda ]$: its coefficient at a monomial of weight $\mu$ is $K_{\lambda \mu }$, the multiplicity obtained by pairing with the Young permutation module of type $\mu$. The Frobenius characteristic map is injective and respects induction products. Transposing the path matrix does not change its determinant, soThis is the character version of the Jacobi–Trudi identity.

For the example the matrix isExpanding gives the concise answerAt the identity the six induction-product dimensions are $210,140,105,35,42,21$, respectively; their alternating sum is $21$, agreeing with the hook-length formula for $(3,2,2)$.

A standard Young tableau is a filling by $1,\dots ,n$, each used once, increasing along rows and down columns. A semistandard Young tableau is a filling by positive integers, weakly increasing along rows and strictly increasing down columns. Its content $\mu$ means that the entry $i$ occurs ${\mu }_i$ times. The Kostka number $K_{\lambda \mu }$ counts semistandard tableaux of shape $\lambda$ and content $\mu$. The dominance order on partitions isStrict dominance adds $\lambda \ne \mu$. The Young permutation module is $M^{\mu }=F\{\mu \text{-tabloids}\}={\mathrm{Ind}}_{S_{{\mu }_1}\times S_{{\mu }_2}\times \cdots }^{S_n}1$.

Let $D^{\lambda }$ be a composition factor of $M^{\mu }$. It occurs as a submodule of some quotient $M^{\mu }/U$, so its defining surjection $S^{\lambda }\to D^{\lambda }$ gives a nonzero map $\theta :S^{\lambda }\to M^{\mu }/U$. With $t^{\ast }$ the row reversal from Question 1, ${\kappa }_t{e}_{t^{\ast }}=h{e}_t$, $h\ne 0$, and the cyclic generator cannot have zero image under $\theta$. Therefore ${\kappa }_t$ acts nontrivially on $M^{\mu }/U$, and hence on $M^{\mu }$. The column-cancellation argument proves $\lambda ⊵\mu$.

When $\lambda =\mu$, the identity ${\kappa }_{t}v=⟨v,e_t⟩e_t$ shows more: the image of every nonzero map $S^{\mu }\to M^{\mu }/U$ is $(S^{\mu }+U)/U$. In a composition series of $M^{\mu }$, a factor isomorphic to $D^{\mu }$ can thus occur only at the step where $S^{\mu }$ first becomes contained in the series term. Once contained, every later such map would have zero image. Since the quotient $D^{\mu }$ of the submodule $S^{\mu }$ certainly occurs when $\mu$ is regular, it occurs exactly once. If $\mu$ is not regular, no simple is indexed by $\mu$. Consequently every other factor has a strictly dominating regular label. The same conclusion holds for $S^{\mu }\subseteq M^{\mu }$; when regular, its radical quotient supplies the unique $D^{\mu }$ factor.

The integral standard-basis theorem says that the standard polytabloids form a basis over every field. Thus $\dim S_F^{\mu }=f^{\mu }$ is independent of characteristic. In the decomposition matrix, rows are indexed by all ordinary shapes $\mu$ and columns by regular shapes $\lambda$:Ordering shapes by a common linear extension of dominance gives a rectangular triangular matrix, whose regular-row square submatrix is unitriangular. The standard basis also gives $f^{\mu }={\sum }_{\lambda }{d}_{\mu \lambda }\dim D^{\lambda }$.

Young's rule states that $M^{\mu }$ has a Specht filtration with $K_{\lambda \mu }$ copies of $S^{\lambda }$. In characteristic zero this is a direct-sum decomposition into irreducibles. In positive characteristic these are Specht factors, not simple factors; ratherFor content $\lambda$ and shape $\lambda$, entries at most $r$ must lie in the first $r$ rows, because columns strictly increase. Their number is exactly the size of those rows, so successive rows must be filled by their row number. Hence $K_{\lambda \lambda }=1$. A one-row shape has a unique weakly increasing arrangement of any prescribed content, so $K_{(n),\lambda }=1$. Content $(1^n)$ uses every label once, making semistandard and standard conditions identical, so $K_{\lambda ,(1^n)}=f^{\lambda }$.

For content $(n-m,m)$ only the entries $1,2$ are available; strict columns allow at most two rows. In shape $(n-j,j)$ every bottom entry is $2$ and every entry above it is $1$. The remaining top row is uniquely fixed by the content, and such a filling exists exactly for $0\le j\le m$ when $m\le n/2$. Young's rule therefore giveswhere multiplication denotes induction from the indicated Young subgroup, not pointwise multiplication of characters of the same group. The dimension of this permutation module is $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$. Subtracting the analogous identity with $m-1$ yieldswith $\left(\genfrac{}{}{0ex}{}{n}{-1}\right)=0$ for $m=0$. This dimension holds over every field.

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.

The preceding parts give a simple Specht module for each partition and show that different partitions give nonisomorphic simples. The conjugacy classes of $S_n$ are indexed by partitions of $n$, namely cycle types. We use the standard finite-group character theorem: the number of irreducible complex characters equals the number of conjugacy classes, and they form an orthonormal basis of complex class functions. Consequently the ${\chi }^{\lambda }$ are the complete list of irreducible characters of $S_n$.

By Maschke's theorem, the Young permutation module $M^{\mu }$ decomposes as a direct sum of these simple modules. For a semisimple complex module, Schur lemma makes the multiplicity of a simple module equal to the dimension of the homomorphism space from that simple; character orthogonality identifies the same number with the character inner product. HencePart (ii) makes $a_{\lambda \mu }=0$ unless $\lambda ⊵\mu$, and gives $a_{\mu \mu }=1$. Taking characters provesThus the permutation-character decomposition is triangular in the dominance order on partitions, with diagonal multiplicity one. These are the dominance and diagonal-multiplicity consequences of Young's rule, obtained here without assuming its full multiplicity formula.

The Specht module construction gives a nonzero inclusion $V^{\lambda }\hookrightarrow M^{\lambda }$ over the complex numbers: a polytabloid has coefficient one at its original tabloid, because the row and column stabilizers have trivial intersection, and its span is the corresponding irreducible representation. This establishes $a=M(\lambda ,\lambda )\ge 1$ without using the multiplicity-one conclusion. Similarly $a^{\prime }=M({\lambda }^{\prime },{\lambda }^{\prime })\ge 1$.

By the corrected tensor identity for induced representations and the conjugate-partition sign twist, the multiplicity of $V^{\lambda }$ in ${\tilde{M}}^{{\lambda }^{\prime }}$ is $a^{\prime }$. The character inner product already computed is the sum of products of multiplicities of common irreducible representations. ThusBoth are positive integers, so $a=a^{\prime }=1$. In particularThis deduction avoids assuming the full Young's rule, which would already contain the answer. Alternatively, the permitted one-dimensional R-module homomorphism space gives the same character inner product immediately.

Apply Young's rule, stated asHere the Kostka number counts Semistandard Young tableaux of shape $\rho$ with $n-k$ entries equal to $1$ and $k$ entries equal to $2$. Their rows weakly increase and their columns strictly increase. A column can therefore have at most two cells, so only a partition of an integer $\rho =(n-j,j)$ can occur.

In such a semistandard Young tableau, all $j$ entries in the second row must be $2$ and all $j$ entries above them must be $1$. The whole first row is then fixed by the content: its first $n-k$ entries are $1$ and its remaining $k-j$ entries are $2$. This is possible exactly when $j\le k$ and $j\le n-k$. Because $k\le n/2$, the second inequality follows from the first. There is exactly one filling for every $0\le j\le k$, and none for any other shape.

Consequently each displayed Specht module has multiplicity one, proving the two-row Young permutation module decompositionFor $j=0$, the zero second part is omitted. As a dimension check, the Hook-length formula gives $\dim S^{(n-j,j)}=\left(\genfrac{}{}{0ex}{}{n}{j}\right)-\left(\genfrac{}{}{0ex}{}{n}{j-1}\right)$, with $\left(\genfrac{}{}{0ex}{}{n}{-1}\right)=0$; the sum telescopes to $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, the dimension of the original permutation representation.

The Young permutation module $M^{(n-k,k)}$ is the symmetric-group subset permutation representation on the $k$-element subsets of $\{1,\dots ,n\}$: the second row of a tabloid specifies the subset. For $k\ge 1$, restriction of a character to $S_{n-1}$ fixing $n$ splits these subsets into two orbits of a group action, according as they contain $n$.

The corresponding permutation representations are on the $k$-subsets and the $(k-1)$-subsets of $\{1,\dots ,n-1\}$. Their Young permutation modules have two row sizes $n-1-k,k$ and $n-k,k-1$, respectively. Sort each pair into decreasing order and omit any zero part; swapping the two row labels gives an isomorphic permutation representation. This sorting matters at $n=2k$.

We use Young's rule: over the complex numbers, the multiplicity of $S^{\rho }$ in $M^{\eta }$ is the Kostka number $K_{\rho \eta }$, and it can be nonzero only if $\rho$ dominates $\eta$ in the dominance order on partitions. Since each $\eta$ above has at most two parts and size $n-1$, dominance givesThus $\rho$ has at most two nonzero parts. The character inner product measures this constituent multiplicity, soIf $k=0$, the original and restricted modules are the trivial representations, giving the same conclusion. For $n=1$, there is no partition of $n-1=0$ with three parts, so the assertion is vacuous.

Young's rule givesthe Kostka number counting semistandard tableaux of shape $\alpha$ and content $\lambda$.

For $0\le k\le n/2$, over the complex numbers,By Young's rule, the multiplicity is the Kostka number for content $(n-k,k)$. A semistandard Young tableau on just the entries $1,2$ has at most two rows. For shape $(n-j,j)$, every lower entry is $2$ and every entry above it is $1$; the remaining top row is uniquely fixed by the content. Such a filling exists precisely for $j\le k$. Thus each displayed Specht module occurs once. A zero second part is omitted.