nav.gif (1245 bytes) mathematics

Ken Ward's Mathematics Pages

Series

Stirling Numbers of the Second Kind and Factorial Polynomials

Series Contents

Page Contents

  1. There is only one representation of a polynomial in factorials
  2. Stirling Numbers of the Second Kind
  3. Any Polynomial of degree n (an integer) can be Represented as a Factorial Polynomial
  4. Example
  5. Alternative Definition

There is only one representation of a polynomial in factorials

Proof

Suppose we have a polynomial in k of degree n, and we can represent it in two different factorials:
1
where a0 and a1 are different. Both factorials are of the same degree, n, as the function. If both equations are true, then both of the factorial representations agree with all values of f(n), say an infinite number because k can be any integer, which is more than n. However, two different polynomials of degree n can agree on at most n values of f(n) (Polynomial argument). So the two factorial representations of f(n) are the same polynomial.  Consequently, there is only one representation of a polynomial  in factorials. (So, a0=a1, etc)

Stirling Numbers of the Second Kind

Stirling Numbers are named after the Scottish mathematician James Stirling (1692-1770)
From a previous page, we showed that some polynomials could be represented as factorials:
k=k(1) [1.01]
k2=k(1)+k(2) [1.02]
k3=k(1)+3k(2)+k(3) [1.03]
We write k on the left hand side rather than x, because conventionally, x, y, z represent real or complex numbers and k, l, m represent integers and we are considering integers here (although factorial polynomials are not limited to integers). (This is just a preference for this page.)

We can rewrite the above equations as:
k=S(1,1)k(1) [1.04]
k2=S(2,1)k(1)+S(2,2)k(2) [1.05]
k3=S(3,1)k(1)+S(3,2)k(2)+S(3,3)k(3) [1.06]
Where S(2,1) means the item number 1 in the row n=2
These numbers are called Stirling Numbers of the Second Kind, and are sometimes written:
2
where i is the i in the k(i) term of the expansion in factorials of kn
A capital S is preferred as the lowercase s is sometimes used with Stirling Numbers of the First Kind, but this is often reversed by some authors, using a lowercase s for Stirling Numbers of the Second Kind, and a capital for those of the First. Indeed, factorials are also written variously. Therefore we need to say what we are using our symbols for. On these pages, a capital S refers to Stirling Numbers of the Second Kind.  

The following can be proved by expanding the terms, and these form the small values for the induction in the next section.
The Stirling number for k is simply 1, because k=k(1) (Coefficient 1)
The Stirling Numbers for k2 are 1, 1, because k2=k(1)+k(2)
And those for k3 are 1, 3, 1, because k3=k(1)+3k(2)+k(3).
We can define k(0) as 1. If we included this terms in the above, we would find that S(1,0)=0, as are all the others, except S(0,0) which is 1. For all the powers of k above 0, there is no constant term. However
3=S(0,0)3k0
So, S(0,0) is clearly 1.

Any Polynomial of degree n (an integer) can be Represented as a Factorial Polynomial

We claim that any polynomial can be represented in the form:
 3[1.07]
We know that some polynomials can be so represented, for instance, when n=1, 2 and 3. See previous page.

We wish to show, by induction, that 1.07 becomes 1.07a, when we substitute n+1 for n:
3a[1.07a]


Proceding by induction, we multiply 1.07 by k, so:
 [1.08]
We need to know how to determine k·k(i) So we recall:

From the above, we note that
 [1.09]

By rearranging we obtain an expression for k·k(i):
5 [1.10]



Evaluating the k·k(i) terms in 1.08 with 1.10, we have:
9 [1.13]

Therefore, 1.13 is true, if 1.07 is true because we can express the factorial in terms of some constants. By comparing the coefficients in 1.13 and 1.07a , we find:
 11 [1.15]
We can further say, that if 1.15 is true, then 1.13 and 1.07a have the same constants.

Using 1.15 we can fill in the table below for Stirling Numbers of the Second Kind.

Stirling Numbers of the Second Kind
i
k(0) k(1) k(2) k(3) k(4) k(5) k(6) k(7)
n 0 1 2 3 4 5 6 7
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1

Example

We can use the table to transform polynomials to factorials.

For instance,
Represent 2k2+3k+7 in factorials:
For convenience, we turn the equation round:
7+3k+2k2 [1.16]
The first factorial (for 7) is:
7f0
The second, for k, f1, is:
(3x1)f1
And the last for k2 is:
(2x1)f1+(2x1)f2
Therefore, collecting f's of the same degree:
7f0+ 5f1+2f2
We can check this by expanding the factorials
=7+5k+2k2-2k
=7+3k+2k2 which is 1.16
Alternatively, we can make a table and multiply the Stirling Numbers in their columns by the coefficients of k in the original equation, as below:

  k(0) k(1) k(2)
7 7*1=7 [S(0,0)*7 ]    
3k   3*1=3 [S(1,1)*3 ]  
2k2   2*1=42 [S(1,1)*2] 2*1=2 [S(2,1)*2]
Sum 7 2

We add up the columns for each term in the original equation and the result is:
7+3k+2k2

We can verify the result we obtained on a previous page by Synthetic Division:
x5+2x4+3x3+7x2+5x+19≡k(5)+12k(4)+40k(3)+45k(2)+18k(1)+19k

By multiply the appropriate lines in the table of Stirling Numbers, as shown in the table below, and adding the columns, we can verify our previous answer.

  k(0) k(1) k(2) k(3) k(4) k(5)
n   0 1 2 3 4 5
0 19          
1 0 5        
2 0 7 7      
3 0 3 9 3    
4 0 2 14 12 2  
5 0 1 15 25 10 1
Sum of Columns: 19 18 45 40 12 1

Alternative Definition

Stirling Numbers of the Second Kind can be defined as:
S(n,i) ways of partitioning a set of n elements in i non-empty subsets.

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