NationMaster - Encyclopedia: Stirling number

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. Euclid, a famous Greek mathematician known as the father of geometry, is shown here in detail from The School of Athens by Raphael. ... Combinatorics is a branch of mathematics that studies collections (usually finite) of objects that satisfy specified criteria. ... James Stirling (April 22, 1692–December 5, 1770) was an important Scottish mathematician. ...

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). Abramowitz and Stegun is the informal moniker of a mathematical reference work edited by Milton Abramowitz and Irene Stegun of the U.S. National Bureau of Standards. ... Blackletter in a Latin Bible of AD 1407, on display in Malmesbury Abbey, Wiltshire, England. ...

$s(n,k)=left[begin{matrix} n k end{matrix}right].$

$S(n,k)= S_n^{(k)} = left{begin{matrix} n k end{matrix}right}.$

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. In mathematics, in particular in combinatorics, the binomial coefficient of the natural number n and the integer k is defined to be the natural number and (Here m! denotes the factorial of m). ... 1935 (MCMXXXV) was a common year starting on Tuesday (link will take you to calendar). ... Jovan Karamata at work Jovan Karamata (Serbian] Cyrillic: ÐˆÐ¾Ð²Ð°Ð½ ÐšÐ°Ñ€Ð°Ð¼Ð°Ñ‚Ð°) (1902-1967) was one of the greatest Serbian mathematicians of the 20th century. ... Donald Knuth at a reception for the Open Content Alliance. ...

Stirling numbers of the first kind

In combinatorial mathematics, unsigned Stirling numbers of the first kind Combinatorics is a branch of mathematics that studies collections (usually finite) of objects that satisfy specified criteria. ... Euclid, a famous Greek mathematician known as the father of geometry, is shown here in detail from The School of Athens by Raphael. ...

$s(n,k),$

(with a lower-case "s") count the number of permutations of n elements with k disjoint cycles. In mathematics, especially in abstract algebra and related areas, a permutation is a bijection from a finite set X onto itself. ... A cyclic permutation is a permutation that shifts all elements of given ordered set by a fixed offset, with the elements shifted off the end inserted back at the beginning in the same order, i. ...

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

$x^n=sum_{k=1}^n s(n,k)(x)^k$

where (x)ⁿ is the rising factorial In mathematics, the Pochhammer symbol, introduced by Leo August Pochhammer, is used in the theory of special functions to represent the rising factorial or upperfactorial and, confusingly, is used in combinatorics to represent the falling factorial or lower factorial To distinguish the two, the notations and are commonly used to...

$(x)^n=x(x+1)(x+2)cdots(x+n-1).$

Stirling numbers of the first kind are sometimes written with the alternate notation

$s(n,k)=left[begin{matrix} n k end{matrix}right].$

The definition can be inverted to express the falling factorial as a power series: In mathematics, the Pochhammer symbol, introduced by Leo August Pochhammer, is used in the theory of special functions to represent the rising factorial or upperfactorial and, confusingly, is used in combinatorics to represent the falling factorial or lower factorial To distinguish the two, the notations and are commonly used to...

$(x)_n = sum_{k=0}^n s(n,k) x^k.$

Similar relationships involving the Stirling numbers hold for the Bernoulli polynomials. Many relations for the Stirling numbers shadow similar relations on the binomial coefficients. The study of these 'shadow relationships' is termed umbral calculus and culminates in the theory of Sheffer sequences. In mathematics, the Bernoulli polynomials occur in the study of many special functions and in particular the Riemann zeta function and the Hurwitz zeta function. ... In mathematics, particularly in combinatorics, the binomial coefficient of the natural number n and the integer k is defined to be the natural number and (Here, for a natural number m, m! denotes the factorial of m. ... In mathematics, before the 1970s, the term umbral calculus was understood to mean the surprising similarities between otherwise unrelated polynomial equations, and certain shadowy techniques that can be used to prove them. ... In mathematics, a polynomial sequence, i. ...

Table of values

Below is a table of values for the Stirling numbers of the first kind, similar in form to Pascal's triangle: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 The first six rows of Pascals triangle In mathematics, Pascals triangle is a geometric arrangement of the binomial coefficients in a triangle. ...

n k	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	−1	1
3	0	2	−3	1
4	0	−6	11	−6	1
5	0	24	−50	35	−10	1
6	0	−120	274	−225	85	−15	1
7	0	720	−1764	1624	−735	175	−21	1
8	0	−5040	13068	−13132	6769	−1960	322	−28	1
9	0	40320	−109584	118124	−67284	22449	−4536	546	−36	1

Recurrence relation

The Stirling numbers of the first kind obey the recurrence relation In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ...

$left[begin{matrix} n+1 k end{matrix}right] = left[begin{matrix} n k-1 end{matrix}right] -n left[begin{matrix} n k end{matrix}right]$

for $1leq k leq n-1$ , with the initial conditions

$left[begin{matrix} n 0 end{matrix}right]=0 quad mbox { and } quad left[begin{matrix} 1 1 end{matrix}right] = 1.$

The above follows from the recurrence relation on the falling factorials:

(x) n + 1 = x (x) n - n (x) n .

Simple identities

Note that

$left[begin{matrix} n 1 end{matrix}right] = (-1)^{n-1} (n-1)!$

and

$left[begin{matrix} n n end{matrix}right] = 1$

and

$left[begin{matrix} n n-1 end{matrix}right] = - {n choose 2}.$

Other relations include

$left[begin{matrix} n 2 end{matrix}right] = (-1)^n (n-1)!; H_{n-1},$

where $H n$ is a harmonic number, and In mathematics, the generalized harmonic number of order is given by The special case of is simply called a harmonic number and is frequently written without the superscript, as In the limit of , the generalized harmonic number converges to the Riemann zeta function The related sum occurs in the study...

$left[begin{matrix} n 3 end{matrix}right] = frac {1}{2} (-1)^{n-1} (n-1)! left[ (H_{n-1})^2 - H_{n-1}^{(2)} right]$

where $H_n^{(m)}$ is a generalized harmonic number. A generalization of this relation to harmonic numbers is given in a later section. In mathematics, the generalized harmonic number of order is given by The special case of is simply called a harmonic number and is frequently written without the superscript, as In the limit of , the generalized harmonic number converges to the Riemann zeta function The related sum occurs in the study...

Explicit formula

The Stirling numbers of the first kind are given by the explicit formula:

s(n,k) = (-1)^(n-k) × ( n!/{(k-1)!×2^(n-k)} ) × [ Sum_{i=1..n-k} (-1)^(i-1) × { ( 1/{6^(i-1)×(i-1)!×(n-k-2×i+2)!} ) - ( {(i-3)}/{5×6^(i-2)×(i-3)!×(n-k-2×i+4)!} ) + ( {(i-5)×(21×i-46)}/{1050×6^(i-3)×(i-5)!×(n-k-2×i+6)!} ) - ( {(i-7)×(i-4)×(7×i-11)}/{5250×6^(i-4)×(i-7)!×(n-k-2×i+8)!} ) + ( {(i-9)×6×(5040+2959×C(i-10,1)+...)}/{1819125×6^(i-5)×(i-9)!×(n-k-2×i+10)!} ) - ..... }×n^(n-k-i) ].

Generating function

A variety of identities may be derived by manipulating the generating function In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ...

$(1+t)^x = sum_{n=0}^infty {x choose n} t^n = sum_{n=0}^infty frac {t^n}{n!} sum_{k=0}^n left[begin{matrix} n k end{matrix}right] x^k = sum_{k=0}^infty x^k sum_{n=k}^infty frac {t^n}{n!} left[begin{matrix} n k end{matrix}right] = e^{xln(1+t)}.$

In particular, the order of summation may be exchanged, and derivatives taken, and then t or x may be fixed.

Finite sums

A simple sum is

$sum_{k=0}^n (-1)^k left[begin{matrix} n k end{matrix}right] = (-1)^n n!.$

Infinite sums

Some infinite sums include

$sum_{n=m}^infty left[begin{matrix} n k end{matrix}right] frac{x^n}{n!} = frac {left(ln (1+x)right)^m}{k!}$

which holds for $x < 1$ .

Relation to harmonic numbers

Stirling numbers of the first kind can be expressed in terms of the harmonic numbers as follows: In mathematics, the generalized harmonic number of order is given by The special case of is simply called a harmonic number and is frequently written without the superscript, as In the limit of , the generalized harmonic number converges to the Riemann zeta function The related sum occurs in the study...

$s(n,k)=(-1)^{k-n} frac{Gamma(n)}{Gamma(k)}w(n,k-1)$

where $w (n,0) = 1$ and

$w(n,k)=sum_{m=0}^{k-1}frac{Gamma(1-k+m)}{Gamma(1-k)}H_{n-1}^{(m+1)} w(n,k-1-m).$

In the above, $Γ(x)$ is the Gamma function and $H^{(m)}_n$ is the harmonic number. The Gamma function along part of the real axis In mathematics, the Gamma function extends the factorial function to complex and non integer numbers (it is already defined on the naturals, and has simple poles at the negative integers). ... In mathematics, the generalized harmonic number of order is given by The special case of is simply called a harmonic number and is frequently written without the superscript, as In the limit of , the generalized harmonic number converges to the Riemann zeta function The related sum occurs in the study...

Enumerative interpretation

The absolute value of the Stirling number of the first kind, $s (n, k)$ , counts the number of permutations of $n$ objects with exactly $k$ orbits (equivalently, with exactly $k$ cycles). For example, $s (4,2) = 11$ , corresponds to the fact that the symmetric group on 4 objects has $3$ permutations of the form In mathematics, the absolute value (or modulus1) of a real number is its numerical value without regard to its sign. ... In mathematics, especially in abstract algebra and related areas, a permutation is a bijection from a finite set X onto itself. ... In physics, an orbit is the path that an object makes, around another object, whilst under the influence of a source of centripetal force, such as gravity. ... A cycle (Latin cyclus, from Greek kuklos meaning circle) is anything round, in the physical sense (e. ... In mathematics, the symmetric group on a set X, denoted by SX or Sym(X), is the group whose underlying set is the set of all bijective functions from X to X, in which the group operation is that of composition of functions, i. ...

$(bulletbullet)(bulletbullet)$ — 2 orbits of size 2 each

and $8$ permutations of the form

$(bulletbulletbullet)$ — 1 orbit of size 3, and 1 orbit of size 1

(see the entry on cycle notation for the meaning of the above expressions.) The cycle notation is a useful convention for writing down a permutation in terms of its constituent cycles. ...

Let us prove this. First, we can remark that the unsigned Stirling numbers of the first are characterized by the following recurrence relation:

$| s(n+1,k)| = | s(n,k-1)| + n| s(n,k)|,qquad 1leq k < n.$

To see why the above recurrence relation matches the count of permutations with $k$ cycles, consider forming a permutation of $n + 1$ objects from a permutation of $n$ objects by adding a distinguished object. There are exactly two ways in which this can be accomplished. We could do this by forming a singleton cycle, i.e. leaving the extra object alone. This accounts for the $s (n, k - 1)$ term in the recurrence formula. We could also insert the new object into one of the existing cycles. Consider an arbitrary permutation of $n$ object with $k$ cycles, and label the objects $a_1,ldots,a_n$ , so that the permutation is represented by Generally, a singleton is something which exists alone in some way. ...

$underbrace{(a_1 ldots a_{j_1})(a_{j_1+1} ldots a_{j_2})ldots(a_{j_{k-1}+1} ldots a_n)}_{ k mbox{ cycles}}.$

To form a new permutation of $n + 1$ objects and $k$ cycles one must insert the new object into this array. There are, evidently $n$ ways to perform this insertion. This explains the $n,s(n,k)$ term of the recurrence relation. Q.E.D.

Stirling numbers of the second kind

Stirling numbers of the second kind S(n,k) (with a capital "S") count the number of equivalence relations having k equivalence classes defined on a set with n elements. The sum In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ... In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x âˆˆ X | x ~ a } The notion of equivalence classes is useful for constructing sets out...

$B_n=sum_{k=1}^n S(n,k)$

is the nth Bell number. If we let The Bell numbers, named in honor of Eric Temple Bell, are a sequence of integers arising in combinatorics that begins thus (sequence A000110 in OEIS): In general, Bn is the number of partitions of a set of size n. ...

$(x)_n=x(x-1)(x-2)cdots(x-n+1)$

(in particular, (x)₀ = 1 because it is an empty product) be the falling factorial, we can characterize the Stirling numbers of the second kind by In mathematics, an empty product, or nullary product, is the result of multiplying no numbers. ... In mathematics, the Pochhammer symbol is used in the theory of special functions to represent the rising factorial or upper factorial and, confusingly, is used in combinatorics to represent the falling factorial or lower factorial The empty product (x)0 is defined to be 1 in both cases. ...

$sum_{k=0}^n S(n,k)(x)_k=x^n.$

(Confusingly, the notation that combinatorialists use for falling factorials coincides with the notation used in special functions for rising factorials; see Pochhammer symbol.) In mathematics, several functions are important enough to deserve their own name. ... In mathematics, the Pochhammer symbol, introduced by Leo August Pochhammer, is used in the theory of special functions to represent the rising factorial or upperfactorial and, confusingly, is used in combinatorics to represent the falling factorial or lower factorial To distinguish the two, the notations and are commonly used to...