Stirling number

From Wikipedia for FEVERv2
Jump to navigation Jump to search

In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. Stirling number_sentence_0

They are named after James Stirling, who introduced them in the 18th century. Stirling number_sentence_1

Two different sets of numbers bear this name: the Stirling numbers of the first kind and the Stirling numbers of the second kind. Stirling number_sentence_2

Additionally, Lah numbers are sometimes referred to as Stirling numbers of the third kind. Stirling number_sentence_3

Each kind is detailed in its respective article, this one serving as a description of relations between them. Stirling number_sentence_4

A common property of all three kinds is that they describe coefficients relating three different sequences of polynomials that frequently arise in combinatorics. Stirling number_sentence_5

Moreover, all three can be defined as the number of partitions of n elements into k non-empty subsets, with different ways of counting orderings within each subset. Stirling number_sentence_6

Notation Stirling number_section_0

Main article: Stirling numbers of the first kind Stirling number_sentence_7

Main article: Stirling numbers of the second kind Stirling number_sentence_8

Several different notations for Stirling numbers are in use. Stirling number_sentence_9

Common notations are: Stirling number_sentence_10

for unsigned Stirling numbers of the first kind, which count the number of permutations of n elements with k disjoint cycles, Stirling number_sentence_11

for ordinary (signed) Stirling numbers of the first kind, and Stirling number_sentence_12

for Stirling numbers of the second kind, which count the number of ways to partition a set of n elements into k nonempty subsets. Stirling number_sentence_13

Abramowitz and Stegun use an uppercase S and a blackletter S, respectively, for the first and second kinds of Stirling number. Stirling number_sentence_14

The notation of brackets and braces, in analogy to binomial coefficients, was introduced in 1935 by Jovan Karamata and promoted later by Donald Knuth. Stirling number_sentence_15

(The bracket notation conflicts with a common notation for Gaussian coefficients.) Stirling number_sentence_16

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 number_sentence_17

Expansions of falling and rising factorials Stirling number_section_1

Stirling numbers express coefficients in expansions of falling and rising factorials (also known as the Pochhammer symbol) as polynomials. Stirling number_sentence_18

with (signed) Stirling numbers of the first kind as coefficients. Stirling number_sentence_19

Stirling numbers of the second kind express reverse relations: Stirling number_sentence_20

and Stirling number_sentence_21

As change of basis coefficients Stirling number_section_2

Considering the set of polynomials in the (indeterminate) variable x as a vector space, each of the three sequences Stirling number_sentence_22

Stirling number_description_list_0

As inverse matrices Stirling number_section_3

The Stirling numbers of the first and second kinds can be considered inverses of one another: Stirling number_sentence_23

and Stirling number_sentence_24

Although s and S are infinite, so calculating a product entry involves an infinite sum, the matrix multiplications work because these matrices are lower triangular, so only a finite number of terms in the sum are nonzero. Stirling number_sentence_25

Example Stirling number_section_4

Expressing a polynomial in the basis of falling factorials is useful for calculating sums of the polynomial evaluated at consecutive integers. Stirling number_sentence_26

Indeed, the sum of a falling factorial is simply expressed as another falling factorial (for k≠-1) Stirling number_sentence_27

For example, the sum of fourth powers of integers up to n (this time with n included), is: Stirling number_sentence_28

Here the Stirling numbers can be computed from their definition as the number of partitions of 4 elements into k non-empty unlabeled subsets. Stirling number_sentence_29

Lah numbers Stirling number_section_5

Main article: Lah numbers Stirling number_sentence_30

These numbers are coefficients expressing falling factorials in terms of rising factorials and vice versa: Stirling number_sentence_31

Symmetric formulae Stirling number_section_6

Abramowitz and Stegun give the following symmetric formulae that relate the Stirling numbers of the first and second kind. Stirling number_sentence_32

and Stirling number_sentence_33

Stirling numbers with negative integral values Stirling number_section_7

The Stirling numbers can be extended to negative integral values, but not all authors do so in the same way. Stirling number_sentence_34

Regardless of the approach taken, it is worth noting that Stirling numbers of first and second kind are connected by the relations: Stirling number_sentence_35

Stirling number_table_general_0

knStirling number_cell_0_0_0 −1Stirling number_header_cell_0_0_1 −2Stirling number_header_cell_0_0_2 −3Stirling number_header_cell_0_0_3 −4Stirling number_header_cell_0_0_4 −5Stirling number_header_cell_0_0_5
−1Stirling number_header_cell_0_1_0 1Stirling number_cell_0_1_1 1Stirling number_cell_0_1_2 1Stirling number_cell_0_1_3 1Stirling number_cell_0_1_4 1Stirling number_cell_0_1_5
−2Stirling number_header_cell_0_2_0 0Stirling number_cell_0_2_1 1Stirling number_cell_0_2_2 3Stirling number_cell_0_2_3 7Stirling number_cell_0_2_4 15Stirling number_cell_0_2_5
−3Stirling number_header_cell_0_3_0 0Stirling number_cell_0_3_1 0Stirling number_cell_0_3_2 1Stirling number_cell_0_3_3 6Stirling number_cell_0_3_4 25Stirling number_cell_0_3_5
−4Stirling number_header_cell_0_4_0 0Stirling number_cell_0_4_1 0Stirling number_cell_0_4_2 0Stirling number_cell_0_4_3 1Stirling number_cell_0_4_4 10Stirling number_cell_0_4_5
−5Stirling number_header_cell_0_5_0 0Stirling number_cell_0_5_1 0Stirling number_cell_0_5_2 0Stirling number_cell_0_5_3 0Stirling number_cell_0_5_4 1Stirling number_cell_0_5_5

See also Stirling number_section_8

Stirling number_unordered_list_1


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Stirling number.