1 Definition and basic setup
Kostka numbers are integers that arise from counting semistandard Young tableaux with prescribed shape and content. They are central objects in algebraic combinatorics because they connect partition theory, symmetric functions, and representation theory. In many settings, they are denoted by \(K_{\lambda \mu}\), where \(\lambda\) is a partition describing the tableau shape and \(\mu\) is a partition or composition describing the weight.
1.1 Partitions and Young diagrams
A partition is a finite nonincreasing sequence of positive integers, such as \((4,2,1)\), whose parts sum to a positive integer. Its Young diagram is a left-justified array of boxes with row lengths given by the parts. Young diagrams provide a visual way to organize combinatorial data and are the standard shapes used in tableau theory.
Partitions are often compared using dominance order, and they index many families of symmetric functions and representations. In the context of Kostka numbers, both the shape and the weight are typically expressed using partitions, though some conventions allow compositions for the weight.
1.2 Semistandard Young tableaux
A semistandard Young tableau is a filling of a Young diagram with positive integers subject to monotonicity rules. These tableaux are the combinatorial objects counted by Kostka numbers. They are widely used because they package both shape data and multiplicity data in a form that is easy to count and manipulate.
1.2.1 Row and column conditions
In a semistandard Young tableau, entries weakly increase along each row from left to right, and strictly increase down each column. These conditions distinguish semistandard tableaux from standard Young tableaux, where each number appears exactly once. The row and column rules ensure that the tableaux behave well under algebraic operations on symmetric functions.
1.2.2 Weight of a tableau
The weight of a tableau records how many times each label appears. For example, if the entry \(1\) appears three times, \(2\) appears twice, and \(3\) appears once, the weight is \((3,2,1)\). This weight determines the content counted by a Kostka number and is usually written as a partition or composition matching the multiplicities of the entries.
1.3 Definition of Kostka numbers
The Kostka number \(K_{\lambda \mu}\) is the number of semistandard Young tableaux of shape \(\lambda\) and weight \(\mu\). Equivalently, it counts the tableaux whose diagram shape is \(\lambda\) and whose entries occur with multiplicities prescribed by \(\mu\). When no such tableau exists, the Kostka number is zero.
These numbers appear as coefficients in the expansion of Schur functions into the monomial symmetric function basis. This algebraic interpretation is one of the main reasons they are important in symmetric function theory.
1.4 Notation and conventions
The notation \(K_{\lambda \mu}\) is standard, though some sources may reverse the order of the indices or use different symbols. In most conventions, \(\lambda\) denotes a partition of the shape and \(\mu\) denotes the weight. If \(\mu\) is treated as a composition, the resulting counting depends only on its sorted partition form in the symmetric function setting.
Conventions may also vary in how empty parts or trailing zeros are handled. Despite these notational differences, the underlying counting problem remains the same.
2 Fundamental properties
Kostka numbers have several basic features that follow directly from their combinatorial definition and their role in symmetric function expansions. These properties make them manageable to compute in small cases and structurally meaningful in general.
2.1 Nonnegativity and integrality
Each Kostka number is a nonnegative integer, since it counts a finite set of tableaux. There is no cancellation involved in the definition. This simple fact is important because it contrasts with many other coefficients in algebraic combinatorics, which may be rational or signed.
2.2 Dependence on shape and weight
The value of \(K_{\lambda \mu}\) depends strongly on both the tableau shape and the weight. Even small changes in either parameter can alter the count substantially. The shape controls the geometry of the filling constraints, while the weight determines how many of each entry must be placed.
Because the row and column conditions are asymmetric, the same multiset of parts can lead to different counts when arranged differently as a composition. In the symmetric function setting, however, the coefficient depends only on the partition type of the weight.
2.3 Symmetry and special values
Some Kostka numbers have immediate values. For example, \(K_{\lambda \lambda}=1\) for a partition \(\lambda\), since there is a unique semistandard tableau of shape and weight both equal to \(\lambda\) with the standard row-constant filling. More generally, the numbers exhibit strong triangularity with respect to dominance order.
There is no general symmetry exchanging \(\lambda\) and \(\mu\), because shape and weight play different roles. Nonetheless, the collection of all Kostka numbers forms a structured family organized by partition order and tableau constraints.
2.4 Dominance order criterion
A key feature of Kostka numbers is their relation to dominance order. This order on partitions gives a sharp criterion for when a Kostka number can be nonzero. It reflects the fact that the tableau constraints force the shape to dominate the weight in an appropriate sense.
2.4.1 Necessary and sufficient conditions for positivity
A classical result states that \(K_{\lambda \mu}>0\) if and only if \(\lambda\) dominates \(\mu\). When this condition fails, no semistandard tableau of the given shape and weight exists. When it holds, at least one tableau can be constructed.
This criterion explains why Kostka matrices are triangular when partitions are ordered by dominance. It is one of the most useful structural facts about the numbers.
3 Combinatorial interpretations
Kostka numbers admit several equivalent combinatorial descriptions. These viewpoints often make different aspects of the same quantity more transparent and allow the use of diverse counting techniques.
3.1 Tableau counting interpretation
The most direct interpretation is as the number of semistandard Young tableaux of fixed shape and weight. This description is elementary and intuitive, and it is the one most commonly used in definitions. It also makes the positivity of the numbers immediate.
3.2 Lattice word formulations
Kostka numbers can also be described using lattice words, which are sequences satisfying ballot-type inequalities. In this viewpoint, tableaux are encoded by reading words, and the semistandard conditions translate into constraints on those words. This reformulation is useful in proving identities and in relating Kostka numbers to other tableau statistics.
3.3 Crystal and path models
In Lie-theoretic combinatorics, Kostka numbers appear in crystal graph models and lattice path models. These frameworks reinterpret tableaux as nodes or paths in a graph with graded structure. The counting then reflects multiplicities in a representation-theoretic model while preserving the same underlying combinatorics.
3.4 Littlewood–Richardson-type viewpoints
Although Kostka numbers are distinct from Littlewood–Richardson coefficients, they share a similar tableau-based flavor. Both arise from structured fillings of Young diagrams and both encode multiplicity information. In some settings, Kostka numbers can be viewed as special cases or limiting coefficients within broader tableau calculus.
4 Connections with symmetric functions
Kostka numbers are fundamental coefficients in the algebra of symmetric functions. They describe how one basis is expressed in terms of another and thereby encode transitions among combinatorially meaningful expansions.
4.1 Schur functions
Schur functions are a distinguished basis of symmetric functions indexed by partitions. They play a central role in combinatorics, geometry, and representation theory. Kostka numbers appear naturally when Schur functions are expanded in the monomial basis.
4.1.1 Expansion in the monomial basis
For each partition \(\lambda\), the Schur function \(s_\lambda\) can be written as a sum of monomial symmetric functions \(m_\mu\) with coefficients \(K_{\lambda \mu}\). These coefficients are precisely the Kostka numbers. This expansion gives one of the most important algebraic meanings of the numbers.
4.1.2 Kostka matrix
If one arranges the coefficients \(K_{\lambda \mu}\) into a matrix indexed by partitions, the result is called the Kostka matrix. With a suitable ordering, this matrix is upper triangular with ones on the diagonal. That structure makes it invertible and underlies many computational and theoretical applications.
4.2 Transition matrices between symmetric function bases
Kostka numbers also appear in transitions between other bases related to Schur functions and monomial functions. Because symmetric function bases are connected by linear change-of-basis relations, the Kostka matrix is one of several matrices encoding such transformations. Its entries reflect the combinatorial complexity of moving between basis elements.
4.3 Inverse Kostka matrix
The inverse of the Kostka matrix expresses monomial symmetric functions in terms of Schur functions, with alternating signs in general. Unlike the Kostka numbers themselves, the inverse coefficients are not all nonnegative. They are important in algebraic manipulations but do not usually admit as direct a counting interpretation.
4.4 Stability and specialization
Kostka numbers are stable under the addition of trailing zeros to partitions, provided the total size remains unchanged. They also behave predictably under specialization of symmetric functions. These stability properties make them compatible with infinite-variable formulations and with limiting procedures in symmetric function theory.
5 Representation-theoretic significance
Kostka numbers have deep interpretations in the representation theory of symmetric groups and general linear groups. In this context, they measure the multiplicities of certain weight spaces or basis components.
5.1 Symmetric group representations
Schur functions correspond to irreducible polynomial representations in a way that also links to representations of symmetric groups through the theory of Young diagrams and Specht modules. Kostka numbers help describe how combinatorial bases relate to these representations. They provide a bridge between tableau enumeration and module structure.
5.2 Polynomial representations of general linear groups
For polynomial representations of the general linear group, Schur functions encode characters, and Kostka numbers appear as multiplicities in weight decompositions. The tableaux counted by \(K_{\lambda \mu}\) correspond to basis vectors in these representations. This gives a concrete combinatorial handle on abstract representation-theoretic data.
5.3 Weight multiplicities
A Kostka number can be interpreted as a weight multiplicity in a highest-weight representation. In this setting, the shape \(\lambda\) specifies the highest weight, while \(\mu\) labels a lower weight space. The number then records how often that weight occurs.
5.4 Highest-weight theory
Highest-weight theory provides the structural framework in which Kostka numbers naturally arise. The triangularity and dominance properties mirror the ordering of weights in such representations. This perspective explains why tableau counts and character coefficients are so closely linked.
6 Algorithms and computation
Because Kostka numbers are discrete and often finite in size, they can be computed by a variety of algorithmic methods. The most suitable approach depends on the size of the partitions and the intended application.
6.1 Direct tableau enumeration
For small shapes, the most straightforward method is to list all semistandard tableaux of the given shape and weight. This is conceptually simple but becomes impractical as the size grows. Still, it is useful for verifying identities and generating examples.
6.2 Recursive formulas
Recursive relations exploit the removal of boxes, the structure of semistandard fillings, or branching rules from representation theory. Such recursions can reduce a large problem to smaller ones. They are particularly effective when combined with dominance order and triangularity.
6.3 Determinantal and generating-function methods
Kostka numbers can sometimes be extracted from determinantal formulas or generating-function expansions. These methods are more algebraic and may compute entire families at once rather than individual values. They are especially valuable when studying structural patterns across many partitions.
6.4 Software and computational approaches
Computer algebra systems and specialized combinatorics packages can calculate Kostka numbers and related symmetric-function coefficients. These tools often implement tableau algorithms, recursion, and basis conversion routines. They make it practical to study examples of moderate size and to experiment with identities.
7 Variants and generalizations
The basic Kostka numbers are part of a larger family of refined quantities. Many generalizations introduce grading, deformation parameters, or broader combinatorial objects while preserving the same basic philosophy of tableau counting and basis transition.
7.1 Kostka–Foulkes polynomials
Kostka–Foulkes polynomials refine Kostka numbers by introducing a parameter \(q\). They interpolate between combinatorial and representation-theoretic information and arise in the theory of Hall–Littlewood polynomials. Evaluating them at special values can recover classical Kostka numbers.
7.2 \(q\)-analogues and graded multiplicities
Many generalizations replace ordinary counts by graded counts, where tableaux contribute according to a statistic. These \(q\)-analogues encode finer information than the ungraded numbers. They often appear in the study of filtered or graded representations.
7.3 Generalized Kostka numbers
Generalized Kostka numbers extend the classical setting to other shapes, other root systems, or other families of symmetric functions. They may count more elaborate fillings or track additional data. The guiding idea remains the same: to quantify how one natural basis decomposes into another.
7.4 Super and affine extensions
In supersymmetric and affine settings, Kostka-type coefficients can be defined for more intricate algebraic structures. These versions often require modified tableaux rules or new combinatorial models. They broaden the reach of the original concept while retaining its role as a multiplicity and transition coefficient.
8 Examples
Examples are especially helpful for understanding how Kostka numbers reflect shape, weight, and dominance conditions. Small cases also illustrate the relationship between tableau enumeration and symmetric function expansions.
8.1 Small partitions and explicit values
For the partition \((1)\), there is only one tableau of shape \((1)\) and weight \((1)\), so the corresponding Kostka number is \(1\). For shape \((2)\), the tableaux of weights \((2)\) and \((1,1)\) behave differently depending on the semistandard conditions, and the values can be checked directly. In each case, the count is small enough to verify by hand.
For a shape such as \((2,1)\), several distinct weights may occur, but only those dominated by \((2,1)\) yield nonzero counts. This provides a simple illustration of the dominance criterion.
8.2 Kostka matrices for low degree
In low degree, Kostka matrices are small and triangular. Their diagonal entries are all \(1\), and many entries above the diagonal vanish because of dominance restrictions. Such matrices provide concrete examples of the basis-change relations among Schur and monomial symmetric functions.
These low-degree matrices are often used in teaching and in computational checks. They reveal the general pattern without requiring advanced theory.
8.3 Worked tableau examples
Consider a tableau of shape \((2,1)\) with entries \(1,1,2\). The row and column conditions allow a valid semistandard filling in which the top row contains two \(1\)s and the lower box contains \(2\). This tableau contributes to the relevant Kostka number for that shape and weight.
As another example, a shape \((3,1)\) with weight \((2,1,1)\) may admit several tableaux, depending on the placement of the repeated entry. The number of valid fillings can be obtained by checking the monotonicity rules systematically. Such examples show how the combinatorics of tableaux translates directly into numerical coefficients.