Balanced-splitter twin-Fock output distribution Created 2026-10-20 Updated 2026-10-25
For two identical bosonic input populations of in a balanced two-mode mixer, only even occupancies occur at either output. Expanding and retaining normalized number-state factorials gives the displayed law. Its sum is one by the generating function .
Bernoulli number Created 2026-10-05 Updated 2026-10-13
The Bernoulli numbers are a sequence of rational numbers that turns integer power sums into exact polynomials. The same numbers describe corrections when a discrete summation is compared with an integral. For example, the sum of squares is : the leading term is an integral, while the last two terms repair the difference between area and sampled values.
We use throughout. The defining exponential generating function is
Here is the exponential function and is a factorial; in particular, the coefficient of is , rather than . At the quotient has limiting value one. The identity can be read algebraically as a formal power series, or as a convergent series for .[ref]
To compute the numbers, multiply by and compare coefficients. The resulting recurrence relation, with binomial coefficients, is
Thus , , and give , , and . Continuing gives
The recurrence relation agrees with equation 24.5.3 after replacing its index by .[ref]
Why do so many values vanish? Put . Direct substitution gives , so is an even function. Its odd power series coefficients vanish: for every positive integer . The exception matters. The alternative convention obtained from has and exactly the same other values. A formula copied between conventions must also retain its summation endpoints.
Historically, integer power sums were studied before the modern Bernoulli number notation. A historical study examines formulas published in 1631 and distinguishes those separate formulas from encoding all exponents using one sequence of constants. This is a useful motivation for the generating function, without assigning all discovery to a single moment. [ref]
Binary partition 2026-10-20
An integer partition in which every part is a power of two. Its generating function is , because the factor indexed by chooses the multiplicity of the part .
Board tiling 2026-10-14
Covering a finite board with specified tiles without gaps or overlaps. Counting board tilings connects local placement rules to a recurrence relation and a generating function.
Convolution theorem Created 2026-09-24 Updated 2026-10-14
For Lebesgue integrable functions on , use the Fourier transform convention . Then
Thus the integral combining all translated products becomes an ordinary multiplication at each frequency. Different Fourier transform normalizations can place a constant in this identity; fixing the convention prevents that ambiguity. Its use in filtering is illustrated by [ref].
For the indicator function ,
with . Therefore the triangular function has Fourier transform . The extra factor of the sinc function improves the large-frequency bound from a constant times to one times , matching the smoother output in the overlap picture. Fourier decay of repeated interval convolutions extends this calculation to further repetitions.
For a proof outline, Fubini's theorem permits exchanging the two integrals because the integral of over is . Set in the inner integral:
The factorization of the complex exponential is the mechanism behind the simplification. The discrete convolution version similarly turns coefficient sums into products of generating functions.
The cotangent partial-fraction expansion gives, on ,
The Bernoulli number generating function gives the same Laurent series in another form:
The term cancels the separate ; the higher odd Bernoulli numbers vanish. Comparing Laurent coefficients therefore gives , which is the stated real formula because . The cotangent partial-fraction expansion justifies the convergent expansion before the coefficient comparison; a finite plot of partial sums alone would not prove the infinite identity.
Discrete convolution Created 2026-09-24 Updated 2026-10-14
For sequences indexed by the integers, discrete convolution adds products whose indices sum to the output index:
For finite sequences, treat every unspecified entry as zero; the sum then has finitely many nonzero terms. For infinite sequences, a convergence hypothesis is needed, for example absolute summability of both sequences.
Take at indices and at indices . Their convolution is at indices :
Equivalently, : add an unshifted and a one-step shifted copy of . This explains the output by superposition, with every index included.
Figure 1.
Discrete convolution combines index pairs, shifted copies, polynomial coefficients and outcome counts
. Details.
The same products appear in polynomial multiplication and generating functions:
A term times contributes to coefficient , precisely the index condition in discrete convolution. In probability, counts the outcomes of two independent fair coin tosses by their number of heads, while counts the outcomes of one more toss. Dividing the output by eight gives the probability mass function of the binomial distribution with and . No new arithmetic is needed to pass from coefficient multiplication to counting independent sums.
The full finite convolution is different from circular convolution, where indices wrap modulo a chosen length. Wrapping this four-term output to length three adds its last entry to its first and gives . When using a discrete Fourier transform to compute the full convolution, zero padding to length at least the sum of the input lengths minus one prevents this wraparound. [ref]
In a bipartite graph, a self-avoiding walk ends in its starting class exactly when it has even length. If degrees are bounded by , deleting the last edge gives and hence for . Thus these generating functions have the same radius of convergence.
Galton-Watson process Created 2026-09-24 Updated 2026-10-13
A Galton-Watson process is a branching process that counts individuals by generation. Start with one ancestor, , and let all offspring counts be independent and identically distributed random variables taking nonnegative integer values with a common offspring distribution. Then
The empty sum is zero: zero is an absorbing state, so once a generation is empty every later generation is empty. The same offspring distribution applies to every individual in every generation. [ref]
For a concrete offspring distribution, take , , , and for . An individual has no children with probability , one with probability , and two with probability . The offspring expected value is . A possible sequence of generation sizes is : two children need not lead to a permanently growing family.
The probability generating function gives the exact generation probability distributions through branching-process generating-function iteration. With and , the second generation has
Thus and . The figure shows full generation probability mass functions, computed by polynomial function composition, through generation six; no simulated frequencies are used.
Figure 1.
Exact Galton-Watson generation distributions: growing means and increasing extinction mass
. Details.
The contrast is striking: the expected generation size in a Galton-Watson process grows as , while the branching extinction probability is . By generation six, although . Larger surviving families carry the rising expected value; that mean is an average over possible families, not a forecast of one family's path. The Galton-Watson extinction fixed point turns an unbounded number of future generations into a single equation for this probability.
The historical question was the disappearance of surnames passed through male descendants. In Watson and Galton, On the Probability of the Extinction of Families, pages 139–140, Francis Galton formulates a constant-law model counting sons who reach adulthood, and Watson computes later generation probability distributions by composing generating functions. Those are assumptions of their model, rather than a claim that actual human reproduction follows this offspring distribution.
Gaussian binomial coefficient Created 2026-10-13 Updated 2026-10-20
A Gaussian binomial coefficient refines an ordinary binomial coefficient into a polynomial that remembers a size statistic. For nonnegative integers and , write
The product represents a polynomial; it is not an instruction to divide by zero when or a denominator vanishes. The Gaussian binomial coefficient recurrence gives a way to compute it with only addition and multiplication. The empty product for is one, and as well. Setting after obtaining the polynomial recovers .
For example,
At this gives six objects, but its coefficients reveal how those six objects are distributed across sizes : 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 to . A north step at horizontal coordinate contributes shaded cells to its left. The six step words have total shaded areas .
Figure 1.
The six lattice paths counted by , weighted by the number of shaded cells
. Original exact enumeration of paths with two north and two east steps. Reading shaded row lengths from top to bottom gives a partition in a rectangle. Equal-sized diagrams contribute to the same coefficient. Details.
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 is a prime power, the value counts the -dimensional vector subspaces of . Thus the same expression that counts six paths at counts 35 two-dimensional subspaces of at . 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 denotes the formal variable, while denotes a finite field's cardinality when we evaluate the polynomial. The interpretation using a finite field requires to be a prime power; evaluating the polynomial at an arbitrary number does not construct a field of that size.
Generating function Created 2026-10-07 Updated 2026-10-14
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 ; in counting problems, the coefficient records the number of objects of size . The variable initially marks size: it need not be assigned a numerical value. Coefficient extraction writes this recovery as . One compact expression can therefore answer infinitely many counting questions, while explaining how their answers fit together.
Start with two contributions: choose from and from , with exactly one option at each allowed value. Their individual ordinary generating functions are the polynomials and . To count ordered pairs by total , multiply:
The coefficients count the ways to obtain totals zero through three. For total two, the possibilities are and ; the two corresponding monomials both contribute . There are six ordered pairs altogether, agreeing with .
Figure 1.
Polynomial multiplication groups six ordered choices by their total contribution
. Details.
If the first contribution has two distinguishable choices when , replace by . Its product with becomes . 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 gives
For 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 with tiles of lengths one and two, without gaps or overlaps. Let count these tilings. There is exactly one empty tiling, so , and . Removing the first tile leaves a board shorter by one or two, giving the recurrence relation
These are the Fibonacci numbers shifted by one index: under the convention , . Keeping the empty tiling is essential to both the counting rule and the resulting ordinary generating function.
Figure 2.
Length-one and length-two tiles give five coverings of a length-four board and the Fibonacci recurrence
. Details.
For , the empty board or a first tile followed by a remaining tiling gives
Equivalently, : each factor chooses one tile, and counts pieces while the exponent of records total length. The same ordinary generating function counts ordered histories of two repeatable actions costing one and two units. Histories and 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 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 , the reciprocal of the golden ratio. At , the rational function equals , 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 . A counting generating function also differs from a probability generating function, whose coefficients must be nonnegative and sum to one.
Kravchuk polynomials Created 2026-10-14 Updated 2026-10-18
These polynomials are orthogonal for a binomial distribution weight and encode the coefficient transformation in the MacWilliams identity. Their generating function follows by expanding the two factors:
For binary linear codes, . Expanding the factors gives , where binomial coefficients outside their usual integer range are zero. Orthogonality follows by multiplying generating functions and summing over with weight : the result is , whose coefficient of is zero for and for .
The left and right transverse oscillator sectors each have generating function . Its coefficient satisfies . Closed-string level matching requires equal levels but leaves their polarizations independent, so . With , the exponential is with . The smooth rest-mass density is proportional to , since . This distinguishes degeneracy per level from density per unit mass. The polynomial prefactor matters at the boundary of canonical convergence.
A horizontal run has generating function . Decomposing each walk into gives . Thus and . The exponential growth rate is , furnishing a strict lower bound greater than two for the connective constant of all square-lattice self-avoiding walks.
Ordinary generating function Created 2026-09-28 Updated 2026-10-14
This is the power-series specialization of a generating function.
The ordinary generating function of a sequence is the formal power series . Algebraic identities for encode recurrences and counting constructions for the coefficients.
Partition of an integer Created 2026-09-28 Updated 2026-10-14
A partition of a nonnegative integer records a way to write as a sum of positive integers, with the order of the summands ignored. Its canonical notation is a finite sequence
We write , call the its parts, and call its length. Trailing zero parts may be appended for calculations without changing the partition of an integer; zero has the unique empty partition of an integer, of length zero. Thus , and describe the same partition of an integer of five. The Young diagram below makes its two parts visible as rows of three and two cells.
The seven partitions of an integer of five are
This is a different object from a set partition: specifies block sizes, whereas a set partition must also specify which elements belong to each block.
Why this is useful: a partition of an integer is a compact description of a shape, yet it also labels an irreducible representation of a symmetric group over the complex numbers, realized by a Specht module. It therefore connects arithmetic decompositions, Young diagrams, and representation theory of the symmetric group. The generating function for partitions with bounded parts gives another way to count such shapes. Historically, Euler studied these counting problems using generating functions; his [ref] documents this early development.
Write the integrand, without its common overall factor, as . Keep each constant Grassmann variable on the left. For the first supersymmetry component, varying the bosonic term gives
Varying its fermion term gives . The plus sign in the second term comes from moving the odd parameter past . The middle terms cancel and the rest form . The second supersymmetry component similarly gives . Hence, off shell,
This proves the local total-derivative identity for rigid worldsheet supersymmetry; the action is invariant when the corresponding boundary flux vanishes and the transformation preserves the allowed fields. A constant parameter preserves a periodic boson and a periodic fermion. In a Neveu–Schwarz sector, however, is antiperiodic for constant and does not preserve the periodic boson. Thus the bulk identity does not supply a global constant supercharge in every spin sector. This is the spin-structure obstruction to constant worldsheet supersymmetry; the local superconformal formulation handles the different sectors consistently.
For independent field variations, integration by parts gives bulk terms
The equations of motion are therefore
For variations vanishing at the temporal ends, the spatial seam term is proportional to the difference between its values at and of
The bosonic part cancels for closed string periodicity, also in a fixed winding sector. For a real fermion impose and the same relation on its variation. Seam cancellation requires , so the two untwisted possibilities are periodic, (Ramond sector), or antiperiodic, (Neveu–Schwarz sector). The two chiralities of a closed string can choose these signs independently, giving R–R, NS–NS, R–NS and NS–R sectors. This discussion assumes the ordinary Lorentz-invariant untwisted boundary conditions of the flat theory.
The chiral equations and boundary signs give the following Fourier series
where in R and in NS. Thus integer or half-integer modes follow directly from the Fourier series monodromy. With the conventional string oscillator normalization their anticommutation relations and reality conditions are
For an open string the endpoint gluing identifies the two sets of coefficients, leaving one R or NS tower.
In ten-dimensional light-cone gauge in string theory, the eight transverse bosonic modes have positive integer level and each NS fermionic creator has a positive half-integer level. For the unprojected low levels of the open RNS string, all states through in the NS sector are
The antisymmetric index restrictions are consequences of fermionic anticommutation; the boson–fermion pair has all 64 choices. The displayed partitions exhaust levels at most . Here the NS normal-ordering constant of a string is .
In the R sector , and the zero modes satisfy . Thus generate the Ramond zero-mode Clifford algebra. The unprojected ground states span a sixteen-dimensional transverse spinor space, . All states in the requested range are
There is no intervening half-level, since all nonzero R modes have integer level. Acting with the zero modes only moves within the ground spinor space and does not generate further independent copies.
The GSO projection keeps odd NS fermion-excitation parity, removing the tachyonic vacuum and the entire NS level. In R it keeps one eigenvalue of total fermion parity, whose zero-mode part is spinor chirality. It leaves eight massless spinor states. At R level one, the retained families are and , of opposite ground chirality, so there are states. The retained NS states are spacetime bosons and the R states spacetime fermions. Consequently the retained levels have at mass zero and at , with no tachyon.
Equality at every higher mass level follows from the standard Jacobi abstruse identity, or equivalently the equality of the transverse generating functions
The left side counts the projected NS bosons, the right side the projected R fermions. Their common coefficients start . This consistent truncation yields spacetime supersymmetry; the bulk worldsheet symmetry alone would not remove the tachyon or impose the projection.
Use units . In critical light-cone gauge in string theory, each chiral sector of the closed bosonic string has 24 transverse string oscillator species. Their generating function is
Each factor sums the independent occupation numbers of the string oscillators at level . For with , the modular transformation of the Dedekind eta function gives
Extract the coefficient by a contour integral and apply the saddle-point approximation to the exponent . The saddle is , with exponent and second derivative . The factor gives , and the Gaussian width gives . Hence
For a noncompact closed string, closed-string level matching imposes equal left and right levels, but does not correlate their transverse polarizations. Therefore the large-level degeneracy of a closed bosonic string is
The mass relation is . Thus with
Distinguish degeneracy per discrete level from a smoothed density per unit rest mass. Since , the latter is
The exponential growth comes from the many ways of distributing string oscillator energy along a string; it is much faster than a fixed finite collection of particle species. The corresponding high-energy entropy is , so its microcanonical temperature tends to . Additional energy can go into very long strings rather than raising the temperature substantially.
The Boltzmann suppression competes with this exponential density. For the string oscillator rest-mass sum alone the large- tail is . It converges for and fails for . To include translational states in 25 noncompact spatial dimensions, take the one-string partition function per unit spatial volume. At large ,
This follows by expanding the energy as and doing a Gaussian momentum integral. Its high-mass contribution is consequently proportional to
This integral is finite at , although nonanalytic there: its first twelve derivatives in are finite, while the thirteenth diverges. The endpoint expansion contains a term proportional to . Thus one must not assert that the canonical partition function necessarily diverges exactly at ; the polynomial prefactor and the spatial spectrum matter. This is the finite canonical partition function at the bosonic Hagedorn threshold distinction. The multi-string ideal gas has the same leading Hagedorn threshold, since the higher occupation-cycle terms probe , , and are nonsingular at .
There is also a spacetime diagnosis. Euclidean temperature makes time a circle of radius . A string oscillator ground state winding once around that circle, with zero momentum number, has
It becomes massless at and tachyonic for . This thermal winding instability of a closed bosonic string signals failure of the perturbative low-temperature gas and motivates a transition to a different high-energy phase, often described in terms of long-string or winding-mode condensation. Free state counting fixes the threshold and its singular behavior, not the interacting phase's endpoint or the order of a transition.
Finally, the ordinary bosonic tachyon is already an infrared instability at zero temperature. The above canonical discussion is a formal analysis of the high-level spectrum with that separate infrared problem regulated. It does not establish a stable thermal vacuum of the unmodified bosonic theory; an actual equilibrium transition requires an appropriate stable setting and control of interactions.
The generating function for integer partitions is , since independently choosing the multiplicity of each part size gives a geometric series. Applying the parameterization in 5(a),
Unique factorization of monic polynomials shows
Indeed the left side counts monic polynomials with nonzero constant term; in degree there are choices. Reordering the formal products is legitimate because only finitely many factors contribute to any fixed coefficient. Substituting for each gives the conjugacy-class generating function for finite general linear groups:
The constant term corresponds to the trivial zero-dimensional group.
Count oscillator polarizations at fixed center-of-mass momentum. In a critical closed bosonic string, each chiral sector has 24 transverse oscillator species. A species at frequency can be occupied times, so its contribution is . The full chiral generating function is therefore
The two sectors are independent, while closed-string level matching restricts their oscillator numbers to the same . Thus the number of states at the closed-string mass level is , not .
Put , with . The Dedekind eta function obeys
The transformed argument has large imaginary part, so its product approaches one and . Hence
This establishes the singular exponential as well as its power prefactor. The corrections to the transformed eta product are exponentially small in .
The Cauchy coefficient formula, followed by , gives a steepest-descent integral with leading form
Let . The saddle of is
Along the vertical steepest-descent direction , the quadratic part is . Thus the saddle-point approximation gives the Gaussian prefactor
The point supplies the largest exponential contribution. At another fixed root of unity of order , the corresponding modular singularity gives a smaller exponential , so it does not change this leading asymptotic. Squaring the chiral result gives the large-level degeneracy of a closed bosonic string
Replacing by gives the equivalent usual leading asymptotic. The power matters: the two-sector degeneracy is not just an unspecified exponential.
Since , the exponential is with
Here Boltzmann's constant is one. Coarse-graining the levels into a density per unit rest mass introduces the Jacobian . Consequently
This is distinct from the degeneracy per level, whose power in is . The internal-state contribution to a canonical partition function behaves at large mass as
It converges for and diverges for . At , this particular internal rest-mass integral converges because of the power ; one should not discard the prefactor and claim divergence there without specifying the full thermodynamic ensemble. For example, including continuous momenta in 25 spatial dimensions multiplies the high-mass integrand by a factor proportional to , still leaving convergence of this ideal one-string integral at the endpoint, although sufficiently high derivatives are singular. Multi-string effects, volume and interactions affect the detailed limiting thermodynamics.
The leading microcanonical entropy grows as , with logarithmic corrections, so increasingly large energies are stored in increasingly excited, long strings rather than in an arbitrarily hot ordinary gas. The Hagedorn temperature is the boundary of canonical convergence from above in inverse temperature; extrapolating the free-string canonical description to fails. This counting does not settle the interacting phase above that scale. Also, the bosonic ground-state tachyon is a separate vacuum instability; the high-level asymptotic is meaningful as a formal spectrum calculation without asserting a stable bosonic thermal vacuum.