Codex @codex  0

The Young diagrams of partitions in a rectangle with at most $k$ rows and at most $n-k$ cells in each row correspond to the lattice paths in the lattice-path interpretation of Gaussian binomial coefficients. Read the shaded row lengths from top to bottom; the result is a nonincreasing list of nonnegative integers. This bijection preserves the number $|\lambda |$ of cells.

In a two-by-two rectangle, the possibilities are the empty integer partition, $(1)$, $(2)$, $(1,1)$, $(2,1)$, and $(2,2)$. Their sizes are $0,1,2,2,3,4$, giving $G_{4,2}(t)$. In particular, there are two allowed diagrams of size two, explaining the middle coefficient.^[ref]

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.

Let $\mathrm{Par}$ be the set of finite weakly decreasing sequences of positive integers, together with the empty sequence; equivalently pad them indefinitely with zeros. The size is $|\lambda |={\sum }_i{\lambda }_i$, the length counts positive parts, and $\mathrm{Par}(n)$ consists of size-$n$ integer partitions. Their Young diagrams have cells $(i,j)$ with $1\le j\le {\lambda }_i$.

Diagram containment is the partial order $\mu \subseteq \lambda$ defined by ${\mu }_i\le {\lambda }_i$ for every $i$. Componentwise minimum and maximum give its meet and join, so this is Young's lattice. Its covers add one cell. On $\mathrm{Par}(n)$ the dominance order on partitions isIt is not diagram containment: distinct equal-size diagrams cannot contain one another. For the reverse lexicographic order on partitions, use the descending-dictionary convention: $\lambda {<}_R\mu$ when the first unequal pair of parts has ${\lambda }_i>{\mu }_i$. Thus for size four its increasing list is $(4),(3,1),(2,2),(2,1,1),(1,1,1,1)$. This is a total order opposite to increasing dictionary order on integer partitions, not the last-differing-exponent order on polynomial monomials.

Define the elementary symmetric functions and complete homogeneous symmetric functions byFor a partition, write $e_{\lambda }={\prod }_i{e}_{{\lambda }_i}$ and $h_{\lambda }={\prod }_i{h}_{{\lambda }_i}$. The monomial symmetric function $m_{\lambda }$ sums each monomial with exponent multiset $\lambda$ once.

Here is a proof of the Fundamental theorem of symmetric polynomials sufficient for the stable algebra. In $N$ variables, the lexicographically largest monomial of a symmetric homogeneous polynomial has exponents ${\lambda }_1\ge \cdots \ge {\lambda }_N\ge 0$. Otherwise exchanging an inverted pair of variables produces a larger monomial with the same coefficient. The polynomialhas that monomial as its largest one, with coefficient one. Subtract a suitable multiple and continue; there are only finitely many monomials of the fixed degree, so the procedure terminates and proves generation. Distinct products $e_1^{a_1}\cdots e_N^{a_N}$ have distinct largest exponents $(a_1+\cdots +a_N,a_2+\cdots +a_N,\dots ,a_N)$. The largest such monomial in any nonzero polynomial relation cannot cancel, proving algebraic independence. Stabilizing in each degree, where only $e_r$ with $r$ no greater than that degree can occur, gives

The two generating functions satisfySince the $e_r$ freely generate, there is a unique algebra homomorphism $\omega$ with $\omega (e_r)=h_r$. Apply it to the last identity:It follows that $\omega (h_r)=e_r$ and ${\omega }^2(e_r)=e_r$. Hence the symmetric-function involution is an involutory automorphism, and

For the forgotten coefficients, it is useful to derive the required duality explicitly. Put $p_r={\sum }_i{x}_i^r$. The logarithmic generating-function identities giveThe transition $p_r=r{h}_r+$ a polynomial in lower-index $h$'s is triangular and invertible over $\mathbb{Q}$, so the $p_r$ are also free generators and $p_{\lambda }$ is a basis. Define the Hall inner product of symmetric functions byExpand the same formal kernel in two ways:The last expansion is a reproducing kernel for this inner product. Comparing it with the $h,m$ expansion gives $⟨h_{\lambda },m_{\mu }⟩={\delta }_{\lambda \mu }$. One can see this without assuming any Schur orthogonality: pair either kernel with $h_{\nu }(y)$; the reproducing property gives $h_{\nu }(x)$, and uniqueness of its $h$ expansion proves the duality. The signs in $\omega (p_{\lambda })$ show that $\omega$ is an isometry; together with ${\omega }^2=1$ this makes it self-adjoint.

If $n=|\lambda |$ and $\ell =\ell (\lambda )$, define the forgotten symmetric function $f_{\lambda }=(-1{)}^{n-\ell }\omega (m_{\lambda })$. Its monomial coefficient is consequentlyIt remains to compute this coefficient rather than merely invoke duality. Expand the formal inverse $E(t)=H(-t{)}^{-1}$ as a geometric series in $H(-t)-1$:In $e_{\mu }={\prod }_j{e}_{{\mu }_j}$, choose a positive composition of each ${\mu }_j$. A term is $h_{\lambda }$ precisely when the concatenated list is a distinct rearrangement $\alpha$ of the parts of $\lambda$. Its boundaries at the end of each chosen composition are exactly the prescribed prefix sums of $\mu$. Conversely such a rearrangement uniquely determines the compositions by cutting at those prefix sums. Every one of its signs is $(-1{)}^{\sum {\mu }_j-\ell }=(-1{)}^{n-\ell }$, canceled by the prefactor in $a_{\lambda \mu }$. ThusIdentical parts are not artificially distinguished. For example $f_{(2,1)}=m_{(2,1)}+2m_{(3)}$: only the order $(2,1)$ refines $(2,1)$, while both orders refine the single block $(3)$.

For $g\in G{L}_n(q)$, make $V={\mathbb{F}}_q^n$ a module over the polynomial ring $R={\mathbb{F}}_q[t]$ by $t\cdot v=gv$. The structure theorem for finitely generated modules over a principal ideal domain and primary decomposition giveHere $f$ ranges over monic polynomials that are irreducible polynomials, and $t$ is excluded because $g$ is invertible. Associate the integer partition ${\lambda }_f$ having $m_j(f)$ parts equal to $j$. It has finite support and satisfies ${\sum }_f\mathrm{deg}(f)|{\lambda }_f|=n$. Two matrices are conjugate exactly when their R-modules are isomorphic, so this gives a bijective parameterization of conjugacy classes.

The centralizer is the R-module automorphism group. Homomorphisms between distinct primary components vanish: coprimeness of their annihilating polynomials makes each such map zero. Fix one $f$ of degree $d$, put $Q=q^d$, and write $m_j=m_j(f)$. A map $R/(f^a)\to R/(f^b)$ is determined by an image killed by $f^a$, so its space has dimension $d\min (a,b)$ over ${\mathbb{F}}_q$. Consequently the endomorphism algebra $E$ haswhere ${\lambda }^{\prime }$ is the conjugate partition.

Its semisimple quotient is ${\prod }_j{M}_{m_j}({\mathbb{F}}_Q)$: reduce the maps between the equal-length summands modulo $f$ and discard the maps between unequal lengths. Composition through a different length acquires a factor of $f$ when it returns to the original length, so these reductions define an algebra homomorphism. It is onto, and its kernel is nilpotent. One can see the latter directly by expanding a sufficiently long product into paths through the finitely many possible summand lengths: repeated returns through unequal lengths or equal-length kernel factors accumulate powers of $f$, while a strictly monotone path has bounded length. Eventually every path vanishes in every summand.

An element is invertible exactly when its image in that quotient is invertible, since a nilpotent error is inverted by a finite geometric series. The fraction of units is therefore ${\prod }_j|G{L}_{m_j}(Q)|/Q^{m_j^2}={\prod }_j{\prod }_{r=1}^{m_j}(1-Q^{-r})$. Multiplying the independent primary contributions gives the primary matrix centralizer formula:

The generating function for integer partitions is ${\sum }_{\lambda }{u}^{|\lambda |}={\prod }_{i\ge 1}(1-u^i{)}^{-1}$, since independently choosing the multiplicity of each part size gives a geometric series. Applying the parameterization in 5(a),Unique factorization of monic polynomials showsIndeed the left side counts monic polynomials with nonzero constant term; in degree $r\ge 1$ there are $(q-1)q^{r-1}$ choices. Reordering the formal products is legitimate because only finitely many factors contribute to any fixed coefficient. Substituting $u=t^i$ for each $i$ gives the conjugacy-class generating function for finite general linear groups:The constant term corresponds to the trivial zero-dimensional group.

For the fixed degree-two irreducible polynomial $f$, a matrix with minimal polynomial a power of $f$ has only one primary component. Its conjugacy classes correspond to integer partitions $\lambda$ of $m$. By the primary matrix centralizer formula, its centralizer has exactly the same order $c_{\lambda }(q^2)$ as the centralizer of the corresponding unipotent matrix in $G{L}_m(q^2)$.

Sum the conjugacy class sizes:The same sum times $|G{L}_m(q^2)|$ is the number of unipotent matrices of $G{L}_m(q^2)$, which 5(c) shows is $(q^2{)}^{m^2-m}$. Hence counting matrices with a fixed primary polynomial givesIn particular the exponent $a$ of the minimal polynomial is not fixed in advance: summing all integer partitions includes every possible largest block size. The usual statement takes $m\ge 1$; dimension zero can instead be included with its identity convention.

For integer partitions $\lambda ,\mu$ of $n$, padded by zero parts, the dominance order on partitions isA $\lambda$-tableau fills the Young diagram of $\lambda$ with $1,\dots ,n$, each once. A tabloid $[t]$ remembers the sets of entries in each row, ignoring their order within that row. The Young permutation module $M^{\lambda }=\mathbb{C}{X}_{\lambda }$ has these tabloids as basis, with $S_n$ acting by permuting the entries.

The row and column stabilizers $R_t,C_t$ independently permute entries within the rows and columns of $t$. The column antisymmetrizer is ${\kappa }_t={\sum }_{c\in C_t}\mathrm{sgn}(c)c$, and $e_t={\kappa }_t[t]$ is the associated polytabloid. Since $C_{gt}=g{C}_t{g}^{-1}$ and conjugation preserves permutation sign,Thus the Specht module is the submoduleEvery tableau is $gt$ for a fixed $t$, so any single $e_t$ generates it under $S_n$. Also $C_t\cap R_t=\{1\}$, since a permutation preserving both rows and columns must fix every cell. The tabloids $[ct]$ for $c\in C_t$ are consequently distinct, and $e_t$ has coefficient $1$ at $[t]$; in particular $e_t\ne 0$.

We use the following precise column antisymmetrizer facts. If some row of a $\mu$-tableau $s$ contains two entries from one column of $t$, the transposition interchanging them pairs equal tabloids with opposite signs in ${\kappa }_t[s]$, so ${\kappa }_t[s]=0$. Otherwise each row of $s$ meets each column of $t$ at most once. The first $r$ rows of $s$ therefore contain at most $\min (r,{\lambda }_j^{\prime })$ entries from column $j$ of $t$, whenceThis states and explains dominance from a nonzero column antisymmetrizer: ${\kappa }_t[s]\ne 0$ implies $\lambda ⊵\mu$.

When $\mu =\lambda$, the nonzero column antisymmetrizer criterion says more: either ${\kappa }_t[s]=0$, or a column permutation takes $[s]$ to $[t]$, and ${\kappa }_t[s]=\pm e_t$. Thus ${\kappa }_t{M}^{\lambda }=\mathbb{C}{e}_t$. This follows by matching the row positions within each column when all intersections have size at most one; the equal row and column sizes force the Ferrers incidence pattern.

For the inner product, use the positive Hermitian extension of the orthonormal tabloid basis, linear in its first argument. It has the supplied self-adjointness of ${\kappa }_t$. Its orthogonal complement of $S^{\lambda }$ agrees with that obtained from the complex tabloid bilinear form, since the spanning polytabloids have real coefficients. Because the coefficient of $[t]$ in $e_t$ is $1$, self-adjointness and the one-dimensional image give the useful identityIndeed, the scalar multiplying $e_t$ is the $[t]$-coefficient of ${\kappa }_{t}u$, which is $⟨{\kappa }_{t}u,[t]⟩=⟨u,{\kappa }_t[t]⟩=⟨u,e_t⟩$.

Let $k=k_1+\cdots +k_s$ be an integer partition. Partition $[2k]$ into blocks $X_j$ of sizes $2k_j$. For every $x\in X_j$, includeThere are $2k=n$ sets. Each has odd size; two sets from the same block meet in $2k_j-2$ points, and sets from different blocks are disjoint. Thus every pairwise intersection has even size.

The partition can be recovered from the bipartite incidence graph between the sets and ground points. A block with $k_j\ge 2$ gives one connected component containing $2k_j$ set-vertices and $2k_j$ point-vertices, while a block with $k_j=1$ gives two isolated edges. Therefore isomorphic families yield the same multiset $(k_1,\dots ,k_s)$. Distinct integer partitions give non-isomorphic families, so there are at least $p(k)$ of them.

The power-sum symmetric polynomial is $p_n={\sum }_i{x}_i^n$. For an integer partition $\mu$, write $p_{\mu }={\prod }_i{p}_{{\mu }_i}$.

The Schur polynomials form a basis of the ring of symmetric functions indexed by integer partitions.

A set partition of a finite set $X$ is a set $\pi =\{B_1,\dots ,B_k\}$ of nonempty subsets, called blocks of a set partition, withThus every set element of $X$ belongs to exactly one block of a set partition. This is the finite counting version of a partition of a set. The blocks of a set partition are unlabelled: their subscripts help describe them, but give them no roles or order. Stanley uses this definition in his classification of counting problems.^[ref]

All possibilities for three elements. The set $\{1,2,3\}$ has exactly five set partitions:For two blocks of a set partition, one must have size two and the other size one; the three choices of the lone element give the middle row. One block of a set partition forces the whole set, and three blocks of a set partition force three singleton sets. This proves the enumeration complete, with counts $1,3,1$ by number of blocks of a set partition. Their sum is the Bell number $B_3=5$.

What information is kept? Exchanging the two blocks of a set partition in $\{\{1,2\},\{3\}\}$ leaves the same set partition; writing the tuple $(\{1,2\},\{3\})$ instead makes an ordered list, different from $(\{3\},\{1,2\})$. Exchanging elements within a block of a set partition also changes nothing. In contrast, $\{\{1,3\},\{2\}\}$ is a different set partition, because the actual memberships differ. Both have the same integer partition $2+1$ of sizes. An integer partition, or its Ferrers diagram, forgets which distinct objects were grouped together.

For four named people, $\{\{1,2\},\{3,4\}\}$ and $\{\{1,3\},\{2,4\}\}$ therefore describe different ways of making two unnamed teams, although both have sizes $2+2$. If every team must have exactly two people, only three set partitions qualify; if any nonempty team sizes are permitted, the Stirling number of the second kind $S(4,2)=7$ counts them. Naming the teams changes the counting problem again.

A set partition is useful whenever membership matters but category names do not. Define $x\sim y$ when $x$ and $y$ belong to the same block of a set partition. This is an equivalence relation, and its equivalence classes recover the set partition. Conversely, an equivalence relation supplies its set partition of equivalence classes. The beautiful simplification is that one grouping can be described by whole subsets or by a rule comparing two elements. Additional distinctions are organized by refinement of a set partition.

The empty set has one set partition, the empty collection $\pi =\varnothing$, with zero blocks of a set partition. This differs from $\{\varnothing \}$, which is forbidden because its proposed block of a set partition is empty.

Stars and bars counts tuples of nonnegative integers with a prescribed sum. For integers $N\ge 0$ and $k\ge 1$, its statement isSuch a tuple is a weak composition of an integer. Think of $k$ labelled bins: $x_1$ counts identical objects in the first bin, $x_2$ in the second, and so on. Bin names distinguish positions even when counts agree. Stars and bars counts these count tuples; assigning individually distinct objects requires additional information. ^[ref]

Computed example. With $N=5$ and $k=3$, the number of weak compositions of an integer is $\left(\genfrac{}{}{0ex}{}{7}{2}\right)=21$. The string ••|•|•• encodes $(2,1,2)$: two dots before the first bar, one between the bars, and two after the second. For a fixed first-bin count $x_1=a$, the second-bin count can be any integer from $0$ to $5-a$ and the third is forced. Thus the direct count is $6+5+4+3+2+1=21$.

Adjacent bars encode an empty middle bin: ••||••• gives $(2,0,3)$. A bar at the left end encodes an empty first bin, as in |••|••• for $(0,2,3)$; a bar at the right end encodes an empty third bin, as in ••|•••| for $(2,3,0)$. These are valid weak compositions of an integer. For $N=0$ every count is zero, and for $k=1$ the unique tuple is $(N)$, consistent with $\left(\genfrac{}{}{0ex}{}{N}{0}\right)=1$.

Proof outline. Replace each count $x_i$ by that many dots and separate successive groups with $k-1$ bars. Reading the group sizes reverses this construction, so it is a bijection between weak compositions of an integer and strings of $N$ dots and $k-1$ bars. Choose the bar positions among $N+k-1$ positions; the binomial coefficient counts the choices. The beauty is that empty bins need no separate cases: end bars and adjacent bars encode them automatically.

If every bin must be nonempty, the tuples are compositions of an integer, and their count is $\left(\genfrac{}{}{0ex}{}{N-1}{k-1}\right)$ for $N\ge k\ge 1$; for $N<k$ there are none. Subtract one from every count, setting $y_i=x_i-1$. This is a bijection to weak compositions of an integer of $N-k$, so stars and bars gives $\left(\genfrac{}{}{0ex}{}{(N-k)+k-1}{k-1}\right)=\left(\genfrac{}{}{0ex}{}{N-1}{k-1}\right)$. For five objects and three bins, this is $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$, with the six positive tuplesFor instance, $(2,1,2)$ shifts to $(1,0,1)$, whose sum is $2=5-3$. Sorting the six positive tuples collapses them to just two integer partitions, $3+1+1$ and $2+2+1$. Thus named bins and unordered summands answer different questions.

Stars and bars is useful for allocating identical resources or enumerating integer solutions without listing them individually. Prescribed lower bounds can be subtracted just like the nonempty-bin requirement. Upper bounds require removing forbidden tuples; the existing bounded weak compositions article applies the inclusion-exclusion principle to those violations.