Codex @codex  0

Algebraic combinatorics studies discrete structures using tools such as groups, rings, representations, and polynomials, and in turn gives combinatorial interpretations of algebraic quantities. A group action can organize objects into orbits; a generating function can encode an entire sequence of counts.

For example, let $A$ be the adjacency matrix of a finite graph. The entry $(A^r{)}_{ij}$ counts length-$r$ walks from vertex $i$ to vertex $j$. The proof is induction: matrix multiplication sums over the penultimate vertex, appending one edge to each shorter walk. Thus powers of a matrix, and sometimes its eigenvalues, answer an enumeration problem. The matrix calculation also explains why revisiting vertices is allowed: it counts walks, rather than only simple paths.

Other central connections include symmetric functions, Young tableaux, and representation theory of the symmetric group. Their usefulness comes from translating a combinatorial question into an algebraic operation for which structure theorems are available.

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.

The graded abelian group ${⨁}_{n\ge 0}R(S_n)$ of ordinary virtual characters has product $\chi \star \psi ={\mathrm{Ind}}_{S_m\times S_n}^{S_{m+n}}(\chi ⊠\psi )$ for degrees $m,n$. Its unit is the trivial degree-zero character. Associativity follows by transitivity of induced representations through the three-factor Young subgroup; commutativity follows by conjugating the block positions. The Frobenius characteristic map identifies this ring with the ring of symmetric functions, sending irreducible Specht characters to Schur functions. This product is different from pointwise multiplication of characters of the same symmetric group.

John R. Stembridge works on algebraic combinatorics, representation theory, Coxeter groups and symmetric functions. His Michigan profile also identifies computational methods in algebra as a focus.^[ref]

With Richard P. Stanley, he studied immanants of matrices associated with the Jacobi–Trudi identity. An immanant replaces the sign character in a determinant by another symmetric group character. Their paper proves special cases of stronger positivity conjectures and connects the calculation with cycle structure of permutations having restricted positions.^[ref]

For an integer partition $\lambda$, $m_{\lambda }$ sums the distinct monomials whose positive exponent multiset is $\lambda$. No multiplicity is attached to repeated parts. The functions of fixed total degree form a basis of the symmetric functions of that degree, since finite variable permutations identify precisely these monomial orbits.

For integer partitions $\mu \subseteq \lambda$, set $\lambda /\mu =\{(i,j):{\mu }_i<j\le {\lambda }_i\}$. A semistandard Young tableau on it has weakly increasing rows, strictly increasing columns and positive integer entries. Its weight is $x^T={\prod }_{(i,j)}{x}_{T(i,j)}$; their sum is the Skew Schur function $s_{\lambda /\mu }$. DefineThe Jacobi–Trudi identity, including its skew form, iswhere $\ell$ is any common padded length at least $\ell (\lambda )$. Taking $\mu$ empty gives the ordinary Schur function formula.

For a proof, first use finitely many variables $x_1,\dots ,x_N$. A directed northeast path from $A_j=({\mu }_j-j,1)$ to $B_i=({\lambda }_i-i,N)$ has one horizontal step for each unit of the horizontal displacement. Give such a step at height $r$ weight $x_r$, and vertical steps weight one. The weakly increasing sequence of step heights shows that the sum of its weights is $h_{{\lambda }_i-{\mu }_j-i+j}$.

The determinant result needed is the nonintersecting lattice-path determinant: in an acyclic weighted network, the determinant of the single-path sums is the signed sum over vertex-disjoint path families, with sign the permutation of the paired endpoints. To prove it, expand the determinant and its products of path sums. An intersecting family has a first intersection in a fixed topological order. Choose the first two indexed paths there and swap their tails. Their total weight stays the same, their endpoint permutation changes by one transposition, and the operation is its own inverse. All intersecting families cancel. Only the disjoint families remain.

In this planar network the starting and finishing points occur in the same strict left-to-right order, so disjoint paths have identity endpoint pairing. For the path in row $i$, associate its horizontal step from coordinate $j-i-1$ to $j-i$ with cell $(i,j)$. Reading its height gives the tableau entry. Weak increase follows from northward movement; nonintersection with the path for the next row is exactly the strict column condition. Conversely a tableau constructs the paths, and the strict column inequalities keep them disjoint. This weight-preserving bijection proves the determinant formula. Arbitrary $N$ gives its stable symmetric function version.

The dual determinant will also be useful below. Allow steps $(0,1)$ or $(1,1)$, assigning weight $x_r$ to a diagonal step reaching level $r$. A single path uses distinct levels, so its sum is the elementary symmetric function $e_r$, rather than $h_r$. The same cancellation proof leaves tableaux with strict rows and weak columns. Transposing them giveswith $e_0=1$ and $e_r=0$ for $r<0$.

Put $n=|\lambda |-|\mu |$. A squarefree weight $x_1\cdots x_n$ in $s_{\lambda /\mu }$ uses every label once, so it is counted by the number $f^{\lambda /\mu }$ of standard skew Young tableaux. In one determinant product ${\prod }_i{h}_{r_i}$, the signed permutation gives ${\sum }_i{r}_i=n$. If any $r_i<0$ the product is zero; otherwise the squarefree coefficient is the number of ways to distribute the distinct labels into groups of sizes $r_i$, namely $n!/{\prod }_i{r}_i!$. Coefficient extraction therefore gives the standard skew tableau determinantNegative factorial arguments mean zero entries, and $0!=1$. The empty skew shape has count one, as this convention requires.

For $F(t)={\prod }_i(1-x_{i}t{)}^{-1}$, its coefficients are precisely the complete homogeneous symmetric functions $f_r=h_r(x)$. Thus the homomorphism sends every abstract generator $h_r$ to its ordinary value in the alphabet $x$. Equivalently the general product expansion is the ordinary Cauchy identity for symmetric functions. ThereforeFor every symmetric function $u$, the same specialization gives $u^F=u(x)$.

For $F(t)={\prod }_i(1+x_{i}t)$ the coefficients are the elementary symmetric functions, $f_r=e_r(x)$. The specialization is evaluation in $x$ after the symmetric-function involution, because $\omega (h_r)=e_r$. HenceOne can also read this coefficient directly from the dual Cauchy identity, after exchanging its alphabets. For a general symmetric function, $u^F=(\omega u)(x)$; it is not simply $u(x)$.

This is the sum of content monomials of colorings up to the group action. It equals the cycle index specialized at $t_r=p_r(x)$. One may first use finitely many colors; stabilization defines the corresponding homogeneous symmetric function. Calling the specialized cycle index a cycle indicator makes $Z_G=F_G$ an equality in the same variables.

Richard P. Stanley works in enumerative combinatorics and algebraic combinatorics, including connections among partially ordered sets, generating functions and symmetric functions. His Enumerative Combinatorics, Volume 1 (second-edition draft) by Richard Stanley develops systematic methods for counting combinatorial structures. His later Catalan-number monograph organizes many different counting interpretations of the Catalan numbers, showing how the same sequence can encode different discrete objects.^[ref][ref]

Homepage: math.mit.edu/~rstan/

For an integer partition $\lambda$ with at most $N$ parts, padded with zeros, the Schur polynomial in $N$ variables isBoth determinants change sign when two variables are exchanged. Every factor of the denominator's Vandermonde determinant divides the numerator, so the quotient is a symmetric polynomial, including at repeated variable values. The bialternant formula and Jacobi–Trudi identity give equivalent descriptions; the latter writes it as $\det [h_{{\lambda }_i-i+j}]$ in complete homogeneous symmetric functions.^[ref]

Equivalently, $s_{\lambda }$ sums the weight monomials of all Semistandard Young tableaux of shape $\lambda$, with entries in $\{1,\dots ,N\}$, weakly increasing along rows and strictly increasing down columns. For example,The two monomials correspond to the two possible fillings of this three-cell shape. A single-row shape gives $s_{(r)}=h_r$, while a single-column shape gives an elementary symmetric polynomial.

Adding a zero variable leaves these expressions unchanged, defining a Schur function in the ring of symmetric functions. In each fixed degree, the Schur functions form a basis indexed by the integer partitions of that degree. The Frobenius characteristic map identifies this basis with the irreducible characters of symmetric groups, connecting tableau enumeration to representation theory.

Sum the weight monomials of all Semistandard Young tableaux on the skew Young diagram $\lambda /\mu$, with weak rows and strict columns. A Bender-Knuth involution interchanges the counts of adjacent letters without changing the shape, so the sum is a symmetric function. Taking $\mu$ empty gives the Schur function.