Stirling Number

Stirling numbers of the first kind

In combinatorics, unsigned Stirling numbers of the first kind
s(n,k)\,
(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
x^n=\sum_{k=1}^n s(n,k)(x)^k
where (x)n is the rising factorial
(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)=\leftn \\ k \end{matrix}\right.
The definition can be inverted to express the falling factorial as a power series:
(x)_n = \sum_{k=0}^n s(n,k) x^k
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. Stirling numbers of the first kind can be expressed in terms of the harmonic numbers as follows:
s(n,k)=(-)^{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, \Gamma(x) is the Gamma function and H^{(m)}_n is the harmonic number.

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
B_n=\sum_{k=1}^n S(n,k)
is the nth Bell number. If we let
(x)_n=x(x-1)(x-2)\cdots(x-n+1)
(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
\sum_{k=1}^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.) The Stirling numbers of the second kind enjoy the following relationship with the Poisson distribution: if X is a random variable with a Poisson distribution with expected value λ, then its nth moment is
E(X^n)=\sum_{k=1}^n S(n,k)\lambda^k.
In particular, the nth moment of the Poisson distribution with expected value 1 is precisely the number of partitions of a set of size n, i.e., it is the nth Bell number (this fact is "Dobinski's formula").

Karamata notation

In recent years, the Stirling numbers have often been denoted in a way introduced in 1935 by Jovan Karamata and promoted later by Donald Knuth:
s(n,k)=\leftn \\ k \end{matrix}\right.
S(n,k)=\left\{\begin{matrix} n \\ k \end{matrix}\right\}.

See also

Lah number

External references

 

<< PreviousWord BrowserNext >>
golden valley county, montana
glacier county, montana
garfield county, montana
gallatin county, montana
flathead county, montana
fergus county, montana
fallon county, montana
deer lodge county, montana
dawson county, montana
daniels county, montana
custer county, montana
chouteau county, montana
cascade county, montana
carter county, montana
carbon county, montana
broadwater county, montana
blaine county, montana
big horn county, montana
beaverhead county, montana
papa
raki
rangi
tane
rehua
kaitangata
centrosome
tangaroa
nicephorus callistus xanthopoulos
buda
tawhiri
tu
upton sinclair
grammatical particle
ku
tu matauenga
york county, maine
washington county, maine
waldo county, maine
somerset county, maine
sagadahoc county, maine
piscataquis county, maine
james stirling (mathematician)
penobscot county, maine
oxford county, maine