Kostka number

In mathematics, the Kostka number K_λμ (depending on two integer partitions λ and μ) is a non-negative integer that is equal to the number of semistandard Young tableaux of shape λ and weight μ. They were introduced by the mathematician Carl Kostka in his study of symmetric functions (Kostka (1882)).[1]

The three semistandard Young tableaux of shape λ = (3, 2) and weight μ = (1, 1, 2, 1). They are counted by the Kostka number K_λμ = 3.

For example, if λ = (3, 2) and μ = (1, 1, 2, 1), the Kostka number K_λμ counts the number of ways to fill a left-aligned collection of boxes with 3 in the first row and 2 in the second row with 1 copy of the number 1, 1 copy of the number 2, 2 copies of the number 3 and 1 copy of the number 4 such that the entries increase along columns and do not decrease along rows. The three such tableaux are shown at right, and K_{(3, 2) (1, 1, 2, 1)} = 3.

Examples and special cases

For any partition λ, the Kostka number K_λλ is equal to 1: the unique way to fill the Young diagram of shape λ = (λ₁, λ₂, ..., λ_m) with λ₁ copies of 1, λ₂ copies of 2, and so on, so that the resulting tableau is weakly increasing along rows and strictly increasing along columns is if all the 1s are placed in the first row, all the 2s are placed in the second row, and so on. (This tableau is sometimes called the Yamanouchi tableau of shape λ.)

The Kostka number K_λμ is positive (i.e., there exist semistandard Young tableaux of shape λ and weight μ) if and only if λ and μ are both partitions of the same integer n and λ is larger than μ in dominance order.[2]

In general, there are no nice formulas known for the Kostka numbers. However, some special cases are known. For example, if μ = (1, 1, 1, ..., 1) is the partition whose parts are all 1 then a semistandard Young tableau of weight μ is a standard Young tableau; the number of standard Young tableaux of a given shape λ is given by the hook-length formula.

Properties

An important simple property of Kostka numbers is that K_λμ does not depend on the order of entries of μ. For example, K_{(3, 2) (1, 1, 2, 1)} = K_{(3, 2) (1, 1, 1, 2)}. This is not immediately obvious from the definition but can be shown by establishing a bijection between the sets of semistandard Young tableaux of shape λ and weights μ and μ', where μ and μ' differ only by swapping two entries.[3]

Kostka numbers, symmetric functions and representation theory

In addition to the purely combinatorial definition above, they can also be defined as the coefficients that arise when one expresses the Schur polynomial s_λ as a linear combination of monomial symmetric functions m_μ:

${\displaystyle s_{\lambda }=\sum _{\mu }K_{\lambda \mu }m_{\mu },}$

where λ and μ are both partitions of n. Alternatively, Schur polynomials can also be expressed[4] as

${\displaystyle s_{\lambda }=\sum _{\alpha }K_{\lambda \alpha }x^{\alpha },}$

where the sum is over all weak compositions α of n and x^α denotes the monomial x₁^α₁⋯x_n^α_n.

Because of the connections between symmetric function theory and representation theory, Kostka numbers also express the decomposition of the permutation module M_μ in terms of the representations V_λ corresponding to the character s_λ, i.e.,

${\displaystyle M_{\mu }=\bigoplus _{\lambda }K_{\lambda \mu }V_{\lambda }.}$

On the level of representations of the general linear group ${\displaystyle \mathrm {GL} _{n}(\mathbb {C} )}$, the Kostka number K_λμ counts the dimension of the weight space corresponding to μ in the irreducible representation V_λ (where we require μ and λ to have at most n parts).

Examples

The Kostka numbers for partitions of size at most 3 are as follows:

K_{(0) (0)} = 1 (here (0) represents the empty partition)

K_{(1) (1)} = 1

K_{(2) (2)} = K_{(2) (1,1)} = K_{(1,1) (1,1)} = 1, K_{(1,1) (2)} = 0.

K_{(3) (3)} = K_{(3) (2,1)} = K_{(3) (1,1,1)} = 1

K_{(2,1) (3)} = 0, K_{(2,1) (2,1)} = 1, K_{(2,1) (1,1,1)} = 2

K_{(1,1,1) (3)} = K_{(1,1,1) (2,1)} = 0, K_{(1,1,1) (1,1,1)} = 1

These values are exactly the coefficients in the expansions of Schur functions in terms of monomial symmetric functions:

s = m = 1 (indexed by the empty partition)

s₁ = m₁

s₂ = m₂ + m₁₁

s₁₁ = m₁₁

s₃ = m₃ + m₂₁ + m₁₁₁

s₂₁ = m₂₁ + 2m₁₁₁

s₁₁₁ = m_111.

Kostka (1882, pages 118-120) gave tables of these numbers for partitions of numbers up to 8.

Generalizations

Kostka numbers are special values of the 1 or 2 variable Kostka polynomials:

${\displaystyle K_{\lambda \mu }=K_{\lambda \mu }(1)=K_{\lambda \mu }(0,1).}$

Notes

1. Stanley, Enumerative combinatorics, volume 2, p. 398.
2. Stanley, Enumerative combinatorics, volume 2, p. 315.
3. Stanley, Enumerative combinatorics, volume 2, p. 311.
4. Stanley, Enumerative combinatorics, volume 2, p. 311.

References

• Stanley, Richard (1999), Enumerative combinatorics, volume 2, Cambridge University Press
• Kostka, C. (1882), "Über den Zusammenhang zwischen einigen Formen von symmetrischen Funktionen", Crelle's Journal, 93: 89–123
• Macdonald, I. G. (1995), Symmetric functions and Hall polynomials, Oxford Mathematical Monographs (2nd ed.), The Clarendon Press Oxford University Press, ISBN 978-0-19-853489-1, MR 1354144, archived from the original on 2012-12-11
• Sagan, Bruce E. (2001) [1994], "Schur functions in algebraic combinatorics", Encyclopedia of Mathematics, EMS Press