Stirling Number Article Index for
Stirling 		Website Links For
Stirling 		 

Information About

Stirling Number
  CATEGORIES ABOUT STIRLING NUMBER
   
permutations
   
q-analogs
   
factorial and binomial topics
   
integer sequences
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




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).

:s(n,k)=\left n \ k \end{matrix} ight .

:S(n,k)= S_n^{(k)} =
\left\{\begin{matrix} n \ k \end{matrix} ight\}.

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.


STIRLING NUMBERS OF THE FIRST KIND

In Combinatorial Mathematics , unsigned Stirling numbers of the first kind

:s(n,k)\,

(with a lower-case "''s''") count the number of Permutation s of ''n'' elements with ''k'' disjoint Cycle s.

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)=\left n \ k \end{matrix} ight .

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.

Similar relationships involving the Stirling numbers hold for the Bernoulli Polynomials . Many relations for the Stirling numbers shadow similar relations on the Binomial Coefficient s. The study of these 'shadow relationships' is termed Umbral Calculus and culminates in the theory of Sheffer Sequences .


Table of values

Below is a table of values for the Stirling numbers of the first kind, similar in form to Pascal's Triangle :


Recurrence relation

The Stirling numbers of the first kind obey the Recurrence Relation

:\left n+1 \ k \end{matrix} ight =
\left n \ k-1 \end{matrix} ight
-n \left n \ k \end{matrix} ight


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

:\left n \ 0 \end{matrix} ight =0
\quad \mbox { and } \quad
\left 1 \ 1 \end{matrix} ight = 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 n \ 1 \end{matrix} ight =
(-1)^{n-1} (n-1)!

and

:\left n \ n \end{matrix} ight = 1

and

:\left n \ n-1 \end{matrix} ight = -
{n \choose 2}.

Other relations include

:\left n \ 2 \end{matrix} ight =
(-1)^n (n-1)!\; H_{n-1},

where H_n is a Harmonic Number , and

:\left n \ 3 \end{matrix} ight =
rac {1}{2} (-1)^{n-1} (n-1)! \left (H_{n-1})^2 - H_{n-1}^{(2)} ight

where H_n^{(m)} is a Generalized Harmonic Number . A generalization of this relation to harmonic numbers is given in a later section.


Generating function

A variety of identities may be derived by manipulating the Generating Function

:(1+t)^x = \sum_{n=0}^\infty {x \choose n} t^n =
\sum_{n=0}^\infty rac {t^n}{n!} \sum_{k=0}^n
\left n \ k \end{matrix} ight x^k =
\sum_{k=0}^\infty x^k
\sum_{n=k}^\infty rac {t^n}{n!}
\left n \ k \end{matrix} ight =
e^{x\ln(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 n \ k \end{matrix} ight =
(-1)^n n!.


Infinite sums

Some infinite sums include

:\sum_{n=m}^\infty
\left n \ k \end{matrix} ight
rac{x^n}{n!} = rac {\left(\ln (1+x) ight)^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 Number s as follows:

:s(n,k)=(-1)^{k-n} rac{\Gamma(n)}{\Gamma(k)}w(n,k-1)

where w(n,0)=1 and

:w(n,k)=\sum_{m=0}^{k-1} rac{\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 .


Enumerative interpretation


The Absolute Value of the Stirling number of the first kind, s(n,k), counts the number of Permutation s of n objects with exactly k Orbit s (equivalently, with exactly k Cycle s). For example, s(4,2)=11, corresponds to the fact that the Symmetric Group on 4 objects has 3 permutations of the form

: (\bullet\bullet)(\bullet\bullet) — 2 orbits of size 2 each

and 8 permutations of the form

: (\bullet\bullet\bullet) — 1 orbit of size 3, and 1 orbit of size 1

(see the entry on Cycle Notation for the meaning of the above expressions.)

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

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

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

is the ''n''th 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=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 Function s for ''rising'' factorials; see Pochhammer Symbol .)


Table of values

Below is a table of values for the Stirling numbers of the second kind:


Recurrence relation

Stirling numbers of the second kind obey the recurrence relation

:\left\{\begin{matrix} n \ k \end{matrix} ight\} =
\left\{\begin{matrix} n-1 \ k-1 \end{matrix} ight\}
+k \left\{\begin{matrix} n-1 \ k \end{matrix} ight\}


with

:\left\{\begin{matrix} n \ 1 \end{matrix} ight\}=1
\quad \mbox { and } \quad
\left\{\begin{matrix} n \ n \end{matrix} ight\} = 1.



Simple identities

Some simple identities include

:\left\{\begin{matrix} n \ n-1 \end{matrix} ight\} =
{n \choose 2}.

This is because dividing ''n'' elements into ''n'' − 1 sets necessarily means dividing it into one set of size 2 and ''n'' − 2 sets of size 1. Therefore we need only pick those two elements;

and

:\left\{\begin{matrix} n \ 2 \end{matrix} ight\} = 2^{n-1}-1.

To see this, first note that there are 2 ''n'' ''ordered'' pairs of complementary subsets ''A'' and ''B''. In one case, ''A'' is empty, and in another ''B'' is empty, so 2 ''n'' − 2 ordered pairs of subsets remain. Finally, since we want ''unordered'' pairs rather than ''ordered'' pairs we divide this last number by 2, giving the result above.


Explicit formula

The Stirling numbers of the second kind are given by the explicit formula

:\left\{\begin{matrix} n \ k \end{matrix} ight\}
= rac{1}{k!}\sum_{j=1}^{k}(-1)^{k-j}{k \choose j} j^n.

This formula is a special case of the ''k'' 'th Forward Difference of the Monomial x^n evaluated at ''x'' = 0:

: \Delta^k x^n = \sum_{j=1}^{k}(-1)^{k-j}{k \choose j} (x+j)^n.

Because the Bernoulli Polynomial s may be written in terms of these forward differences, one immediately obtains a relation in the Bernoulli Number s:

:B_m(0)=\sum_{k=0}^m rac {(-1)^k k!}{k+1}
\left\{\begin{matrix} m \ k \end{matrix} ight\}.


Moments of the Poisson distribution

If ''X'' is a Random Variable with a Poisson Distribution with Expected Value λ, then its ''n''th Moment is

:E(X^n)=\sum_{k=1}^n S(n,k)\lambda^k.

In particular, the ''n''th 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 ''n''th Bell number (this fact is "Dobinski's formula").


Moments of fixed points of random permutations

Let the random variable ''X'' be the number of fixed points of a Uniformly Distributed Random Permutation of a finite set of size ''m''. Then the ''n''th moment of ''X'' is

:E(X^n) = \sum_{k=1}^m S(n,k).

Note: The upper bound of summation is ''m'', not ''n''.

In other words, the ''n''th moment of this Probability Distribution is the number of partitions of a set of size ''n'' into no more than ''m'' parts.


INVERSION RELATIONSHIPS

The Stirling numbers of the first and second kind can be considered to be inverses of one-another:

:\sum_{n=0}^{\max\{j,k\}}
\left n \ j \end{matrix} ight
\left\{\begin{matrix} k \ n \end{matrix} ight\}
= \delta_{jk}


and

:\sum_{n=0}^{\max\{j,k\}}
\left\{\begin{matrix} n \ j \end{matrix} ight\}
\left k \ n \end{matrix} ight
= \delta_{jk}


where \delta_{jk} is the Kronecker Delta .


SEE ALSO



REFERENCES