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(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: [1.02]
We note: [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): [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(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'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: