20240429
Kostka coefficients
The Kostka coefficients appear in the monomial expansion of Schur functions, and the Schur expansion of the complete homogeneous symmetric functions:
\[ \schurS_\lambda = \sum_\mu K_{\lambda\mu} \monomial_\mu, \qquad \completeH_\mu = \sum_\mu K_{\lambda\mu} \schurS_\lambda. \]Hence, $K_{\lambda\mu}$ is equal to the number of semistandard Young tableaux of shape $\lambda$ and content $\mu.$
From this, we immediately have that $K_{\lambda\lambda}=1,$ $K_{\lambda,1^n} = f^{\lambda}$ and that $K_{\lambda\mu}=0$ unless $\lambda \trianglerighteq \mu$ in dominance order.
Below is the matrix $(K_{\lambda\mu})$ and its inverse, with rows and columns indexed by the partitions 5, 41, 32, 311, 221, 2111, 11111.
\[ (K_{\lambda\mu})= \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 2 & 2 & 3 & 4 \\ 0 & 0 & 1 & 1 & 2 & 3 & 5 \\ 0 & 0 & 0 & 1 & 1 & 3 & 6 \\ 0 & 0 & 0 & 0 & 1 & 2 & 5 \\ 0 & 0 & 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} , \quad (K_{\lambda\mu})^{1}= \begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 2 \\ 0 & 0 & 1 & 1 & 1 & 2 & 2 \\ 0 & 0 & 0 & 1 & 1 & 1 & 3 \\ 0 & 0 & 0 & 0 & 1 & 2 & 3 \\ 0 & 0 & 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} \]See the overview of transition matrices for a combinatorial interpretation of the entries in the inverse matrix.
Kostka coefficients from Littlewood–Richardson
For skew Kostka coefficients, we have the equality
\[ K_{\lambda/\mu,\nu} = \langle \schurS_{\mu} \cdot \completeH_{\nu} , \schurS_\lambda \rangle = \langle \schurS_{\mu} \cdot \schurS_{(\nu_1)} \dotsm \cdot \schurS_{(\nu_\ell)} , \schurS_\lambda \rangle \]and the latter is a Littlewood–Richardson coefficient $c^{\tau}_{\sigma\lambda}$ where $\tau/\sigma$ is the skew shape obtained by "concatenating" $\ell$ horizontal strips of sizes given by $\nu,$ and the shape $\mu.$ See [p.338, Sta01] for proof.
Recursions for Kostka coefficients
From the definition of Kostka coefficients, there is a straightforward recursion. This recursion is equivalent to the Pieri rule. Let $\mu = (\mu_1,\dotsc,\mu_\ell)$ be a partition with $\ell \geq 2$ parts, and let $\mu^{(\ell)}$ denote the partition $(\mu_1,\dotsc,\mu_{\ell1})$ (this is $\mu$ with the last part removed). Then
\[ K_{\lambda \mu} = \sum_{\nu} K_{\nu,\mu^{(\ell)}} \]where the sum is taken over all partitions $\nu$ of size $\lambda\mu_\ell,$ such that $\lambda/\nu$ is a horizontal strip.
See also the recursion for Kostka–Foulkes polynomials.
In [p.327, Mac95], the following recursion is described. In fact, it generalizes to Jack polynomials.
First, let $d(\lambda)\coloneqq \partitionN(\lambda')\partitionN(\lambda).$ Let $\mu$ be a partition of length $\ell.$ Then we have the recursion
\[ K_{\lambda, \mu} = \frac{1}{ d(\lambda)  d(\mu)} \sum_{1 \leq i \lt j \leq \ell} \sum_{1 \leq r \leq \mu_j} (\mu_i  \mu_j) K_{\lambda, (\mu+r \evec_i  r \evec_j)^*} \]where $(\mu+r \evec_i  r \evec_j)^*$ denotes the partition obtained from $\mu$ by decreasing entry $i$ by $r,$ and increasing entry $j$ by $r,$ and rearrange in decreasing fashion. The initial conditions are given by $K_{\mu, \mu}=1,$ and $K_{\lambda, \mu}=0$ unless $\lambda \geq \mu$ in dominance order.
Recursions for inverse Kostka coefficients
A convenient recursive formula for the entries in $(K_{\lambda\mu})^{1}$ is given in [ER90].
Let $\lambda = (r_1^{j_1}, r_2^{j_2},\dotsc,r_k^{j_k})$ where $r_1 \lt r_2 \lt \dotsb.$ Let $\mu = (\mu_1,\dotsc,\mu_\ell)$ in increasing order. We have that
\[ K^{1}_{\lambda\mu} = \sum_{\substack{1 \leq j \leq d \\ r_j = \mu_i+j1}} (1)^{i1} K^{1}_{\lambda[j], (\mu_11,\mu_21,\dotsc,\mu_{i1}1,\mu_{i+1},\dotsc,\mu_{\ell})} \]where $\lambda[j]$ denotes the partition obtained from $\lambda$ with one part equal to $j$ removed.
An implementation of this recursion in Mathematica can be found in this github file.
In [Car98], a $t$version of the Eğecioğlu–Remmel result is proved, where $(K_{\lambda\mu}(t))^{1}$ is given a combinatorial interpretation.
A similarlooking but different recursion is given in [Thm. 3, Dua03].
Let $\lambda = (r_1^{j_1}, r_2^{j_2},\dotsc,r_k^{j_k})$ where $r_1 \lt r_2 \lt \dotsb.$ Let $\mu = (\mu_1,\dotsc,\mu_\ell)$ in increasing order. We have that
\[ K^{1}_{\lambda\mu} = \sum_{r_j \geq \mu_\ell} (1)^{r_j\mu_\ell} \sum_{\nu} K^{1}_{\lambda[j], \nu} \]where $\lambda[j]$ denotes the partition obtained from $\lambda$ with one part equal to $j$ removed, and the inner sum is taken over all $\nu$ such that $\mu/\nu$ is a vertical strip of size $r_j\mu_\ell.$
See also [WZ18], where the coefficients appearing in
\[ \schurS_\mu \hallLittlewoodP_\nu(t) = \sum_\lambda \bar{K}^\lambda_{\mu\nu}(t) \schurS_{\nu} \]are studied.
The Kostant partition function
See Harris, Insko and Omar [HIO18] for a short introduction.
Let $\evec_{ij}$ denote the vector with $1$ at index $i$ and $1$ at index $j$ and remaining entries equal to $0.$ We refer to this collection of vectors as positive roots or just roots for short. Given an integer vector $w$ of length $n,$ let Kostant's partition function $\kostantP(w)$ be the number of solutions to
\[ w = \sum_{(i,j) \in \binom{[n]}{2}} a_{ij} \evec_{ij} \]with $a_{ij}\geq 0$ being nonnegative integers. This is the definition in root system type $A_n$ — there are analogues of the partition function in other types. Clearly $\kostantP(w)=0$ unless $w_1+w_2+\dotsb+w_n=0.$
There is a $q$analogue of $\kostantP(w),$ denoted $\kostantP_q(w)$ introduced by Lustzig [Lus83]. It is defined as
\[ \kostantP_q(w) \coloneqq \sum_{ (a_1,\dotsc,a_\ell) } q^{a_1+\dotsb + a_\ell} \]where we sum over all nonnegative solutions $(a_1,\dotsc,a_\ell)$ that expresses $w$ as a nonnegative linear combination of roots.
From the definition above, we have that
\[ \prod_{1 \leq i \lt j \leq n} \left( 1  q\frac{x_i}{x_j} \right)^{1} = \sum_{ w \in \setZ^n } \kostantP_q(w) \xvec^w. \]This has a close relationship with the Jacobi–Trudi identity, see the excellent introduction in [DLT94].
Let $w=(5,2,7),$ and our roots are $\evec_{12},$ $\evec_{13}$ and $\evec_{23}.$ We have that $\kostantP(w) = 6,$ since there are $6$ solutions with nonnegative coefficients:
\[ 052, 143, 234, 325, 416, 507 \]For example, $(5,2,7) = 3\evec_{12} + 2\evec_{13} + 5\evec_{23}.$ Furthermore,
\[ \kostantP_q(w) = q^{12}+q^{11}+q^{10}+q^9+q^8+q^7. \]
KostantPartitionFunction[w_List] /; Tr[w] != 0 = {};
KostantPartitionFunction[w_List] := Module[
{a, n = Length[w], roots, idx, vars, sol},
idx = Subsets[Range[n], {2}];
roots = Table[SparseArray[ss>{1,1},{n}], {ss,idx}];
vars = a /@ idx;
sol = Solve[
And @@ Join[Thread[vars >= 0],
Thread[w == vars.roots]]
, vars, Integers];
If[Length[sol] == 0, {}, vars /. sol]
];
KostantPartitionFunction[{5,2,7}]
Kostant's partition function is related to juggling sequences, see [BHHMS20].
The number of summands used in expressing $w,$converges to a Gaussan distribution, see [HRS19]. Similar properties for other root systems hold.
Kostant partition function in general types
In more generality, let $\Phi^+ \subset \Phi$ be a set of positive roots in a root system. The Kostant partition function for $\Phi^+$ is defined via the relation
\begin{equation*} \prod_{\alpha \in \Phi^+} \frac{1}{1e^\alpha} = \sum_{w} \kostantP(w) e^w. \end{equation*}Note that $e$ is just a formal variable in this context, but with this convention, $e^{\alpha} e^{\beta} = e^{\alpha + \beta}.$ The $q$analogue is then defined via
\begin{equation*} \prod_{\alpha \in \Phi^+} \frac{1}{1q e^\alpha} = \sum_{w} \kostantP_q(w) e^w. \end{equation*}Thus, the coefficient $[q^j]\kostantP_q(w)$ count the number of ways to express $w$ as a sum of exactly $j$ positive roots.
In [Ras04b], a different $q$analogue, defined via
\begin{equation*} \prod_{\alpha \in \Phi^+} \frac{1+(q1)e^\alpha}{1 e^\alpha} = \sum_{w} \kostantP^*(w;q) e^w, \end{equation*}is considered. Then $[q^j]\kostantP^*(w;q)$ is the number ways to express $w$ as a sum of positive roots, where exactly $j$ roots appear with a positive multiplicity.
See http://de.arxiv.org/pdf/1111.6648.pdf for a connection with Fibonacci numbers.
Kostka coefficients from Kostant's partition function
Let $\lambda$ and $\mu$ be integer partitions of $n.$ Then the Kostant's multiplicity formula (see [(1.1.5), Kos59]) states that
\[ K_{\lambda,\mu} = \sum_{\sigma \in \symS_n} (1)^{\length(\sigma)} \kostantP\left( \sigma(\lambda + \rho)  (\mu+\rho) \right) \]where $\rho = (n1,n2,\dotsc,2,1,0).$ This formula is used to prove polynomiality of stretched Kostka coefficients, see [BGR04]. Note that the above formula is really not an efficient way to compute Kostka coefficients.
The Kostka–Foulkes polynomials $K_{\lambda,\mu}(q)$ can be computed via the $q$analogue:
\[ K_{\lambda,\mu}(q) = \sum_{\sigma \in \symS_n} (1)^{\length(\sigma)} \kostantP_q\left( \sigma(\lambda + \rho)  (\mu+\rho) \right). \]We have that
\[ \completeH_\mu(\xvec) = \sum_{\alpha \in \setZ^n} \kostantP(\alpha)\schurS_{\mu + \alpha}(\xvec). \]Kostka coefficients from contingency tables
Let $\lambda$ and $\mu$ be partitions of lengths at most $n$ and let and $\rho = (n1,n2,\dotsc,2,1).$ Moreover, let $M_\alpha[\beta]$ be the number of nonnegative integer matrices with row sums given by $(\alpha_1,\dotsc,\alpha_n)$ and column sums given by $(\beta_1,\dotsc,\beta_n).$ Thus, $M_\alpha[\beta]$ count certain contingency tables.
By using the Jacobi–Trudi identity, it is then straightforward to derive the following identity for skew Kostka coefficients:
\[ K_{\lambda/\mu,\nu} = [\monomial_\nu] \schurS_{\lambda/\mu} = \sum_{\sigma \in \symS_n} (1)^\sigma M_\nu[\sigma(\lambda+\rho)  (\mu+\rho)]. \]We do the proof in the nonskew case. The skew case is similar. Recall that for $\lambda = (\lambda_1,\dotsc,\lambda_\ell),$ the Jacobi–Trudi identity states that
\begin{equation} \schurS_\lambda(\xvec) = \left \completeH_{\lambda_i  i + j}(\xvec) \right_{1 \leq i,j \leq \ell} . \end{equation}By letting $\rho \coloneqq (n1,n2,\dotsc,2,1,0),$ we can write this as
\begin{equation} \schurS_\lambda(\xvec) = \left \completeH_{\lambda_i + \rho_i  \rho_j}(\xvec) \right_{1 \leq i,j \leq \ell} \end{equation}Expanding the determinant, we recognize this as
\begin{equation} \schurS_\lambda(\xvec) = \sum_{\sigma \in \symS_n} (1)^\sigma \prod_{j=1}^{\ell} \completeH_{\sigma(\lambda+\rho)_j  \rho_j}(\xvec) = \sum_{\sigma \in \symS_n} (1)^\sigma \completeH_{\sigma(\lambda+\rho)  \rho}(\xvec). \end{equation}Recall now that
\[ \completeH_\alpha(\xvec) = \sum_{\beta} M_\alpha[\beta] m_\beta(\xvec), \]where $M_\alpha[\beta]$ count the number of nonnegative integer matrices with row sums given by $\alpha$ and column sums given by $\beta.$ This observation completes the proof.
Littlewood–Richardson coefficients from the partition function
Let $\lambda,$ $\mu$ and $\nu$ be partitions of length at most $k,$ and such that $\lambda+\mu = \nu.$ Set
\[ \delta \coloneqq \frac{1}{2}(k1,k3,\dotsc,3k,1k). \]We have that the Littlewood–Richardson coefficient $c^{\nu}_{\lambda \mu}$ is given by
\[ c^{\nu}_{\lambda \mu} = \sum_{\sigma, \tau \in \symS_k} (1)^{\inv(\sigma \tau)} \cdot \kostantP\left( \sigma(\lambda+\delta) + \tau(\mu+\delta)  (\nu+2\delta) \right). \]
LittlewoodRichardson[lam_List, mu_List, nu_List] :=
Module[{perms, nlam, nmu, nnu, k, delta},
k = Max[Length /@ {lam, mu, nu}];
perms = Permutations@Range[k];
{nlam, nmu, nnu} = PadRight[#, k] & /@ {lam, mu, nu};
delta = 1/2 Table[j, {j, k  1, (k  1), 2}];
Sum[
With[{
vec = (nlam + delta)[[sigma]]
+
(nmu + delta)[[tau]]

(nnu + 2 delta)},
(1)^Inversions[sigma[[tau]]]
Length[KonstantPartitionFunction[vec]]
]
, {sigma, perms}, {tau, perms}]
];
(* This should return 1 *)
LittlewoodRichardson[{2, 2}, {3}, {4, 2, 1}]
(* This should return 2 *)
LittlewoodRichardson[{2, 1, 1}, {3, 1}, {4, 2, 1, 1}]
A similar expression for the Schur P structure coefficients can be found in [Thm. 6.2.5, Ras04b]. This can perhaps be seen as a type $B$ analog of Steinbergs formula.
In [BZ88] the authors attributes the following formula to B. Kostant:
Let $\lambda,\mu,\nu$ be partitions of length at most $\ell,$ such that $\nu=\lambda+\mu.$ Then
\begin{equation} c^{\nu}_{\lambda \mu} = \sum_{\sigma \in \symS_\ell} \varepsilon(\sigma) K_{\mu, \sigma(\nu+\rho)(\lambda+\rho)}, \end{equation}where $\rho = \tfrac12 (\ell1,\ell3,\dotsc,1\ell).$
Shrivastava [Shr22] provides a modern proof of this formula.
A generalization of this formula exists for Gromow–Witten invariants, which show up in the study of toric Schur functions.
Stretched Kostka coefficients
See also stretched Littlewood–Richardson coefficients.
By using the Gelfand–Tsetlin polytope model for semistandard Young tableaux, we can obtain the Kostka coefficients $K_{\lambda,\mu}$ as the number of lattice points in certain nonintegral (some vertices might not have integer coordinates) polytopes. This implies that the map $k \mapsto K_{k\lambda,k\mu}$ is a quasipolynomial in $k.$ However, we have the stronger statement, due to Derksen and Weyman [DW02]:
The map $k \mapsto K_{k\lambda,k\mu}$ is a polynomial in $k.$
In fact, this follows from the analogous statement for Littlewood–Richardson coefficients.
The proof idea (both for Kostka and Littlewood–Richardson coefficients) is to express $K_{k\lambda,k\mu}$ using Kostant's partition function. It then remains to prove that for fixed vectors $\alpha \in \setN^n$ and $\beta \in \setZ^n,$ the map $k \mapsto \kostantP\left( k \alpha + \beta \right)$ is a polynomial for large enough $k.$ This fact follows [Thm. 1, Stu95] together with the fact that the vector partition function $\phi_A$ in type $A$ (another name for $\kostantP$) arises from a unimodular matrix (all minors have determinant in $\{1,0,1\}$). Unimodularity for the matrix corresponding to Kostant's partition function follows easily from [Appendix, HT57].
Flagged skew Kostka coefficients can be expressed using contingency tables. From this expression, polynomiality also follows, see [AO23].
Kostka–Foulkes polynomials from charge
For an excellent background on charge, see [Chapter 2.4, But94].
Here is a longer explanation on how to compute the coefficients $K_{\lambda,\mu}(q),$ the Kostka–Foulkes polynomials by using charge. These coefficients appear in the expansion of Schur polynomials into Hall–Littlewood polynomials. The combinatorial model using charge was first described by Lascoux and Schützenberger in [LS78].
First we need to introduce the charge of a permutation. For $\sigma \in \symS_k,$ we let
\begin{equation*} \charge(\sigma) \coloneqq \maj(\rev(\sigma^{1})) = \sum_{i \notin \DES(\sigma^{1})} (ki). \end{equation*}For example,
\[ \charge(198423765) = \maj(\rev(156498732) ) = \maj(237894651) = 20. \]The cocharge of a permutation, $\cocharge(\pi)$ is defined as $\binom{n}{2}\charge(\pi).$
Computing $\cocharge(198423765)$ can be done as follows. Write the permutation and write a 0 as a subscript for $1.$
\[ 1_0\; 9\; 8\; 4\; 2\; 3\; 7\; 6\; 5 \]We then move to the next larger element in the permutation with no subscript. If moving to the left, the subscript is increased by one, otherwise it stays the same. The first two steps here is to the right, so the subscripts are set to $0.$
\[ 1_0\; 9\; 8\; 4\; 2_0\; 3_0\; 7\; 6\; 5 \]We then move to the left,
\[ 1_0\; 9\; 8\; 4_1\; 2_0\; 3_0\; 7\; 6\; 5, \]and then to the right:
\[ 1_0\; 9\; 8\; 4_1\; 2_0\; 3_0\; 7\; 6\; 5_1. \]Proceeding in this fashion, we arrive at
\[ 1_0\; 9_5\; 8_4\; 4_1\; 2_0\; 3_0\; 7_3\; 6_2\; 5_1. \]The cocharge is now the sum of the subscripts, $0+5+4+1+0+0+3+2+1 = 16.$ This agrees with the fact that $16+20 = 36 = \binom{9}{2}.$
Standard subwords
Given a word $w$ with content $\mu \vdash n,$ partition its entries into standard subwords as follows. Start from the right of $w$ and mark the first occurrence of $1.$ Proceed to the left and mark the first occurrence of $2,$ then $3$ and so on, wrapping around the end if nessecary, until $\mu'_1$ entries have been marked. This subword is the first standard subword of $w.$ Remove this subword, and repeat the process to find the second standard subword, of length $\mu'_2.$
For example, the first standard subword in $w = 2 1 1 2 3 5 4 3 4 1 1 2 2 3$ has been underlined.
\[ 2, 1, 1, \underline{2}, 3, \underline{5}, 4, 3, \underline{4}, 1, \underline{1}, 2, 2, \underline{3}. \]In total, we have four standard subwords in $w,$ with corresponding charge values
\[ \charge(25413) = 3,\quad \charge(2431)=2 \quad \charge(132)=2 \quad \charge(12) = 1, \]and we define $\charge(w)$ as the sum of the charge values of the standard subwords. Hence $\charge(w) = 8$ for our particular word.
Charge of SSYT
For a semistandard Young tableau $T \in \SSYT(\lambda,\mu),$ the reading word of $T,$ $\rw(T)$ is given by concatenating the rows of $T,$ starting with the bottommost row. We then define $\charge(T) = \charge(\rw(T)),$ and the Kostka–Foulkes polynomial $K_{\lambda,\mu}(q)$ may be computed as
\[ K_{\lambda,\mu}(q) = \sum_{T \in \SSYT(\lambda,\mu)} q^{\charge(T)}. \]Similarly, the modified Kostka–Foulkes polynomials are defined as
\[ \tilde{K}_{\lambda,\mu}(q) = \sum_{T \in \SSYT(\lambda,\mu)} q^{\cocharge(T)}. \]We have the relation
\[ \tilde{K}_{\lambda,\mu}(q) = q^{\partitionN(\mu)} K_{\lambda,\mu}(q^{1}). \]We shall now compute $K_{421,3211}(q).$ There are four tableaux in $\SSYT(421,3211)$:
$1$  $1$  $1$  $4$ 
$2$  $2$  
$3$ 
$1$  $1$  $1$  $3$ 
$2$  $2$  
$4$ 
$1$  $1$  $1$  $2$ 
$2$  $4$  
$3$ 
$1$  $1$  $1$  $2$ 
$2$  $3$  
$4$ 
The corresponding standard subwords and charge values are given by
\begin{equation*} \underset{1+0+0}{ 3214,\; 21,\; 1 } \qquad % \underset{2+0+0}{4213,\; 21,\; 1 } \qquad % \underset{1+1+0}{ 3241,\; 12,\; 1} \qquad % \underset{2+1+0}{4231,\; 12,\; 1} \end{equation*}Hence, $K_{\lambda\mu}(q) = q+2q^2+q^3.$
Here are all $K_{\lambda,\mu}(q)$ for partitions of size $4.$ The rows are indexed by $\lambda.$
$\;$  $\textbf{4}$  $\textbf{31}$  $\textbf{22}$  $\textbf{211}$  $\textbf{1111}$  
$\textbf{4}$  $1$  $0$  $0$  $0$  $0$  
$\textbf{31}$  $q$  $1$  $0$  $0$  $0$  
$\textbf{22}$  $q^2$  $q$  $1$  $0$  $0$  
$\textbf{211}$  $q^3$  $q^2+q$  $q$  $1$  $0$  
$\textbf{1111}$  $q^6$  $q^5+q^4+q^3$  $q^4+q^2$  $q^3+q^2+q$  $1$  
Properties of charge
The elementary Knuth transforms are transformations on three adjacent letters on words. We allow the transformations $yzx \leftrightarrows yxz $ whenever $x \lt y\leq z$ and $xzy \leftrightarrows zxy$ whenever $x \leq y \lt z.$ Two words are Knuthequivalent, denoted $\equiv$ if one can obtain one from the other via a sequence of elementary Knuth transforms. See also the close relationship with the Robinson–Schensted–Knuth correspondence.
For words of partition weight, we have some extra nice properties: Each equivalence class contains a unique word which is the reading word of a semistandard Young tableau. Furthermore, one can show that $w \equiv w'$ then $\charge(w)=\charge(w'),$ see [Cor. 2.4.38, But94].
Charge on words is the unique statistic with the following properties:
 $\charge(\emptyset) = 0,$
 $\charge(w) = \charge(\sigma\cdot w),$ where $\sigma$ act via Lascoux–Schützenberger involutions,
 if $x \neq 1$ and $wx$ has partitioncontent, then $\charge(wx) = \charge(xw)+1,$
 if $w1^m$ has partitioncontent and $w$ contains no ones, then $\charge(w1^m) = \charge(w),$
 if $w$ and $w'$ are Knuthequivalent, then $\charge(w) = \charge(w').$
This is stated as above in [p.54, Nel05].
One can also obtain the charge via crystal operators [Pat21].
Skew Kostka–Foulkes polynomials
The skew Kostka–Foulkes polynomials $K_{\lambda/\mu,\nu}(q)$ are defined as the coefficients in the expansion
\[ \schurS_{\lambda/\mu}(\xvec) = \sum_{\nu}K_{\lambda/\mu,\nu}(q) \hallLittlewoodP_{\nu}(\xvec;q). \]One can show that the above formula generalizes, see [Corr. 2.5.8, But94].
\[ K_{\lambda/\mu,\nu}(q) = \sum_{T \in \SSYT(\lambda/\mu,\nu)} q^{\charge(T)}. \]One can also use rigged configurations to compute Kostka–Foulkes polynomials in an efficient manner.
Cyclage
In [LS81], Lascoux and Schützenberger introduce the notion of cyclage. Let $\mu$ be a partition, and consider the set $\SSYT(\cdot,\mu) \coloneqq \bigcup_\lambda \SSYT(\lambda,\mu).$ That is, the set of all semistandard Young tableaux with content $\mu.$ They define a poset structure on $\SSYT(\cdot,\mu)$ via the covering relations
\[ T \prec T' \text{ if there is $i\geq 2$ such that } \rw(T)\cdot i \equiv i\cdot \rw(T'), \]where $\equiv$ denotes Knuth equivalence. This is in fact a graded poset, whose grading is given by cocharge. See [Section 5.6, Lot02] for more properties of cyclage.
The charge is displayed on the right hand side of each tableau.
Catabolism
Catabolism is defined in [Exercise 5.6.1, Lot02] as follows. Given a tableau $T$ of shape $\lambda,$ let $F$ be the first row of length $\lambda_1$ and $R$ be the tableau consisting of the remaining rows. Perform row insertion on $F \cdot \rw(R).$ This gives a new tableau with the same weight as $T,$ and charge has increased by $\lambda\lambda_1.$ Tableaux with only one row are the only fixed points under catabolism.
In this example, we start with
$1$  $1$ 
$2$  $3$ 
$4$ 
The top row is moved to the bottom, to create a skew shape.
$2$  $3$  
$4$  
$1$  $1$ 
We then perform jeudetaquin to get a straight shape.
$2$  $3$  
$4$  
$1$  $1$ 
$2$  $3$  
$1$  $4$  
$1$ 
$2$  $3$  
$1$  $1$  $4$ 
$1$  $2$  $3$  
$1$  $4$ 
$1$  $1$  $2$  $3$ 
$4$ 
$1$  $1$  $2$  $3$ 
$4$ 
The final tableau is the result of catabolism. This procedure is equivalent with the one described above.
The charge is displayed on the right hand side of each tableau.
Identities
Using the Robinson–Schensted–Knuth correspondence, one can show that
\[ \sum_{\lambda \vdash n} K_{\lambda \mu} K_{\lambda \nu} = N_{\mu\nu}, \]where $N_{\mu\nu}$ is the number of $n \times n$matrices with entries in $\setN,$ row sums are determined by $\mu$ and columnsums are determined by $\nu.$
There is a $q$analogue of this in the case $\nu=1^n,$ see [Corolloary 1.3, Kir00].
\[ \sum_{\lambda \vdash n} K_{\lambda \mu} K_{\lambda, 1^n}(q) = q^{n(\mu')} \qbinom{n}{\mu_1,\dotsc,\mu_\ell}_q. \]For a partition $\lambda$ let
\[ \lambda^{(i)} \coloneqq (\lambda_1+1,\lambda_2+1,\dotsc,\lambda_{i1}+1,\lambda_{i+1},\dotsc,\lambda_{\ell}). \]Furthermore, $\lambda^{[i]}\coloneqq (\lambda_{i+1},\dotsc,\lambda_\ell).$ With these definitions, we have the following recursion for Kostka–Foulkes polynomials:
\[ K_{\lambda\mu}(q) = \sum_{i=1}^{\mu_1} (1)^{i1} q^{\lambda_1\mu_1i+1} \sum_{\tau^i} K_{\tau^i,\mu^{[1]}}(q) \]where the sum runs over all partitions $\tau^i$ such that $\tau^i/\lambda^{(i)}$ are horizontal $(\lambda_1\mu_1i+1)$strips.
Parabolic Kostka polynomials
The parabolic Kostka polynomials $K_{\lambda,R}(q)$ (or generalized Kostka polynomials) generalize the Kostka–Foulkes polynomials. The following definition appear in [SW00].
Let $R = (R^1,\dotsc,R^k)$ be a sequence of partitions, and let $\lambda$ be a partition such that $\lambda = \sum_j R^j.$ Let $\gamma$ be the partition whose parts is the multiset of parts of the $R^j.$ Furthermore, let $\eta_j \coloneqq \length(R^j)$ and $N \coloneqq \sum_j \eta_j.$ Let $M$ be the $N\times N$ matrix with diagonal blocks of size $\eta_j,$ and let $R^+_\eta \subset [N]^2$ be the subset of entries in $M$ strictly above the blocks.
Let $R=((4,4),(3),(1,1,1)).$ Then $\eta = (2,1,3),$ $N=6$ and $\gamma = 443111.$ The matrix $M$ is as follows where $R^+_\eta$ consists of the lightgreen boxes.
Hence,
\[ R^+_\eta = \{13,14,15,16, \; 23,24,25,26, \; 34, 35, 36 \}. \]Introduce $\kostantP^\eta_q(w),$ which is a generalization of the $q$analogue of the Kostant partition function, via the relation
\begin{equation*} \sum_{w \in \setZ^n} \kostantP^\eta_q(w) = \prod_{(i,j) \in R^+_\eta} \frac{1}{1q\frac{x_i}{x_j}}. \end{equation*}Finally, the parabolic Kostka polynomial $K_{\lambda,R}(q)$ is defined as
\begin{equation*} K_{\lambda,R}(q) = \sum_{\sigma \in \symS_n} (1)^{\length(\sigma)} \kostantP^\eta_q\left( \sigma(\lambda + \rho)  (\mu+\rho) \right), \end{equation*}where $\rho = (N1,\dotsc,2,1,0).$ It is straightforward from this definition to see that if each partition $R_i = (\mu_i),$ a single part, then $K_{\lambda,R}(q) = K_{\lambda,\mu}(q),$ the standard Kostka–Foulkes polynomial.
One can show [Prop. 8, SW00] that
\[ K_{\lambda,R}(1) = \langle \schurS_\lambda, \schurS_{R^1} \schurS_{R^2} \dotsm \schurS_{R^k} \rangle, \]which is a type of generalized Littlewood–Richardson coefficient.
Rectangular special case
When all $R^j$ are rectangles, the $K_{\lambda,R}(q)$ are Poincaré polynomials.
Several conjecture regarding this special case appear in these notes. In particular, there is a connection with LLT polynomials.
When the part sizes in the rectangles $R^j$ are weakly decreasing, we have a dominant sequence of rectangles. In this case, it is knonw that $K_{\lambda,R}(q) \in \setN[q],$ via a rigged configuration proof. A charge formula is conjectured in [Conj. 27, SW00], and later proved by M. Shimozono [Thm. 11, Shi01]. There,
\[ K_{\lambda,R}(q) = \sum_{T \in LRT(\lambda,R)} q^{\charge_R(T)} \]where $\charge_R$ is a generalization of charge, and $LRT(\lambda,R)$ is the set of certain Littlewood–Richardson tableaux. See [KS02KSS01SW99] for more background.
Atomic decomposition
http://fpsac2019.fmf.unilj.si/resources/Posters/76poster.pdf
Quantum Kostka coefficients
The quantum Kostka coefficients arises in the study of the quantum cohomology of the Grassmanian, [PR16]. A combinatorial formula for these coefficients first appeared in [BCF99].
Let $\lambda \subseteq n \times k$ and suppose $\nu$ satisfies $\nu = \lambda + m(n+k).$ Then the quantum Kostka coefficient $K_{\lambda \nu}^{k,n}$ is given by
\[ K_{\lambda \nu}^{k,n} = \sum_{\rho} \sign(\rho/\lambda) K_{\rho \nu} \]where $K_{\rho \nu}$ is a regular Kostka coefficient and the sum ranges over all partitions $\rho$ occupying at most $n$ columns, obtained by adding $m$ ribbons (each containing $(n+k)$ boxes). The sign $\sign(\rho/\lambda)$ is given by multiplying $(1)^{nwidth(r_j)}$ for all ribbons $r_j$ where the width is the number of columns the ribbon occupies.
References
 [AO23] Per Alexandersson and Ezgi Kantarci Oğuz. Cylindric Schur functions. , 2023.
 [BCF99] Aaron Bertram, Ionuţ CiocanFontanine and William Fulton. Quantum multiplication of Schur polynomials. Journal of Algebra, 219(2):728–746, September 1999.
 [BGR04] Sara Billey, Victor Guillemin and Etienne Rassart. A vector partition function for the multiplicities of $\mathfrakSL_k(\mathbbC)$. Journal of Algebra, 278(1):251–293, August 2004.
 [BHHMS20] Carolina Benedetti, Christopher R. H. Hanusa, Pamela E. Harris, Alejandro H. Morales and Anthony Simpson. Kostant's partition function and magic multiplex juggling sequences. 24(3):439–473, June 2020.
 [BJ16] Timothee W. Bryan and Naihuan Jing. An algebraic formula for the Kostka–Foulkes polynomials. arXiv eprints, 2016.
 [But94] Lynne M. Butler. Subgroup lattices and symmetric functions. American Mathematical Society, 1994.
 [BZ88] A. D. Berenstein and A. V. Zelevinsky. Tensor product multiplicities and convex polytopes in partition space. Journal of Geometry and Physics, 5(3):453–472, 1988.
 [Car98] Joaquin O. Carbonara. A combinatorial interpretation of the inverse tKostka matrix. Discrete Mathematics, 193(13):117–145, November 1998.
 [DLT94] Jacques Désarménien, Bernard Leclerc and JeanYves Thibon. HallLittlewood functions and Kostka–Foulkes polynomials in representation theory. Séminaire Lotharingien de Combinatoire [electronic only], 32:38, 1994.
 [Dua03] Haibao Duan. On the inverse Kostka matrix. Journal of Combinatorial Theory, Series A, 103(2):363–376, August 2003.
 [DW02] Harm Derksen and Jerzy Weyman. On the Littlewood–Richardson polynomials. Journal of Algebra, 255(2):247–257, 2002.
 [ER90] Ömer Eğecioğlu and Jeffrey B. Remmel. A combinatorial interpretation of the inverse Kostka matrix. Linear and Multilinear Algebra, 26(12):59–84, January 1990.
 [HIO18] Pamela E. Harris, Erik Insko and Mohamed Omar. The $q$analog of Kostant's partition function and the highest root of the simple Lie algebras. Australasian J. Combinatorics, 71:68–91, 2018.
 [HRS19] Pamela E. Harris, Margaret Rahmoeller and Lisa Schneider. On the asymptotic behavior of the $q$analog of Kostant's partition function. arXiv eprints, 2019.
 [HT57] I. Heller and C. B. Tompkins. 14 . an extension of a theorem of Dantzig's. In Linear Inequalities and Related Systems. (AM38). Princeton University Press, December 1957.
 [Kir00] Anatol N. Kirillov. New combinatorial formula for modified Hall–Littlewood polynomials. In $q$Series from a Contemporary Perspective. American Mathematical Society, 2000.
 [Kos59] Bertram Kostant. A formula for the multiplicity of a weight. Transactions of the American Mathematical Society, 93(1):53–73, 1959.
 [KS02] Anatol N. Kirillov and Mark Shimozono. A generalization of the Kostka–Foulkes polynomials. Journal of Algebraic Combinatorics, 15(1):27–69, 2002.
 [KSS01] Anatol N. Kirillov, Anne Schilling and Mark Shimozono. Various representations of the generalized Kostka polynomials. In The Andrews Festschrift. Springer Berlin Heidelberg, 2001.
 [Lot02] M. Lothaire. Algebraic combinatorics on words. Cambridge University Press, 2002.
 [LS78] Alain Lascoux and MarcelPaul Schützenberger. Sur une conjecture de H. O. Foulkes. C. R. Acad. Sci. Paris Sér. AB, 286(7):A323–A324, 1978.
 [LS81] Alain Lascoux and MarcelPaul Schützenberger. Le monoïde plaxique (proc. colloqu. naples 1978). Quad. Ricerca Sci., 109, 1981.
 [Lus83] George Lusztig. Singularities, character formulas, and a $q$analog of weight multiplicities. In Analyse et topologie sur les espaces singuliers (IIIII)  6  10 juillet 1981. Société mathématique de France, 1983.
 [Mac95] Ian G. Macdonald. Symmetric functions and Hall polynomials. Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, Second edition, 1995. With contributions by A. Zelevinsky, Oxford Science Publications
 [Nel05] Kendra Nelsen. A New Interpretation of the Cocharge Statistic. 2005.
 [Pat21] Leonardo Patimo. Charges via the affine Grassmannian. arXiv eprints, 2021.
 [PR16] Zoran Z. Petrović and Marko Radovanović. Recurrence formulas for Kostka and inverse Kostka numbers via quantum cohomology of Grassmannians. Algebras and Representation Theory, 20(2):257–273, August 2016.
 [Ras04b] Etienne Rassart. Geometric approaches to computing Kostka numbers and LittlewoodRichardson coefficients. Massachusetts Institute of Technology. 2004.
 [Shi01] Mark Shimozono. A cyclage poset structure for Littlewood–Richardson tableaux. European Journal of Combinatorics, 22(3):365–393, March 2001.
 [Shr22] Sagar Shrivastava. Littlewood–Richardson coefficients as a signed sum of Kostka numbers. arXiv eprints, 2022.
 [Sta01] Richard P. Stanley. Enumerative Combinatorics: Volume 2. Cambridge University Press, First edition, 2001.
 [Ste61] Robert Steinberg. A general Clebsch–Gordan theorem. Bull. Amer. Math. Soc., 67(4):406–407, July 1961.
 [Stu95] Bernd Sturmfels. On vector partition functions. Journal of Combinatorial Theory, Series A, 72(2):302–309, November 1995.
 [SW00] Mark Shimozono and Jerzy Weyman. Graded characters of modules supported in the closure of a nilpotent conjugacy class. European Journal of Combinatorics, 21(2):257–288, February 2000.
 [SW99] Anne Schilling and S. Ole Warnaar. Inhomogeneous lattice paths, generalized Kostka polynomials and $A_{n1}$ supernomials. Communications in Mathematical Physics, 202(2):359–401, April 1999.
 [WZ18] M. Wheeler and P. ZinnJustin. Hall polynomials, inverse Kostka polynomials and puzzles. Journal of Combinatorial Theory, Series A, 159:107–163, October 2018.