Generating Functions II (Exponential): Counting Labeled Structures

We introduce exponential generating functions (EGFs) and show that their product corresponds to labeled merging. We then derive the EGFs for Stirling numbers and Bell numbers, and prove Cayley's formula for labeled trees.

Folio Official

March 1, 2026

1 Definition of Exponential Generating Functions

Definition 1 (Exponential generating function).

Given a sequence

(a_{n})_{n \geq 0}

, the formal power series

\hat{A} (x) = n = 0 \sum \infty a_{n} \frac{x ^{n}}{n !}

is called the exponential generating function (EGF) of

(a_{n})

Remark 2.

While OGFs are naturally suited to counting unlabeled structures, EGFs are tailored to counting labeled structures. The crucial difference manifests in the interpretation of the product.

Example 3.

The EGF of

a_{n} = 1

(

n \geq 0

) is

\sum_{n \geq 0} x^{n} / n! = e^{x}

. The EGF of

a_{n} = n!

(the number of permutations) is

\sum_{n \geq 0} x^{n} = 1/ (1 - x)

2 Products and Labeled Merging

Theorem 4 (Product interpretation for EGFs).

Let

\hat{A} (x)

and

\hat{B} (x)

be the EGFs of sequences

(a_{n})

and

(b_{n})

, respectively. The coefficient

c_{n}

of the product

\hat{C} (x) = \hat{A} (x) \hat{B} (x)

is given by

c_{n} = k = 0 \sum n (k n) a_{k} b_{n - k} .

Proof.

\hat{A} (x) \hat{B} (x) = n = 0 \sum \infty (k = 0 \sum n \frac{a _{k}}{k !} \cdot \frac{b _{n - k}}{( n - k )!}) x^{n} = n = 0 \sum \infty \frac{1}{n !} (k = 0 \sum n (k n) a_{k} b_{n - k}) \frac{x ^{n}}{1}

Collecting terms in

x^{n} / n!

gives

c_{n} = \sum_{k = 0}^{n} (k n) a_{k} b_{n - k}

. □

Remark 5.

The appearance of the binomial coefficient

(k n)

reflects the operation of splitting

n

labels into two groups — one of size

k

bearing

a_{k}

structures and one of size

n - k

bearing

b_{n - k}

structures. This is the combinatorial meaning of "labeled merging."

3 Stirling Numbers of the First Kind

Definition 6 (Stirling number of the first kind).

The number of ways to decompose a permutation of

n

elements into exactly

k

disjoint cycles is called the unsigned Stirling number of the first kind, denoted

c (n, k)

[\frac{n}{k}]

. The signed Stirling number of the first kind is

s (n, k) = (- 1)^{n - k} c (n, k)

Theorem 7.

k = 0 \sum n c (n, k) x^{k} = x (x + 1) (x + 2) \dots (x + n - 1) = x^{(n)}

where

x^{(n)}

denotes the rising factorial.

Proof.

We proceed by induction on

n

. When

n = 0

, both sides equal

1

(the empty product). From the identity

x^{(n)} = x^{(n - 1)} (x + n - 1)

, we obtain the recurrence

c (n, k) = c (n - 1, k - 1) + (n - 1) c (n - 1, k)

. Combinatorially, this corresponds to the following dichotomy for the element

n

: either

n

forms a new cycle by itself (contributing

c (n - 1, k - 1)

) or

n

is inserted into one of the

n - 1

possible positions within an existing cycle (contributing

(n - 1) c (n - 1, k)

). □

4 EGF for Stirling Numbers of the Second Kind

Theorem 8.

The EGF for the Stirling numbers of the second kind is

n = k \sum \infty S (n, k) \frac{x ^{n}}{n !} = \frac{( e ^{x} - 1 ) ^{k}}{k !} .

Proof.

The series

e^{x} - 1 = \sum_{n = 1}^{\infty} x^{n} / n!

is the EGF for nonempty labeled sets. Consequently,

(e^{x} - 1)^{k} / k!

is the EGF for partitions of a labeled set into

k

nonempty blocks (dividing by

k!

because the blocks are unordered). This is precisely the definition of the Stirling number of the second kind. □

5 Bell Numbers

Definition 9 (Bell number).

The total number of partitions of an

n

-element set is called the

n

-th Bell number,

B_{n}

. That is,

B_{n} = \sum_{k = 0}^{n} S (n, k)

Theorem 10.

n = 0 \sum \infty B_{n} \frac{x ^{n}}{n !} = e^{e^{x} - 1}

Proof.

Since

B_{n} = \sum_{k} S (n, k)

n = 0 \sum \infty B_{n} \frac{x ^{n}}{n !} = k = 0 \sum \infty \frac{( e ^{x} - 1 ) ^{k}}{k !} = e^{e^{x} - 1} .

□

6 Cayley's Formula via Prüfer Sequences

Theorem 11 (Cayley's formula (proof via EGFs)).

The number of labeled trees on

n

vertices is

n^{n - 2}

Proof.

Let

T (x)

denote the EGF for labeled rooted trees. A rooted tree consists of a root vertex together with an unordered collection of rooted subtrees attached to it, so

T (x)

satisfies the functional equation

T (x) = x e^{T (x)}

. Applying the Lagrange inversion formula:

[x^{n}] T (x) = \frac{1}{n} [y^{n - 1}] e^{n y} = \frac{1}{n} \cdot \frac{n ^{n - 1}}{( n - 1 )!} = \frac{n ^{n - 1}}{n !} .

Hence the number of labeled rooted trees on

n

vertices is

n^{n - 1}

. Since any of the

n

vertices can serve as the root, the number of labeled (unrooted) trees is

n^{n - 1} / n = n^{n - 2}

An alternative, more direct proof constructs an explicit bijection between labeled trees and Prü □

The EGF technique is remarkably powerful for counting labeled structures. When combined with the Lagrange inversion formula and the compositional formula, it provides a systematic approach to deriving a wide range of combinatorial identities.

Combinatorics Discrete Mathematics Textbook Generating Functions EGF

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Generating Functions II (Exponential): Counting Labeled Structures

Folio Official

March 1, 2026

1 Definition of Exponential Generating Functions

Definition 1 (Exponential generating function).

Given a sequence

(a_{n})_{n \geq 0}

, the formal power series

\hat{A} (x) = n = 0 \sum \infty a_{n} \frac{x ^{n}}{n !}

is called the exponential generating function (EGF) of

(a_{n})

Remark 2.

While OGFs are naturally suited to counting unlabeled structures, EGFs are tailored to counting labeled structures. The crucial difference manifests in the interpretation of the product.

Example 3.

The EGF of

a_{n} = 1

(

n \geq 0

) is

\sum_{n \geq 0} x^{n} / n! = e^{x}

. The EGF of

a_{n} = n!

(the number of permutations) is

\sum_{n \geq 0} x^{n} = 1/ (1 - x)

2 Products and Labeled Merging

Theorem 4 (Product interpretation for EGFs).

Let

\hat{A} (x)

and

\hat{B} (x)

be the EGFs of sequences

(a_{n})

and

(b_{n})

, respectively. The coefficient

c_{n}

of the product

\hat{C} (x) = \hat{A} (x) \hat{B} (x)

is given by

c_{n} = k = 0 \sum n (k n) a_{k} b_{n - k} .

Proof.

\hat{A} (x) \hat{B} (x) = n = 0 \sum \infty (k = 0 \sum n \frac{a _{k}}{k !} \cdot \frac{b _{n - k}}{( n - k )!}) x^{n} = n = 0 \sum \infty \frac{1}{n !} (k = 0 \sum n (k n) a_{k} b_{n - k}) \frac{x ^{n}}{1}

Collecting terms in

x^{n} / n!

gives

c_{n} = \sum_{k = 0}^{n} (k n) a_{k} b_{n - k}

. □

Remark 5.

The appearance of the binomial coefficient

(k n)

reflects the operation of splitting

n

labels into two groups — one of size

k

bearing

a_{k}

structures and one of size

n - k

bearing

b_{n - k}

structures. This is the combinatorial meaning of "labeled merging."

3 Stirling Numbers of the First Kind

Definition 6 (Stirling number of the first kind).

The number of ways to decompose a permutation of

n

elements into exactly

k

disjoint cycles is called the unsigned Stirling number of the first kind, denoted

c (n, k)

[\frac{n}{k}]

. The signed Stirling number of the first kind is

s (n, k) = (- 1)^{n - k} c (n, k)

Theorem 7.

k = 0 \sum n c (n, k) x^{k} = x (x + 1) (x + 2) \dots (x + n - 1) = x^{(n)}

where

x^{(n)}

denotes the rising factorial.

Proof.

We proceed by induction on

n

. When

n = 0

, both sides equal

1

(the empty product). From the identity

x^{(n)} = x^{(n - 1)} (x + n - 1)

, we obtain the recurrence

c (n, k) = c (n - 1, k - 1) + (n - 1) c (n - 1, k)

. Combinatorially, this corresponds to the following dichotomy for the element

n

: either

n

forms a new cycle by itself (contributing

c (n - 1, k - 1)

) or

n

is inserted into one of the

n - 1

possible positions within an existing cycle (contributing

(n - 1) c (n - 1, k)

). □

4 EGF for Stirling Numbers of the Second Kind

Theorem 8.

The EGF for the Stirling numbers of the second kind is

n = k \sum \infty S (n, k) \frac{x ^{n}}{n !} = \frac{( e ^{x} - 1 ) ^{k}}{k !} .

Proof.

The series

e^{x} - 1 = \sum_{n = 1}^{\infty} x^{n} / n!

is the EGF for nonempty labeled sets. Consequently,

(e^{x} - 1)^{k} / k!

is the EGF for partitions of a labeled set into

k

nonempty blocks (dividing by

k!

because the blocks are unordered). This is precisely the definition of the Stirling number of the second kind. □

5 Bell Numbers

Definition 9 (Bell number).

The total number of partitions of an

n

-element set is called the

n

-th Bell number,

B_{n}

. That is,

B_{n} = \sum_{k = 0}^{n} S (n, k)

Theorem 10.

n = 0 \sum \infty B_{n} \frac{x ^{n}}{n !} = e^{e^{x} - 1}

Proof.

Since

B_{n} = \sum_{k} S (n, k)

n = 0 \sum \infty B_{n} \frac{x ^{n}}{n !} = k = 0 \sum \infty \frac{( e ^{x} - 1 ) ^{k}}{k !} = e^{e^{x} - 1} .

□

6 Cayley's Formula via Prüfer Sequences

Theorem 11 (Cayley's formula (proof via EGFs)).

The number of labeled trees on

n

vertices is

n^{n - 2}

Proof.

Let

T (x)

denote the EGF for labeled rooted trees. A rooted tree consists of a root vertex together with an unordered collection of rooted subtrees attached to it, so

T (x)

satisfies the functional equation

T (x) = x e^{T (x)}

. Applying the Lagrange inversion formula:

[x^{n}] T (x) = \frac{1}{n} [y^{n - 1}] e^{n y} = \frac{1}{n} \cdot \frac{n ^{n - 1}}{( n - 1 )!} = \frac{n ^{n - 1}}{n !} .

Hence the number of labeled rooted trees on

n

vertices is

n^{n - 1}

. Since any of the

n

vertices can serve as the root, the number of labeled (unrooted) trees is

n^{n - 1} / n = n^{n - 2}

An alternative, more direct proof constructs an explicit bijection between labeled trees and Prü □

Combinatorics Discrete Mathematics Textbook Generating Functions EGF

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Generating Functions II (Exponential): Counting Labeled Structures

1 Definition of Exponential Generating Functions

2 Products and Labeled Merging

3 Stirling Numbers of the First Kind

4 EGF for Stirling Numbers of the Second Kind

5 Bell Numbers

6 Cayley's Formula via Prüfer Sequences

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

Generating Functions II (Exponential): Counting Labeled Structures

1 Definition of Exponential Generating Functions

2 Products and Labeled Merging

3 Stirling Numbers of the First Kind

4 EGF for Stirling Numbers of the Second Kind

5 Bell Numbers

6 Cayley's Formula via Prüfer Sequences

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry