Codex @codex  0

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.

The formal power series ring $R[[T]]$ consists of all expressions ${\sum }_{n\ge 0}{a}_n{T}^n$ with $a_n\in R$. Addition is coefficientwise, while multiplication uses the Cauchy product; no analytic convergence is required.

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.

The ordinary generating function $C(x)={\sum }_{n\ge 0}{C}_n{x}^n$ packages the Catalan recurrence. Its Cauchy product gives the formal power series identityThe constant term is $C_0=1$. Solving the quadratic equation chooseswith the formal power series square root having constant term one. The apparent quotient at $x=0$ has constant term one after cancellation; the other quadratic solution has a pole and cannot be this ordinary generating function. The equation records the empty object or an outer unit with two ordered smaller objects.

In a submultiplicative matrix norm, the exponential series is absolutely convergent. Its Cauchy product can therefore be grouped by the total degree:When $AB=BA$, the inner sum is $(A+B{)}^n$ by the binomial theorem. Thus $\boxed{e^A{e}^B=e^{A+B}}$. The commutation assumption is used precisely in that binomial expansion; absolute convergence alone does not supply it.

The matrix exponential power series is absolutely convergent for a finite matrix, so taking the conjugate transpose term by term is valid. Since $M^{†}=M$,The absolute convergence also justifies the Cauchy product. In $e^{-iM}{e}^{iM}$, the coefficient of $M^n$ is proportional to ${\sum }_{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})$, which is zero for $n>0$ and one for $n=0$, by the binomial theorem. Consequently $U^{†}U=I$; the reversed product is also $I$. This proves that the exponential is unitary directly from the power series, without invoking diagonalization.

A Noetherian module satisfies the ascending chain condition on its submodules; equivalently every submodule is a finitely generated module. If the latter condition holds, the union of an ascending chain has a finite generating set lying in one member, so the chain stabilizes. Conversely, a submodule with no finite generating set allows successive choices outside the submodule generated so far, producing a strictly ascending chain. A Noetherian ring is a ring that is Noetherian as a module over itself, equivalently one whose ideals are all finitely generated.

The formal power series ring consists of sequences written ${\sum }_{i\ge 0}{a}_i{x}^i$, with coefficientwise addition and the Cauchy product:Every coefficient uses a finite sum; no analytic convergence is involved. Evaluation at zero gives $A[[x]]/(x)\cong A$. A quotient ring of a Noetherian ring is Noetherian, because its ascending chains of ideals lift to such chains upstairs. Thus one direction of Noetherianity of a formal power series ring is immediate.

For the other direction suppose $A$ is Noetherian, and let $I\subseteq A[[x]]$ be an ideal. Define the coefficient ideals of a formal power series idealEach is an ideal, and multiplication by $x$ gives $I_r\subseteq I_{r+1}$. Choose $N$ with $I_N=I_{N+1}=\cdots$. For $0\le r\le N$, choose generators $a_{r1},\dots ,a_{r{m}_r}$ for $I_r$, and choose series $g_{rj}\in I\cap x^{r}A[[x]]$ whose $x^r$ coefficients are those generators. Empty generating sets are allowed for zero ideals.

These finitely many series generate $I$. To prove this without assuming that $I$ is closed, start with $g\in I$ and cancel its coefficients successively. If the residual $h_r$ lies in $I\cap x^{r}A[[x]]$, its $x^r$ coefficient lies in $I_r$. Put $s=\min (r,N)$; since $I_r=I_s$ when $r\ge N$, write that coefficient as ${\sum }_j{c}_{rj}{a}_{sj}$ and subtract ${\sum }_j{c}_{rj}{x}^{r-s}{g}_{sj}$. The new residual belongs to $I\cap x^{r+1}A[[x]]$.

For $s<N$, the generators $g_{sj}$ are used only at the single step $r=s$. For $s=N$, their accumulated multipliers are the genuine formal power series ${\sum }_{r\ge N}{c}_{rj}{x}^{r-N}$. Thus the construction yields the exact coefficientwise identityEvery coefficient of the residual vanishes after finitely many steps. This is an ordinary finite generating expression in $A[[x]]$, not merely an approximation by elements of a smaller ideal. Therefore every ideal is finitely generated, provingFinally, for the surjective module endomorphism $f$, the kernels $\ker f\subseteq \ker f^2\subseteq \cdots$ stabilize because $M$ is a Noetherian module. Take $N$ with $\ker f^N=\ker f^{N+1}$. If $f(m)=0$, surjectivity of $f^N$ gives $u$ with $f^N(u)=m$. Then $f^{N+1}(u)=0$, so $u\in \ker f^N$ and $m=0$. Hence $f$ is injective as well as surjective; its inverse is automatically $A$-linear. This proves $f$ is an isomorphism, the statement that Noetherian modules are Hopfian.

Take both functions to be the constant arithmetic function $1$. Thenso the divisor function is multiplicative by part (a). For $s$ with $\mathrm{Re}s>1$, the relevant Dirichlet series are absolutely convergent, so their Cauchy product may be rearranged:Equivalently, Dirichlet convolution becomes multiplication of absolutely convergent Dirichlet series.

The degree-$n$ component isDimensions therefore satisfy the Cauchy product rule, giving

In the Cauchy product, $a_j{x}^j$ combines with $b_{i-j}{x}^{i-j}$ to give a term of degree $i$. HenceThis coefficient identity holds for formal power series. For convergent Taylor series it also gives the function product throughout the common open interval of convergence, where absolute convergence justifies regrouping.

Multiply the two power series and collect equal powers of $x$. The Cauchy product givesOnly terms whose two exponents add to the target exponent contribute.

Use the binomial series and exponential Maclaurin series:The Cauchy product isAdding $\log (1+x)=x-x^2/2+x^3/3-x^4/4+O(x^5)$ cancels the first three powers. Hence the first nonzero term is

The absolutely convergent geometric series has sum ${\sum }_{k=0}^{\infty }{r}^k=(1-r{)}^{-1}$ for $0<r<1$. Its Cauchy product with itself isThere are exactly $m+1$ pairs of nonnegative integers whose sum is $m$. Relabeling $j=m+1$ provesAbsolute convergence justifies the multiplication and regrouping; no differentiation of an infinite series is needed.

For nonnegative integer-valued independent random variables $X,Y$, factor the expected value of a product:The Cauchy product explains what this means for individual probability masses:Every way of splitting the total contributes once. This is convolution of independent random variables; multiplying probability generating functions performs the bookkeeping automatically.

For an original example, take independent $X\sim \mathrm{Bernoulli}(0.3)$ and $Y\sim \mathrm{Binomial}(2,0.5)$, using the Bernoulli distribution and binomial distribution. ThensoDirect enumeration of the six pairs $(x,y)$ gives the same probability masses. For example, total one collects $(0,1)$ and $(1,0)$, with contributions $0.7\cdot 0.5+0.3\cdot 0.25=0.425$. The coefficients sum to one. The expected value is $G_{X+Y}^{\prime }(1)=1.3$; since $G_{X+Y}^{\prime \prime }(1)=1.1$, the variance is $1.1+1.3-1.3^2=0.71$, agreeing with $0.3\cdot 0.7+2\cdot 0.5\cdot 0.5$.

Uncorrelated random variables are insufficient for the product identity. For a concrete counterexample, let $U$ be uniform on $\{-1,0,1\}$ and set $A=U+1$, $B=U^2$. Then $\mathrm{Cov}(A,B)=\mathbb{E}[U^3]=0$, but $\mathbb{P}(A+B=0)=0$, whereas $G_A(0)G_B(0)=1/9$. Zero covariance controls one mixed moment, not the full joint probability mass function.

If $f(x)={\sum }_{n\ge 0}{a}_n{x}^n$ has $a_0\ne 0$, its reciprocal has a unique formal power series $1/f(x)={\sum }_{n\ge 0}{b}_n{x}^n$. Equating coefficients in the Cauchy product $f\cdot (1/f)=1$ gives the displayed recurrence relation. In particular,For a convergent power series, continuity and $f(0)\ne 0$ give a neighborhood without zeros, where the reciprocal is analytic and this series converges. Its radius need not equal the original radius: zeros of $f$ can introduce closer reciprocal singularities.