A.5 Stirling numbers

To count the number of possible states of a model composed of a large number of agents, when they have at most countably many decision rules or behavioral pat­terns, is to count the number of random combinations of their choices.

The Stirling numbers can be introduced in at least two ways: by counting the number of distinct combinatorial structures as mentioned above, or by algebraic recursions. We use both ways; see Van Lint and Wilson (1992, p. 104). Other and older references are Jordan (1947), Riordan (1958), and David and Barton (1962, p.13). See also Sachkov (1996, Sec. 3.2). Abramovitz and Stegun (1968, p. 824) provides a useful summary of the properties of the Stirling numbers we develop below. We selectively discuss their properties in this section.

A.5.1 Introduction

In one sense, the simplest definition of the Stirling numbers is by identitites. Expand a descending factorial

into power series, that is, into Taylor series, as

The coefficients of the expansion define the Stirling numbers of the first kind. They are recovered by repeated differentiation as

and s(n, 0) = 0, where the symbol D represents differentiation with respect to x. The subscript means that the derivative is evaluated at 0. This definition is valid for nonnegative integers n and k ≤ n; see Jordan (1947, p. 142) and Riordan (1958, p. 33).

Equation (A.1) shows that (x)_n is the generating function of the Stirling numbers of the first kind.

The Stirling numbers of the second kind appear as coefficients of expansion of xⁿ in terms of the descending factorials:

These numbers are defined for nonnegative integer values of n and k.

We next use a Newton series expansion, which expresses f (x) in terms of its value and the values of finite differences expressed at a point (taken to be zero here), to relate the Stirling numbers of the second kind to finite-difference expressions. Let

with

where we see that the Stirling numbers of the second kind are given by

A.5.2 Recursions

Then, the Taylor series expansion (A.1) becomes

These are sometimes called signless or unsigned Stirling numbers of the first kind. This recursion relation has a natural interpretation in terms of the number of cycles of length k in random permutations of n objects or symbols, to which we return shortly. Equation (A.1) is now the generating function of the signless Stirling numbers of the first kind,

We have the exponential generating function for x^[n] as

We recover θ^[n] as the coefficient of sⁿ/n! of the righthand side:

Here we use a convention of extracting the coefficient of sⁿ by [sⁿ].

To derive algebraically the recursion formula satisfied by the Stirling num­bers of the second kind, note the identity for the difference operation

By dividing this relation by k! and recalling the definition in terms of the Newton series expansion, we deduce the recursion

Alternatively, we use (A.2) to express xⁿ'⁺¹ as

Exercise. Use this expression to find a closed-form expression for the coeffi­cient ∑(n; a₁, a₂,..., a_n) = S(n, m) in the expression

Multiplying both sides of (A.1) by tⁿ/n! and summing over n from zero to infinity, we obtain the exponetial generating function for the descending factorials as

More on the generating functions later.

These definitions do not reveal how these numbers are related to combina­torial problems in random maps and random permutations, but are useful in deriving the recursion relations they satisfy. These two kinds of numbers are also reciprocals of each other in that

A.5.3 Relations with combinatorics

Here, we give combinatorial derivations of the recursion relations. Stirling num­bers of the first kind are related to cycle structures of permutations. Since the set S = {1, 2,..., n} is finite, any permutation applied repeatedly to any el­ement of S will eventually return to it.

Let p(n, k) be the number of permutations of n objects with exactly k cycles. Then a permutation of {1, 2,..., n - 1} into k cycles can be made into a permutation with k cycles by inserting the object n after any of the sym­bols 1, 2,..., n - 1, that is, in n - 1 ways. Additionally, symbol n can be made a cycle of length one, and attached to any of the p(n - 1, k - 1) permutations to make them permutations of n objects with k cycles. We thus have

Withtheboundary conditions that p(0, 0) = 1 and that p(n, k) = 0 for negative integers n or k or for k greater than a positive n. In view of (A.4), this recursion relation and the boundary condition are identical with those for the unsigned Stirling numbers of the first kind; hence

for all values of the arguments.

A partition of a finite set [n] := {1, 2,..., n} into k parts is a collection of k subsets of S such that none of the subsets is empty, all are pairwise disjoint, and their union is the original set S. We may think of it as a single-valued map from S into k points (cells, boxes, or types). The number of such partitions is S(n, k), since it satisfies the same recursion as (A.5) and the same boundary conditions as the Stirling numbers of the second kind, because we can partition n - 1 points of S into k subsets and place n into any of these subsets in k ? S(n - 1, k) ways, or we can put n by itself as one subset and put the remaining n - 1 points into k - 1 subsets.

van Lint and Wilson (1992) define a Stirling number of the second kind as the cardinality of the set of all partitions of an n-set into k nonempty subsets.

Stanley (1983, Sec. 1.4) uses a random map construction. Consider a set of arbitrary maps of an n-set S into a set X with x elements. There are xⁿ such maps. Define S(n, k) to be the number of partitons of [n] into k blocks B₁, B₂,..., B_k. Then k!S(n, k) is the number of linearly ordered maps, as we see by making the correspondence f (i) = bj if i ∈ B_j.

Therefore,

The binomial coefficient is present because there are this many ways of choosing a subset Y of X with k elements. The recursions are used to show that these alternative definitions are equivalent.

A.5.4 Explicit expressions and asymptotic relations

Jordan (1947, p. 201) notes that

which can be verified directly by noting thateven though

a relation used by Harris (1960) in discussing random maps.

Exercise. Use this relation to show that ∑(n; a₁, a₂,..., a_n)* = c(n, m), where

The roots of the descending factorial (x )_n are r_i = i, i = 0, 1,..., n - 1. Therefore, the coefficients of x^k is given by

then it becomes

A.5.5 Asymptotics

Since we will be modeling situations with a large number of agents, and possibly a large number of types, we list here some asymptotic expressions for Stirling numbers for easy reference.

We have

for k = o (ln n),

where γ is the Euler constant. See Sachkov (1996, pp. 146,157) who also shows that

and

as n goes to infinity.