nav.gif (1245 bytes) mathematics

Ken Ward's Mathematics Pages

Stirling Numbers of the First Kind

Series Contents

Page Contents

  1. Stirling Numbers of the First Kind
    1. Proof
  2. Table of Stirling Numbers of the First Kind
    1. Value of the First Term
      1. Proof
  3. Alternative Definitions

Stirling Numbers of the First Kind

We claim that factorial polynomials can be written as regular polynomials:
1 [1.01]
Where the s's are constants (Stirling Numbers of the First Kind)
We note that
k(0)=1, so s(0,0)=1
k(1)=x, so s(1,1)=1. s(1,0)=0 because there are no constants
k(2)=x(x-1)=x2-x, so s(2,2)=1, s(2,1)=-1 and s(2,0)=0
Because for all n>0, the factorial contains a factor, k, then all the powers will be 1 or above: there will be no constants. So s(n,0)=0 for all n>0. (s(0,0)=1, as shown above).

Proof

We use induction. We know the first few factorials can be expressed as polynomials.

We assume that if 1.01 is true, then so is:
2 [1.02]

We note:
3 [1.03]
because  k(n+1) is the k(n) with the additional factor (k-n), by definition.
k(n) =k(k-1)...(k-n+1)
k(n+1) =k(k-1)...(k-n+1)·(k-n)

Multiplying 1.01 by (k-n) gives us, noting for the left-hand-side, k(n)(k-n)=k(n+1):
4 [1.04]

Collecting together like powers, we have:
5[1.05]
By comparing the coefficients of 1.05 and 1.02, we find:
6 [1.06]

It is true, that if 1.01 is true then so is 1.02, provided we relate the Stirling numbers according to 1.06.

As we have shown that for n=1, the claim is true, it is also true for n=2, n=3 and n=n, so we have completed the induction.

Using the formula from this page, we note (for comparison) that Stirling Numbers of the Second Kind are related by:
11
That is, Stirling Numbers of the Second Kind do not have the minus sign and the multiplier is i, not n.

Table of Stirling Numbers of the First Kind

We can fill in the column, 0, making s(0,0) =1 and the rest 0, as we have shown above. We can then proceed using the formula, 1.06, above and fill in the rest of the values. The blanks are zero. (For the table, I used a spreadsheet)
We can quickly build up such a table for small values, and the table saves us a lot of work, especially as n increases. For instance, we can write down the expansion of k(7) simply by reading the table:
k(7)=720k-1764k2+1624k3-735k4+175k5-21k6+k7

Stirling Numbers of the First Kind
k0 k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 k11
n\ i 0 1 2 3 4 5 6 7 8 9 10 11
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 -1,764 1,624 -735 175 -21 1
8 0 -5,040 13,068 -13,132 6,769 -1,960 322 -28 1
9 0 40,320 -109,584 118,124 -67,284 22,449 -4,536 546 -36 1
10 0 -362,880 1,026,576 -1,172,700 723,680 -269,325 63,273 -9,450 870 -45 1
11 0 3,628,800 -10,628,640 12,753,576 -8,409,500 3,416,930 -902,055 157,773 -18,150 1,320 -55 1

Value of the First Term

We can note that s(n,1)=(-1)n-1(n-1)! [1.07]
Remembering that s(n,0)=1, for n>0, and using formula 1.06, with i=1:
s(n+1,1)=(-n)s(n,1) [1.08]
s(1,1)=1
s(2,1)=(-1)1
s(3,1)=(-2)(-1)1
s(4,1)=(-3)(-1)1

Proof

We can prove by induction that:
s(n,1)=(-1)n-1(n-1)!, for integer n>0 [1.09]

We assume that if s(n,1)=(-1)n-1(n-1)! [1.09 repeated]
Then it is true that s(n+1,1)=(-1)n(n)! [1.10]

Multiply 1.07 by (-n)
s(n,1)·(-n)=(-1)n-1(n-1)!·(-n)[1.11]

According to 1.08:
s(n+1,1)=(-n)s(n,1)
So, 1.11 can be written
s(n+1,1)=(-1)n-1(n-1)!(-n) [1.12]
Because the minus in (-n) combines with the other minuses to give (-1)n-1(-1)=(-1)n
And the n combines with the (n-1)! in  in 1.12 to give n!, we have:
s(n+1,1)=(-1)n(n)!
Which is 1.10. So, if 1.09 is true, so is 1.10
We know it is true for n=1, 2, 3, and 4, so it is true for n=5. And so it is true for all n
Hence:
s(n,1)=(-1)n-1(n-1)! [1.07, repeated]

Alternative Definitions

Stirling Numbers of the First Kind can be defined as
s(n,i) ways of partitioning a set of n elements into i cycles.

The numbers in the table above are signed, because they are related to expanding factorial functions. Other forms are unsigned (but have the same absolute values). For the unsigned form, the relationship is:
s(n+1,i)=s(n,i-1)+ns(n,i)








Ken Ward's Mathematics Pages


Faster Arithmetic - by Ken Ward

Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle:
Buy now at Amazon.com
Faster Arithmetic for Adults