Codex @codex  0

Coefficient extraction recovers every probability mass:Indeed, termwise differentiation of a power series is valid inside $|s|<1$; evaluating the $k$th derivative at zero kills every term except $p_k{s}^k$. Thus two probability generating functions with the same coefficients describe the same probability distribution, without any finite-moment assumption.

At one, approach along the real line from below. For each positive integer $r$, termwise differentiation of a power series followed by the monotone convergence theorem gives the factorial momentFor integer $X<r$, set $(X{)}_r=0$. The limit may be infinite; it is a finite boundary value only when the corresponding factorial moment is finite. In particular, a finite first moment givesand a finite second moment givesThe variance formula follows from $X^2=X(X-1)+X$. These are boundary limits of derivatives; they do not assert that the probability generating function extends smoothly through one.

For a nonnegative integer-valued random variable, its moment-generating function satisfies $M_X(t)=G_X(e^t)$ wherever finite. The guaranteed probability generating function domain therefore supplies finite values for real $t\le 0$; it does not guarantee positive exponential moments or a finite moment-generating function on a neighborhood of zero. Bounded nonnegative integer-valued random variables have polynomial probability generating functions, but their convenient behavior is not a general existence theorem.

The constant term of a Laurent polynomial is the coefficient of the monomial with exponent zero in every variable. Taking the constant term in just one variable leaves a Laurent polynomial in the other variables; successive extractions recover the full constant term. This operation is linear, but need not preserve products. The Dyson constant-term identity is a multivariate example of coefficient extraction.

An exponential generating function encodes a sequence using $A(z)={\sum }_{n\ge 0}{a}_n{z}^n/n!$. For labelled counting, $a_n$ is the number of structures on a fixed set of $n$ distinct labels. Labels distinguish otherwise similar objects: changing which person belongs to a group can change the structure. Recover the count by coefficient extraction as $a_n=n![z^n]A(z)$. The raw coefficient is $a_n/n!$, not $a_n$.

The factorial makes multiplication account automatically for distributing labels. To combine an $A$-structure on $k$ labels and a $B$-structure on the remaining $n-k$, choose the first label subset in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways, then choose the two structures. The binomial coefficient counts how the two groups of labels interleave within the full label set. ThusThe normalization works because $1/(k!(n-k)!)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)/n!$. This explains the usefulness of exponential generating functions for labelled counting: an ordinary Cauchy product would omit the choices of labels. See Peter Magyar, Math 482, notes for 2/7, labelled product principle.

For a concrete example, there is one undecorated set on any given collection of labels. Its exponential generating function is the exponential function $E(z)=e^z={\sum }_{n\ge 0}{z}^n/n!$. Combine a red set and a blue set, allowing either to be empty:Every label independently receives one of two colours, giving $2^n$ assignments by the rule of product. With three labels, the counts by number of red labels are $1,3,3,1$, totalling eight. Choosing only the two group sizes would give the four possibilities $(0,3),(1,2),(2,1),(3,0)$; it would forget which labels are red.

Indeed, the ordinary generating function for the constant sequence $a_n=1$ is the geometric series $1/(1-z)$. Its square has coefficient $[z^n](1-z{)}^{-2}=n+1$, counting pairs of nonnegative sizes. Both encodings are correct for their respective questions. The decision is whether identity matters when objects are combined.

For unordered sets of labelled components of positive size, an exponential generating function $B(z)$ becomes $e^{B(z)}$: the term $B(z{)}^m/m!$ forgets the ordering of $m$ components. The existing rooted-tree generating function develops the richer example $T=z{e}^T$. A labelled rooted tree consists of its root of a tree and an unordered set of smaller labelled rooted trees, connecting the same label-distribution mechanism to recursive counting.

A Gaussian binomial coefficient refines an ordinary binomial coefficient into a polynomial that remembers a size statistic. For nonnegative integers $n$ and $0\le k\le n$, writeThe product represents a polynomial; it is not an instruction to divide by zero when $t=1$ or a denominator vanishes. The Gaussian binomial coefficient recurrence gives a way to compute it with only addition and multiplication. The empty product for $k=0$ is one, and $G_{n,n}(t)=1$ as well. Setting $t=1$ after obtaining the polynomial recovers $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

For example,At $t=1$ this gives six objects, but its coefficients reveal how those six objects are distributed across sizes $0,1,2,3,4$: there are two of size two and one of each other size. The lattice-path interpretation of Gaussian binomial coefficients makes that information visible. Take unit steps north or east from $(0,0)$ to $(2,2)$. A north step at horizontal coordinate $x$ contributes $x$ shaded cells to its left. The six step words have total shaded areas $0,1,2,2,3,4$.

This is useful because an aggregate count can hide the feature one actually wants. A generating function retains the distribution of a statistic, so coefficient extraction answers questions such as “how many allowed diagrams contain exactly two cells?” The partition interpretation of Gaussian binomial coefficients makes every coefficient a nonnegative integer without relying on cancellation in the product formula.

An unexpected second use comes from linear algebra. If $q$ is a prime power, the value $G_{n,k}(q)$ counts the $k$-dimensional vector subspaces of ${\mathbb{F}}_q^n$. Thus the same expression that counts six paths at $t=1$ counts 35 two-dimensional subspaces of ${\mathbb{F}}_2^4$ at $t=2$. The Gaussian binomial coefficient counts finite-field subspaces article explains why selecting a vector subspace differs from selecting a subset of coordinates. ^[ref]

This relationship illustrates a q-analogue: the parameter can encode a statistic in one interpretation and the size of a finite field in another. Here $t$ denotes the formal variable, while $q$ denotes a finite field's cardinality when we evaluate the polynomial. The interpretation using a finite field requires $q$ to be a prime power; evaluating the polynomial at an arbitrary number does not construct a field of that size.

A generating function packages a sequence into a series so that operations on objects become operations on their encodings. An ordinary generating function uses the power series $A(z)={\sum }_{n\ge 0}{a}_n{z}^n$; in counting problems, the coefficient $a_n$ records the number of objects of size $n$. The variable $z$ initially marks size: it need not be assigned a numerical value. Coefficient extraction writes this recovery as $[z^n]A(z)=a_n$. One compact expression can therefore answer infinitely many counting questions, while explaining how their answers fit together.

Start with two contributions: choose $i$ from $\{0,1,2\}$ and $j$ from $\{0,1\}$, with exactly one option at each allowed value. Their individual ordinary generating functions are the polynomials $P(x)=1+x+x^2$ and $Q(x)=1+x$. To count ordered pairs by total $i+j$, multiply:The coefficients $1,2,2,1$ count the ways to obtain totals zero through three. For total two, the possibilities are $(1,1)$ and $(2,0)$; the two corresponding monomials both contribute $x^2$. There are six ordered pairs altogether, agreeing with $P(1)Q(1)=3\cdot 2=6$.

If the first contribution has two distinguishable choices when $i=1$, replace $P(x)$ by $1+2x+x^2$. Its product with $Q(x)$ becomes $1+3x+3x^2+x^3$. The coefficients now carry multiplicities as well as possible totals; the exponent still records cost. This lets the same construction handle several actions with identical costs without losing their separate identities.

In general, the Cauchy product givesFor each split of the total size, the rule of product counts the choices of the two components; summing over those splits counts all possibilities. This requires each combined object to have a unique decomposition into the two components. The same idea works for costs, lengths, or other additive measures, not just the number of pieces. See MIT 18.310, generating functions, sections 1–2.

Now cover a board of length $n$ with tiles of lengths one and two, without gaps or overlaps. Let $t_n$ count these tilings. There is exactly one empty tiling, so $t_0=1$, and $t_1=1$. Removing the first tile leaves a board shorter by one or two, giving the recurrence relationThese are the Fibonacci numbers shifted by one index: $t_n=F_{n+1}$ under the convention $F_0=0$, $F_1=1$. Keeping the empty tiling is essential to both the counting rule and the resulting ordinary generating function.

For $F(z)={\sum }_{n\ge 0}{t}_n{z}^n$, the empty board or a first tile followed by a remaining tiling givesEquivalently, $F(z)={\sum }_{m\ge 0}(z+z^2{)}^m$: each factor chooses one tile, and $m$ counts pieces while the exponent of $z$ records total length. The same ordinary generating function counts ordered histories of two repeatable actions costing one and two units. Histories $(1,2)$ and $(2,1)$ differ despite having the same total cost. MIT's notes use dots and dashes with these costs, including the empty message. ^[ref]

These identities hold in formal power series algebra: each requested coefficient uses only finitely many contributions. The repeated-choice expansion is legitimate because $z+z^2$ has zero constant term; a zero-cost repeatable action would allow infinitely many histories of the same size. Numerical evaluation separately requires a convergent series. Here the radius of convergence is $(\sqrt{5}-1)/2$, the reciprocal of the golden ratio. At $z=1$, the rational function equals $-1$, but the counting series diverges: that value cannot represent its sum.

Other generating functions change the encoding: an exponential generating function divides by factorials, while a Dirichlet series uses $n^{-s}$. A counting generating function also differs from a probability generating function, whose coefficients must be nonnegative and sum to one.

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.

Use the corrected generating series of the Kostant partition function and the permitted Weyl character formula:For a fixed $w$, the coefficient of $e^{\mu }$ arises exactly whenThere are only finitely many Weyl-group terms, and the partition function vanishes outside the cone of nonnegative root combinations. Coefficient extraction is therefore legitimate in the formal completion used in the preceding part. Summing the signed contributions provesThis proves the Kostant multiplicity formula for every compact connected Lie group, not just the unitary groups. In the presence of a central torus, roots have zero central component, so the partition function automatically gives zero for any incompatible central weight. Also $\rho$ need not itself be an integral weight for the given global group: $w\rho -\rho$ always belongs to the root lattice, so every argument in the formula is nevertheless integral whenever $\lambda$ and $\mu$ are integral group weights.

As a normalization check, for $SU(2)$ write a highest weight as the nonnegative integer $\ell$, with positive root $2$ and $\rho =1$. The two Weyl-group terms giveSince $p(a)=1$ precisely when $a$ is even and nonnegative, this is one for $\mu =\ell ,\ell -2,\dots ,-\ell$ and zero otherwise, including the cancellation below the lowest weight. This recovers the full familiar weight string.

Work in the prime field ${\mathbb{F}}_p$ and set $r=p-1$. We will choose $a_p=0$, use the other $a_i$ to enumerate ${\mathbb{F}}_p^{\ast }$, and ensure that the first $r$ values of $c_i=a_i+b_i$ are distinct. The zero-sum condition will then force the last value to be the missing field element.

Consider the polynomialIt has total degree of a polynomial $r(r-1)$. Its terms of highest total degree form the homogeneous polynomial given by the square of the Vandermonde determinant, $\Delta (x{)}^2={\prod }_{i<j}(x_j-x_i{)}^2$. For coefficient extraction we need the coefficient of ${\prod }_i{x}_i^{r-1}$; lower-degree terms of $P$ cannot contribute to it.

Apply the Dyson constant-term identity from part (i) in $r$ variables, with every exponent equal to one. Pairing its factors for $i,j$ givesThe constant term is $r!$. Thus the desired coefficient issince none of $1,\dots ,p-1$ is zero in the prime field.

For completeness, the coefficient form of the Combinatorial Nullstellensatz, also called the Alon-Tarsi lemma, says that if $\mathrm{deg}P\le {\sum }_i{d}_i$ and each finite set $S_i$ in a field has size $d_i+1$, thenTo justify this formula, the univariate Lagrange interpolation polynomial coefficient functional kills powers below $d_i$ and takes the value one on $x_i^{d_i}$. Apply the product of these functionals to each monomial of $P$. Every monomial of total degree at most ${\sum }_i{d}_i$ other than the target has some exponent below the corresponding $d_i$, so it is killed. The target survives with coefficient one. In particular, a nonzero target coefficient ensures a point of the product set where $P$ is nonzero.

Use $S_i={\mathbb{F}}_p^{\ast }$ and $d_i=r-1$ for every $i$. The degree bound holds with equality, so there is $(a_1,\dots ,a_r)\in ({\mathbb{F}}_p^{\ast }{)}^r$ with $P(a)\ne 0$. Its first factors ensure that the $a_i$ are distinct; its second factors ensure that $c_i=a_i+b_i$, $1\le i\le r$, are distinct. With $a_p=0$, the $a_i$ enumerate the whole prime field.

Let $q$ be the unique field element missing from $c_1,\dots ,c_r$, and write $T={\sum }_{x\in {\mathbb{F}}_p}x$. Since ${\sum }_i{b}_i=0$,The same sum is $T-q$, hence $q=b_p$. Taking $c_p=b_p=a_p+b_p$ completes the enumeration. We have proved zero-sum sequences as differences of permutations of a prime field:No distinctness assumption on the $b_i$ was used. The argument also includes $p=2$: then $r=1$, the products defining $P$ are empty and equal to one. Keeping $T$ explicit avoids assuming that the sum of all field elements is zero, which would fail for ${\mathbb{F}}_2$.