From set partitions to exact transfer: Stirling, Bell and Fubini numbers

Read side by side

An extended hand-worked example · Komorebi P.

One triangular table counts partitions of labelled objects into nonempty blocks. Constant and factorial weights on that same table generate Bell and ordered Bell (Fubini) numbers. We compute both from an explicit row, prove the general generating-function substitution and its inverse, trace polynomial and moment realizations, and identify the boundary between reversible data and lossy summaries.

No new mathematical result is claimed. The counting identities are classical. The purpose is to follow one explicit object through the coordinate, transfer, reconstruction and obstruction language used throughout the collection.

Run the existing factorial-weight experiment · Read the exact program · Download the verified results

The destination: two answers from the same partition row

Let \(S(n,k)\) be the Stirling number of the second kind: the number of partitions of an \(n\)-element labelled set into exactly \(k\) nonempty, unlabelled blocks. Set \(S(0,0)=1\), and let entries outside \(0\le k\le n\) be zero.

Our central object is

Adding these coordinates counts partitions without ordering the blocks:

A partition with \(k\) blocks can have those blocks ordered in \(k!\) ways. The same row, with its \(k\)-th coordinate multiplied by \(k!\), becomes

Thus

Here \(B_n\) denotes the Bell numbers and \(F_n\) denotes the ordered Bell, or Fubini, numbers. Some sources use a different symbol for \(F_n\); we use \(F\) consistently on this page.

The image is produced by the standalone Python program. Every cell is an exact integer, not a logarithmically rounded coefficient. The complete table is available as CSV.

1. Construct the triangular coordinates

For example, a three-element set has exactly three partitions into two nonempty blocks: \(\{1\}\mid\{2,3\}\), \(\{2\}\mid\{1,3\}\), and \(\{3\}\mid\{1,2\}\). Hence \(S(3,2)=3\).

To make a partition of \(\{1,\ldots,n\}\) into \(k\) blocks, inspect the last element \(n\).

It either forms a singleton block, leaving a partition of \(n-1\) objects into \(k-1\) blocks, or joins one of \(k\) blocks of a partition of \(n-1\) objects into \(k\) blocks. Therefore

Starting with \(S(0,0)=1\), this gives:

For example, \(S(5,3)=S(4,2)+3S(4,3)=7+3(6)=25\). The triangular recurrence determines the complete row with no numerical approximation.

We distinguish this recurrence from the site’s finite residue-packet and FIR-filter examples: the Stirling triangle is a triangular transformation across different sequence indices, not a fixed-length translation-invariant convolution.

2. Make the operator explicit

Let \(\mathcal S\) be the infinite lower-triangular matrix

If the input weights are \(a_k\), the output family is

For our two examples,

Equivalently, write \(D=\operatorname{diag}(0!,1!,2!,\ldots)\). The two maps are \(\mathcal S\) and \(\mathcal SD\) acting on the constant sequence \(\mathbf1\). All finite truncations of \(\mathcal S\) have diagonal entries \(S(n,n)=1\), and hence determinant one. The diagonal \(D\) is invertible over \(\mathbb Q\), although \(D^{-1}\) contains reciprocal factorials.

Here are the first five rows, with columns indexed from zero:

Applying it to \((1,1,1,1,1)^{\mathsf T}\) gives \((1,1,2,5,15)^{\mathsf T}\), while applying it to \((1,1,2,6,24)^{\mathsf T}\) gives \((1,1,3,13,75)^{\mathsf T}\).

One kernel, different inputs, different families. The choice of weight sequence is mathematical data, not an arbitrary display setting.

3. Undo the transfer exactly

Let \(s(n,k)\) denote the signed Stirling numbers of the first kind, defined by

They satisfy \(s(0,0)=1\) and

Why this is the inverse: for a positive integer \(x\), count all functions from an \(n\)-element set into an \(x\)-element set. Every function determines a partition into its \(k\) nonempty inverse-image blocks. After choosing that partition, there are \(x(x-1)\cdots(x-k+1)\) ways to assign distinct target labels to its blocks. Thus

The identity holds as a polynomial because it holds for every positive integer \(x\). Substitute the signed first-kind polynomial expansion and compare powers of \(x\). This gives \(\mathcal S\,s=I\). Both matrices are lower triangular with diagonal one, so the reverse product is also \(s\,\mathcal S=I\) in every finite truncation.

The two triangular matrices are inverses:

Thus knowing the complete sequence \((B_0,\ldots,B_n)\) recovers its original weight at \(n\), and similarly for Fubini:

For \(n=5\), the inverse coefficients are

The Fubini inverse works by direct arithmetic:

The Bell inverse gives

This inversion is not reconstructing an arbitrary Stirling row from just one Bell or Fubini value. It inverts the known triangular transform across the sequence of all preceding output indices.

Inspect the signed transfer matrix and its exact identity product.

4. Generate both families from exponential series

A second derivation checks the same arithmetic by an independent route. There are \(k!S(n,k)\) onto maps from an \(n\)-element set to \(k\) labelled targets. Inclusion and exclusion give

For fixed \(k\), sum over \(n\) as an exponential generating function:

Set \(u(t)=e^t-1\), which has zero constant term. Reweighting this identity yields two distinct generating functions:

These are exact identities of formal power series over \(\mathbb Q\). The sums are well defined coefficient by coefficient because \(u(t)^k\) starts at degree \(k\). No analytic convergence assumption is needed for the formal identities.

This makes the connection to the Euler and factorial-lane demonstrations precise: the Fubini generating function is another reciprocal series, but its denominator and indexing are different. The resulting coefficient family is not the Euler sequence.

The general input rule and its formal inverse

The two generating functions above are instances of a single, exact operation. For an arbitrary weight sequence \(a_0,a_1,\ldots\) over \(\mathbb Q\), write

Substitute the fixed-\(k\) identity from the start of this section, rearranging only coefficientwise finite sums:

The inverse substitution exists because \(e^t-1\) has zero constant term and linear coefficient one. Its compositional inverse is \(\log(1+u)\). Therefore

This is the formal-series counterpart of the signed-Stirling matrix inversion in Section 3. The two inversion methods act in different coordinate descriptions but recover the same input sequence. Here are four specializations of the one rule:

All four are classical substitutions. The point of the operator presentation is that changing the input weights does not require inventing a new triangular kernel, and the full output sequence retains its inverse. The checker also exercises this substitution on rational and alternating weight families beyond these four examples.

Two independent recurrence checks

Differentiate the Bell generating function:

For \(n=4\), this gives \(B_5=1+4+12+20+15=52\).

For Fubini, the reciprocal identity can be written \((1-u(t))F(t)=1\). Comparing the coefficient of \(t^n/n!\) gives, for \(n\ge1\),

In particular,

The standalone checker computes both families by Stirling rows and these independent recurrences. It also expands \(\exp(e^t-1)\) and the reciprocal \(1/(2-e^t)\) using exact rational series arithmetic, rather than floating-point evaluations at small \(t\).

5. A polynomial bridge: evaluation versus exponential moments

The preceding triangular formulas reveal a more general construction. Keep the row as a polynomial before applying any summary. Define the Touchard polynomial

For our central row,

Evaluating at \(z=1\) forgets the number of blocks but preserves the partition count: \(T_n(1)=B_n\). A different linear functional on the same polynomial produces the ordered Bell numbers. The gamma integral for an integer \(k\ge0\) is

Indeed, the integral is \(1\) for \(k=0\), and integration by parts gives \(I_k=kI_{k-1}\) for \(k\ge1\). This proves the factorial rule without numerical approximation.

Because \(T_n\) is a finite polynomial, we may integrate term by term, without an interchange of infinite series:

The entire computation at \(n=5\) is visible:

This distinguishes the operations precisely: Bell is polynomial evaluation; Fubini is an exponential moment of that polynomial. Neither operation requires an unrelated counting kernel.

A one-parameter family of exact transfers

For a nonnegative real parameter \(\lambda\), rescale the polynomial argument before taking the moment:

In particular,

The \(T_5(\lambda)\) column records polynomial evaluations. The \(F_5(\lambda)\) column records exponential moments after scaling the polynomial argument. These are distinct operations even when they use the same parameter. At \(n=0\), both polynomials give \(1\) for every parameter, consistent with \(S(0,0)=1\).

To derive the complete families, first preserve the formal coefficient variable \(z\):

These are formal identities over \(\mathbb Q[z][[t]]\) and \(\mathbb Q[\lambda][[t]]\), respectively. Each fixed coefficient of \(t^n\) involves only \(k\le n\). In particular, the reciprocal specialization \(\lambda=1\) gives exactly \(1/(2-e^t)\). For \(n\ge1\), its parameterized coefficients also satisfy

Two further operations on the Touchard family

The Stirling recurrence yields an exact polynomial differential rule:

The term \(S(n,k-1)\) contributes \(zT_n(z)\), and the term \(kS(n,k)\) contributes \(zT_n'(z)\). For example,

There is also a binomial addition law, obtained by multiplying the two Touchard EGFs from the preceding section:

At \(x=y=1\), it gives a second finite route to a parameter value:

The polynomial recurrence and addition identity connect the same counting coordinates to differentiation and binomial convolution. Neither requires interpreting the Stirling transform itself as a fixed-length FIR filter.

A second interpretation: geometric moments

The same reciprocal has a classical probabilistic realization. When \(\lambda>0\), let \(M\) be a nonnegative integer with

Its falling-factorial moments are \(\mathbb E[(M)_k]=k!\lambda^k\). To see this directly, put \(q=\lambda/(1+\lambda)\). Differentiate the geometric series \(1/(1-q)=\sum_{m\ge0}q^m\) \(k\) times and multiply by \(q^k\):

Dividing by \(1+\lambda\) gives \(k!\lambda^k\) exactly. Combine this with the basis identity from Section 3, \(m^n=\sum_k S(n,k)(m)_k\), to obtain

Here \((M)_k=M(M-1)\cdots(M-k+1)\) and the \(n=0\) convention is \(m^0=1\), including \(m=0\). The sum converges for \(\lambda>0\). At \(\lambda=1\) this becomes the classical ordered-Bell formula

This is an independent interpretation, not a claim that infinitely many terms are required to compute \(F_n\): the original finite Stirling row remains exact. The signed Stirling inverse still recovers the input moments \(k!\lambda^k\) from the complete prefix \((F_0(\lambda),\ldots,F_n(\lambda))\). A single output \(F_n(\lambda)\) does not recover its underlying row.

The checker verifies the parameter values, polynomial recurrences, geometric falling-factorial moments, formal generating functions, reciprocal identities and signed inversions using integers and rational fractions. Download the parameterized moment table alongside the earlier tables.

6. Split the reciprocal identity into even and odd packets

The reciprocal \(F(t)=1/(2-e^t)\) offers a useful direct bridge to Komorebi’s residue coordinates. Define

They retain even and odd coefficient addresses, respectively, so \(F=F_{\mathrm e}+F_{\mathrm o}\). In our exponential normalization,

The identity \(F=1+uF\), with \(u=e^t-1\), must respect these packet addresses. Write

An even term in a product comes from even times even or odd times odd. An odd term comes from the other two pairings. Therefore

This two-packet transfer system is exactly equivalent to \((1-u)F=1\): adding its two rows recovers the original reciprocal equation. It is not a different reciprocal function.

See the two transfer paths at coefficient five

The coefficient \(F_5\) receives the \(j\)-even contributions

and the \(j\)-odd contributions

The two packet contributions reconstruct the original recurrence:

No coefficient was inferred by interpolation. We partitioned a finite sum according to its residue and retained both children.

Extend to a three-packet decomposition

For any integer \(m\ge2\), define

The packets reconstruct \(F=\sum_rF_r^{(m)}\). Equivalently, over the formal series ring extended by a primitive \(m\)-th root of unity \(\zeta_m\),

Indeed, the average of \(\zeta_m^{\ell(n-r)}\) vanishes unless \(n\equiv r\pmod m\), when it equals one. This is the familiar roots-of-unity coefficient filter, now applied to the Fubini reciprocal.

For \(m=3\), the three packets begin as follows:

From residue filtering to a coupled transfer

A coefficient filter alone tells us which addresses belong to each packet. The full reciprocal equation gives more: an exact transfer law between packets. Put

Taking residue \(r\) of the identity \(F=1+uF\) gives, for every integer \(m\ge2\),

For \(m=3\), suppress the superscript and write the complete circulant system:

Because every \(u_a\) has zero constant coefficient, this matrix has identity constant term and is invertible as a formal power-series matrix. The three-packet equation is equivalent to the original reciprocal, not an approximation or a different sequence.

At degree five the output belongs to residue \(2\bmod3\). Splitting the original binomial recurrence by the tap degree \(j\bmod3\) gives

Thus \(30+380+131=\boxed{541}\). The checker tests the entire coupled identity coefficient by coefficient for moduli \(2,3,4,5\), rather than checking packet reconstruction alone. These are finite algebraic transfers of the already established formal reciprocal.

The coefficient checker uses integer residue indexing and exact rational series. It does not approximate complex roots numerically. The three-packet decomposition is a refinement of coefficient addresses, not a new formula for \(F_n\) or an assertion about new transcendental values.

Download all reciprocal packet coefficients.

7. A real obstruction: two summaries do not determine the whole row

We have distinguished two reversible maps:

• The full Stirling triangle acting on a complete input sequence has a signed-Stirling inverse.
• Multiplying every \(k\)-th coordinate by \(k!\) is invertible over \(\mathbb Q\).

But reducing an \(n\)-th row to one or two scalars is a different operation. Let

This map need not be injective when the row has at least three free coordinates. We can exhibit the loss without any numerical search. At \(n=4\), consider

Both profiles have the same two outputs:

Their difference lies in the simultaneous kernel:

because

The profile \(w\) is not claimed to be another valid Stirling row. Its purpose is to prove that the linear aggregation map cannot reconstruct arbitrary coordinate data even when both scalar outputs are supplied. The genuine Stirling row is uniquely specified by its recurrence and boundary conditions, which are additional information absent from \(L\).

This is the same distinction as our operator and wavelet demonstrations: an invertible representation can be followed by a lossy measurement. A failure of the latter does not invalidate the former.

The sharp recovery distinction

The failure above concerns two scalar summaries, not a failure of all finite representations. Retain instead the entire parameterized polynomial for an arbitrary coordinate profile \(x=(x_0,\ldots,x_n)\):

Its coefficients reconstruct every coordinate:

Over \(\mathbb Q\), values at \(n+1\) distinct parameter points also recover this degree-at-most-\(n\) polynomial by interpolation. For consecutive samples \(0,1,\ldots,n\), one exact construction is

Here is the same \(n=4\) obstruction, now evaluated at additional parameter addresses:

Indeed, \(P_v(\lambda)=\lambda+14\lambda^2+36\lambda^3+24\lambda^4\), while \(P_w(\lambda)=5\lambda+4\lambda^2+42\lambda^3+24\lambda^4\). One extra sample at \(2\) distinguishes these particular profiles, but does not generally identify an arbitrary five-coordinate profile. The complete five-sample table does: exact interpolation recovers \(v=(0,1,7,6,1)\) and, separately, \(w=(0,5,2,7,1)\).

We have therefore exhibited both sides of a precise boundary: complete triangular outputs are invertible across indices, complete parameter polynomials are recoverable within a fixed row, and the two fixed summaries \(B_n,F_n\) are insufficient for unrestricted coordinate recovery. The candidate \(w\) remains a non-Stirling profile.

Download the exact interpolation and candidate comparison.

Inspect the obstruction witness, coordinate by coordinate.

8. What the checks prove, and what they do not

The mathematical identities above are derived from partition counting, lower-triangular inversion, formal exponential series, and the orthogonality of roots of unity. The program independently checks their finite consequences.

The standalone checker uses only standard-library exact integers and fractions. It checks:

• Stirling rows against independently enumerated set partitions for small \(n\).
• Factorial-weighted rows against inclusion and exclusion for onto maps.
• Both orders of multiplication of the truncated Stirling and signed-Stirling matrices.
• Inversion of the Bell and Fubini sequence prefixes to their distinct input weights.
• The Bell exponential series, Fubini reciprocal series, and separate binomial recurrences.
• The general Stirling-series substitution and its formal logarithmic inverse for additional rational input families.
• The Touchard differential recurrence and binomial addition law.
• Exact polynomial interpolation that recovers complete row coordinates, contrasted with two-scalar noninjectivity.
• The Touchard polynomial bridge, scaled gamma moments, signed inverse, and parameterized reciprocal recurrences.
• Coupled reciprocal packet transfers for moduli two through five, including the three-residue coefficient-five paths.
• The explicit \(n=4\) aggregation obstruction.

Finite computation is a regression check, not a substitute for the displayed general proofs. All sequences and identities here are classical. The broader analytic and formalized Special Functions volume has its own claim map and scope. Nothing on this page asserts new Lean compilation, universal recovery from finite summaries, or new results on unrelated conjectures.

9. Reproduce the exact records

Python 3.10 or later is sufficient; NumPy, plotting packages and external services are unnecessary. From the collection checkout run:

python -B examples/stirling_bell_fubini.py
python -B examples/stirling_bell_fubini.py --output stirling-results

The second command regenerates the exact integer CSVs, rational packet table, SVG diagram and JSON verification record. The publication build generates these outputs from this same retained program, records their SHA-256 digests and makes a source-and-results archive; the website checks its links and file identities separately.

Read the full Python source · Download the Python checker · Download the source-and-results ZIP

Parameterized moment bridge (CSV) · Exact row reconstruction (CSV) · Stirling rows (CSV) · Sequence and inverse checks (CSV) · Signed inverse matrix (CSV) · Reciprocal packets (CSV) · Obstruction witness (CSV) · Exact SVG diagram · Verification record (JSON)

Original literature and related worked examples

The Special Functions sequence atlas, lessons S07 and S08 already gives the Bell and factorial-weighted Fubini rows, the generating functions, and the comparison plots. Its Special Functions monograph supplies the broader sequence setting and separate Lean coverage. The existing sequence-shapes playground lets readers modify parameters and inspect 2D and 3D sequence maps.

For the reciprocal and residue machinery, see the Euler extended example, factorial lanes, and Paper IV. These links establish related constructions, not a claim that Euler, factorial-lane and Fubini coefficients are identical.

All demonstrations · All worked examples · Evidence guide