Stirling number
Stirling numbers are two families of positive integers that count specific partitioning and permutation structures: the Stirling numbers of the second kind, denoted S(n,k) or \left\{ \begin{array}{c} n \\ k \end{array} \right\}, count the number of ways to partition a set of n distinct elements into exactly k non-empty unlabeled subsets, while the Stirling numbers of the first kind, denoted \left| \begin{array}{c} n \\ k \end{array} \right|, count the number of permutations of n elements that consist of exactly k disjoint cycles (with a signed variant s(n,k) = (-1)^{n-k} \left| \begin{array}{c} n \\ k \end{array} \right| often used in generating functions).[1][2] These numbers, named after the Scottish mathematician James Stirling, play a central role in enumerative combinatorics and appear in the change-of-basis transformations between the monomial basis x^n and the falling factorial basis (x)_n = x(x-1)\cdots(x-n+1) in polynomial expansions.[2] Specifically, the identity x^n = \sum_{k=0}^n S(n,k) (x)_k expresses powers in terms of falling factorials using second-kind numbers, while the inverse relation (x)_n = \sum_{k=0}^n s(n,k) x^k (with signed first-kind numbers) converts falling factorials to powers.[2] Both types satisfy similar recurrences: for second-kind numbers, S(n+1,k) = k \cdot S(n,k) + S(n,k-1), reflecting the choice of placing the (n+1)-th element into an existing subset or a new one; for unsigned first-kind numbers, \left| \begin{array}{c} n+1 \\ k \end{array} \right| = n \cdot \left| \begin{array}{c} n \\ k \end{array} \right| + \left| \begin{array}{c} n \\ k-1 \end{array} \right|, corresponding to inserting the (n+1)-th element into an existing cycle or starting a new one.[1][2] Beyond partitions and permutations, Stirling numbers extend to broader applications, including the enumeration of surjective functions (where the number of surjections from an n-set to a k-set is k! \cdot S(n,k)), Bell numbers (total partitions, B_n = \sum_k S(n,k)), and connections to algebraic structures like the cycle index of the symmetric group or derivatives of generating functions such as \ln(1+x).[1] They also arise in probability (e.g., Ewens sampling formula), numerical analysis (e.g., finite difference approximations), and even physics (e.g., quantum mechanics via cycle decompositions).[2] Values are zero when k > n or k = 0 (except trivial cases), with S(n,1) = 1 and S(n,n) = 1 for second-kind, and similarly \left| \begin{array}{c} n \\ 1 \end{array} \right| = (n-1)! and \left| \begin{array}{c} n \\ n \end{array} \right| = 1 for first-kind, highlighting their boundary behaviors in combinatorial counts.[1]Definitions and Notation
Stirling Numbers of the First Kind
The signed Stirling numbers of the first kind, denoted s(n,k), are integers defined such that |s(n,k)| equals the number of permutations of n elements with exactly k cycles (where fixed points count as 1-cycles), and the sign is given by (-1)^{n-k}. The unsigned versions, often denoted c(n,k), \left[ \begin{array}{c} n \\ k \end{array} \right], or |s(n,k)|, simply count these permutations without the sign.[3][4] This combinatorial interpretation arises from decomposing permutations into disjoint cycle structures, where s(n,k) = 0 if k > n or k < 0, and s(n,n) = 1 corresponding to the identity permutation with n fixed points.[3] In standard notation, s(n,k) distinguishes the signed first-kind numbers from the unsigned second-kind Stirling numbers S(n,k), which count set partitions.[3] These signed numbers serve as coefficients in the polynomial expansion of the falling factorial: x^{\underline{n}} = x(x-1)\cdots(x-n+1) = \sum_{k=0}^n s(n,k) \, x^k. For example, with n=3, x(x-1)(x-2) = x^3 - 3x^2 + 2x = \sum_{k=1}^3 s(3,k) \, x^k, yielding s(3,1) = 2, s(3,2) = -3, and s(3,3) = 1.[3] This expansion facilitates change-of-basis transformations between power basis polynomials and falling factorials, with the second-kind numbers providing the inverse relation.[3] Basic values of the signed Stirling numbers of the first kind form a triangular array, with rows indexed by n and columns by k = 1 to n (since s(n,0) = 0 for n > 0). The following table shows values up to n=5, derived from the unsigned counts adjusted by the sign (-1)^{n-k}:[3][4]| n \setminus k | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 1 | ||||
| 2 | -1 | 1 | |||
| 3 | 2 | -3 | 1 | ||
| 4 | -6 | 11 | -6 | 1 | |
| 5 | 24 | -50 | 35 | -10 | 1 |
Stirling Numbers of the Second Kind
Stirling numbers of the second kind, denoted S(n, k) or \left\{ \begin{array}{c} n \\ k \end{array} \right\}, count the number of ways to partition a set of n distinct objects into k non-empty unlabeled subsets.[6] These numbers arise in various combinatorial contexts and play a core role in expressing powers of a variable in terms of falling factorials, providing a change of basis between the monomial basis \{x^n\} and the falling factorial basis \{(x)_k\}, where the falling factorial is defined as (x)_k = x(x-1)\cdots(x-k+1) for k \geq 1 and (x)_0 = 1. Specifically, x^n = \sum_{k=0}^n S(n,k) (x)_k. [7][7] For small values, the table of S(n,k) illustrates their growth:[6][8]| n \setminus k | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 1 | ||||
| 2 | 1 | 1 | |||
| 3 | 1 | 3 | 1 | ||
| 4 | 1 | 7 | 6 | 1 | |
| 5 | 1 | 15 | 25 | 10 | 1 |
Combinatorial Interpretations
Permutations and Cycles for the First Kind
The unsigned Stirling numbers of the first kind, denoted c(n,k), count the number of permutations of n elements with exactly k cycles, where fixed points are considered 1-cycles.[12] The signed Stirling numbers of the first kind, s(n,k), satisfy s(n,k) = (-1)^{n-k} c(n,k), providing a signed enumeration that aligns with the generating function for falling factorials and facilitates applications in algebraic combinatorics.[12] This signing convention ensures all permutations with the same number of cycles share the same sign, equal to the sign of the permutation itself, since the sign of a permutation is (-1)^{n-k}.[3] For n=4, there are 24 permutations in total. The breakdown by number of cycles is as follows: c(4,1) = 6 (all 4-cycles, such as (1\,2\,3\,4)); c(4,2) = 11 (eight permutations consisting of a 3-cycle and a fixed point, like (1\,2\,3)(4), and three consisting of two 2-cycles, like (1\,2)(3\,4)); c(4,3) = 6 (six permutations each with a 2-cycle and two fixed points, like (1\,2)(3)(4)); and c(4,4) = 1 (the identity permutation with four fixed points).[13] The corresponding signed values are s(4,1) = -6, s(4,2) = 11, s(4,3) = -6, and s(4,4) = 1.[14] These numbers appear in the cycle index of the symmetric group S_n, which encodes the enumeration of permutations by cycle type. The exponential generating function for the unsigned counts is \sum_{n=0}^\infty \left( \sum_{k=0}^n c(n,k) t^k \frac{x^n}{n!} \right) = \exp\left( t \log \frac{1}{1-x} \right), where the inner sum extracts the coefficient for fixed n and t.[15] The signed enumeration via s(n,k) supports applications such as counting signed permutations in the context of permutation signs and inclusion-exclusion principles. For derangements (permutations without fixed points), the numbers contribute through the cycle index by excluding 1-cycles, yielding the exponential generating function e^{-x}/(1-x) = \sum_{n=0}^\infty d(n) x^n / n!, where d(n) is the derangement count, derived from the full permutation generating function.[16]Set Partitions for the Bell Numbers and Second Kind
Stirling numbers of the second kind, denoted S(n,[k](/page/K)), count the number of ways to partition a set of n labeled elements into exactly [k](/page/K) nonempty unlabeled subsets.[6] Equivalently, S(n,[k](/page/K)) equals the number of surjective functions from a set of n elements to a set of [k](/page/K) elements, divided by [k](/page/K)!, since each partition corresponds to [k](/page/K)! ways to label the subsets.[6] For example, consider partitioning the set \{1,2,3,4\} into 2 nonempty subsets, where S(4,2) = 7. The distinct partitions are:\{1,2,3\} \mid \{4\},
\{1,2,4\} \mid \{3\},
\{1,3,4\} \mid \{2\},
\{2,3,4\} \mid \{1\},
\{1,2\} \mid \{3,4\},
\{1,3\} \mid \{2,4\},
\{1,4\} \mid \{2,3\}.[17] These illustrate how the subsets are unordered, so partitions differing only by subset relabeling are considered identical. The Bell number B_n, which enumerates the total number of partitions of an n-element set into any number of nonempty subsets, is given by B_n = \sum_{k=1}^n S(n,k).[18] For n=4, B_4 = S(4,1) + S(4,2) + S(4,3) + S(4,4) = 1 + 7 + 6 + 1 = 15.[6] Thus, the Stirling numbers of the second kind provide a refinement of the Bell numbers, distributing the total partition count across the possible numbers of subsets k.[18] An explicit formula for the Bell numbers, known as Dobiński's formula, is
B_n = \frac{1}{e} \sum_{k=0}^\infty \frac{k^n}{k!}.
This arises from the exponential generating function for Bell numbers and relates directly to the sum over Stirling numbers, as the formula counts weighted partitions via Poisson-distributed structures.[19] In combinatorics, Stirling numbers of the second kind are fundamental for enumerating set partitions and structures in combinatorial species, such as unlabeled collections of sets.[20] They also appear in statistics for computing raw moments of distributions like the Poisson, where E(X^n) = \sum_{i=1}^n S(n,i) \lambda^i, and in clustering analysis, where partitioning data points into groups mirrors set partition counts.[20]