Stirling number
The Stirling numbers of the first and second type, named after James Stirling, are used in combinatorics and theoretical computer science.
- 3.1 Example
- 3.2 Features
Designation and Notation
With regard to a pre- 1730 published work Stirlings in which these figures are examined, led Niels Nielsen in 1906 in the manual of the theory of the gamma function, the term " Stirling numbers of the first and second kind" a ( " nombres de Stirling " already in a 1904 article published ).
Neither the designation as Stirling numbers still uniform notations have prevailed. In this article, Stirling numbers of the first kind are denoted by small or one above the other in square brackets, Stirling numbers of the second kind denoted with large or stacked written in braces:
The bracket notation, also called Karamata notation, was introduced in 1935 by Jovan Karamata in analogy with the binomial coefficients, 1992, Donald Knuth began with a detailed excursus on the Stirling numbers for this notation.
Stirling numbers of the first kind
The Stirling numbers of the first kind is the number of permutations of a - element set that have exactly Cycles. Another definition is frequently used instead called Stirling numbers of the first kind.
Example
The amount of elements can be divided in the following ways on Cycles:
So is. For more examples, see Zykeltyp.
Properties
Apply the explicit formulas
And the recursive formula
With the initial conditions
Other special values are
- Sequence A000254 in OEIS
- Sequence A000399 in OEIS
- Sequence A001303 in OEIS
- Sequence A000914 in OEIS
For all the - th harmonic number and a generalized harmonic number.
Generally can be regarded as a polynomial in the degree. It has the leading coefficient, and contains all the factors of n, n- 1, ..., n- k, and for odd factors and n2 (n-1 ) 2 The polynomial
In the degree is referred to as Stirling polynomial, see also Stirling polynomials.
Generating functions are
With the rising factorial
Is a prime number, then for divisible by and for straight divisible by ( Nielsen 1893). The set of Wolstenholme is the special case
Since the number of all permutations is one - element set, it follows
And in particular, directly from the definition of
For each there exists a such that
And or ( Erdős 1953).
The result is strictly logarithmically concave for each, that is, for
Is the asymptotic behavior of assuming
With the Euler - Mascheroni constant
Stirling numbers of the second kind
The Stirling number of the second kind is the number of partitions of a -element - element set, ie the number of ways to split a - element set into nonempty disjoint subsets.
Is also the number of ways to divide distinguishable balls on not distinguishable compartments, so that at least one ball is in each subject. Are the subjects distinguishable, one obtains ways, this is also the number of surjective maps of a - element set to an - element set.
Example
The amount of items can be decomposed in the following ways into non-empty disjoint subsets:
So is.
Properties
Apply the explicit formulas
With integer non-negative and the recursive formula
With the initial conditions
Other special values are
- Sequence A000392 in OEIS
- Sequence A001297 in OEIS
- Sequence A001296 in OEIS
For all
Also can be regarded as a polynomial in the degree. It has the leading coefficient, and contains all the factors of n, n- 1, ..., n- k, and for odd factors (n- k) and 2 (n- k 1 ) 2 The same Stirling polynomial of degree obtained as the Stirling numbers of the first kind by
Generating functions are
With the falling factorial
Is a prime number, then for divisible by.
As the Bell's number is the number of all partitions of a - element set, applies
The? N Bernoulli number is obtained as the alternating sum
By means of the recursion formula it can be shown that there is for each one, so that
And or true. It is an open question whether there is, for the case occurs.
The result is strictly logarithmically concave for each, that is, for
Relationship between the Stirling numbers of the first and second type
From the relations
Which are also often used to define the Stirling numbers of the second and first type, it follows that these are the coefficients of the inverse linear transformation to each other, the Stirling transformation and the inverse transformation Stirling. That is, the lower triangular matrix and inverse to each other are:
With the Kronecker delta for and for
The Stirling numbers of the first and second kind can be represented ( Schlomilch 1852) respectively by the other:
The Stirling numbers can be uniquely continued to negative integer indices and that the recurrence formulas
Generally apply for and obtained the whole for all numbers and valid duality
Also, the two Recursive converted into one another, and also for Putting the polynomials in conceived Sn, n-k, and Sn, n- k is a negative integer, the result is the same Continued negative integer indexes, and the polynomials duality
Analogy with the binomial coefficients
For the binomial coefficients
The Karamata notation emphasizes the analogy:
Accordingly, the Stirling numbers in a triangle pattern can similarly arrange the Pascal's triangle.
Triangle of Stirling numbers of the first kind ( first row first column sequence A130534 in OEIS ):
1 1 1 1 2 3 6 11 6 1 24 50 35 10 1 120 274 225 85 15 1 720 1764 1624 735 175 21 1 5040 13068 13132 6769 1960 322 28 1 40320 109584 118124 67284 22449 4536 546 36 1 ........................... 1 Triangle of Stirling numbers of the second kind ( first row first column sequence A008277 in OEIS ):
1 1 1 1 3 1 1 7 6 1 1 15 25 10 1 1 31 90 65 15 1 1 63 301 350 140 21 1 1 127 966 1701 1050 266 28 1 1 255 3025 7770 6951 2646 462 36 1 1 ........................ 1 As another analogy, there are injective and surjective functions with -element definition and target -element set.
Stirling polynomials
Launched in section Stirling numbers of the first kind Stirling polynomials by the generating functions
Described, the one generating by generalization capabilities of and receives. According to another definition, the polynomials and called the Stirling polynomials. Ψ0 polynomials (x ) ψ1 (x ), ..., ψ6 (X)
And special values are
With the Bernoulli number? k 1. Can be calculated with the formulas the polynomials
With by for j ∉ {0, 1, ..., k-1 }, and
And by C1, 0 = 1, ck, j = 0 for j ∉ {0, 1, ..., k- 1} and
Recursively defined integer coefficients. For one obtains
This calculation of and is particularly efficient for large and small.