Stirling number

related topics
{math, number, function}
{language, word, form}

In mathematics, Stirling numbers arise in a variety of combinatorics problems. They are named after James Stirling, who introduced them in the 18th century. Two different sets of numbers bear this name: the Stirling numbers of the first kind and the Stirling numbers of the second kind.

Contents

Notation

Several different notations for the Stirling numbers are in use. Stirling numbers of the first kind are written with a small s, and those of the second kind with a large S (Abramowitz and Stegun use an uppercase S and a blackletter S respectively). They are:

The notation of using brackets and braces, in analogy to the binomial coefficients, was introduced in 1935 by Jovan Karamata and promoted later by Donald Knuth; it is referred to as Karamata notation. The mathematical motivation for this type of notation, as well as additional Stirling number formulae, may be found on the page for Stirling numbers and exponential generating functions.

Stirling numbers of the first kind

Unsigned Stirling numbers of the first kind

(with a lower-case "s") count the number of permutations of n elements with k disjoint cycles.

Stirling numbers of the first kind (without the qualifying adjective unsigned) are the coefficients in the expansion

where (x)n is the falling factorial

Stirling numbers of the second kind

Stirling numbers of the second kind S(nk) (with a capital "S") count the number of ways to partition a set of n elements into k nonempty subsets. The sum

is the nth Bell number. If we let

(in particular, (x)0 = 1 because it is an empty product) be the falling factorial, we can characterize the Stirling numbers of the second kind by

(Combinatorialists also use the notation x^{\underline{k\!}} for falling factorial, and x^{\overline{k\!}} for rising factorial.[1] Confusingly, the Pochhammer symbol that many use for falling factorials coincides with the notation used in special functions for rising factorials.)

Full article ▸

related documents
Dyadic rational
T1 space
Algebraic number
C*-algebra
Magma computer algebra system
Real line
Regular space
Cayley's theorem
Alternative algebra
Partial fractions in integration
Subalgebra
Category (mathematics)
Nowhere dense set
BPP
Borel-Cantelli lemma
Double negative elimination
Euler's criterion
Decision problem
Weierstrass–Casorati theorem
Hash collision
NP-hard
Intersection (set theory)
Whittaker–Shannon interpolation formula
Polynomial time
Bézout's identity
Heaviside step function
CLU (programming language)
Syntactic sugar
Partial function
Commutative ring