Ken Ward's Mathematics Pages

Stirling Numbers of the First Kind

Page Contents

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⁷

n\ ⁱ	0	1	2	3	4	5	6	7	8	9	10	11
	Stirling Numbers of the First Kind
	k⁰	k¹	k²	k³	k⁴	k⁵	k⁶	k⁷	k⁸	k⁹	k¹⁰	k¹¹
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

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