Ken Ward's Mathematics Pages

Stirling Numbers of the First Kind

Series Contents

Page Contents

0. Stirling Numbers of the First Kind
   0. Proof
0. Table of Stirling Numbers of the First Kind
   0. Value of the First Term
      0. Proof
0. Alternative Definitions

Stirling Numbers of the First Kind

We claim that factorial polynomials can be written as regular polynomials:
[1.01]
Where the s's are constants (Stirling Numbers of the First Kind)
We note that
k⁽⁰⁾=1, so s(0,0)=1
k⁽¹⁾=x, so s(1,1)=1. s(1,0)=0 because there are no constants
k⁽²⁾=x(x-1)=x²-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:
[1.02]

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

Multiplying 1.01 by (k-n) gives us, noting for the left-hand-side, k⁽ⁿ⁾(k-n)=k⁽ⁿ⁺¹⁾:
[1.04]

Collecting together like powers, we have:
[1.05]
By comparing the coefficients of 1.05 and 1.02, we find:
[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:

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⁽⁷⁾ simply by reading the table:
k⁽⁷⁾=720k-1764k²+1624k³-735k⁴+175k⁵-21k⁶+k⁷

	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)! [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)ⁿ
And the n combines with the (n-1)! in  in 1.12 to give n!, we have:
s(n+1,1)=(-1)ⁿ(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