# Stirling Numbers of the Second Kind

I am trying to understand the derivation of the Stirling Numbers from a difference table.

From my book:

Let $h_n = n^p$. The $0$-th diagonal of the difference table for $h_n$ has the form $c(p,0), c(p,1), c(p,2),\dots,c(p,p),0,0,\dots\;\;$.

This is where I am confused: what is $c(p,p)$? I at first thought they were the binomial coefficients, but upon computing the difference table for $h_n = n^4$:

$$\begin{array}{rrrrrrrrr} 0, & & 1, & & 16, & & 81, & & 256 \\ & 1, & & 15, & & 65, & & 175 \\ & & 14, & & 50, & & 110 \\ & & & 36, & & 60 \\ & & & & 24 \end{array}$$

The $0$-th diagonal is clearly: $0, 1, 14, 36$, but $0 \ne \binom40$, $1 \ne\binom41$, etc.

In the end the Stirling Numbers of the Second Kind are derived to be: $S(p,k) = c(p,k)/k!$

The book Introductory Combinatorics by Brualdi (5th edition) can be found online here: filetosi.files.wordpress.com/2010/12/combiatoric.pdf. My questions about c(p,k) begin at pg. 281, halfway through the page.

-
As you can see from Grigory's answer, adding as much context as possible is good both for people trying to answer your question and for you, if you want to get good answers. IMHO in this case you should add the information about the book into your post. – Martin Sleziak Dec 3 '11 at 18:59

I think it would be to mention the name of the book. Based on the this google search it seems to be Brualdi: Introductory Combinatorics.

From what I understood when I looked into my copy of the books $c(p,k)$ is simply the notation for the $p$-th term of $0$-th diagonal of table obtained from $h_n=n^p$. (In 5th edition, which I have, he refers to Theorem 8.2.2, where the elemets of 0-th diagonal are denoted $c_0,c_1,\dots,c_p,0,0,\dots$, i.e. the $k$-th term of $0$-th diagonal is $c_k$. Here the author simply added one more index to denote the power from the original sequence $h_n=n^p$.)

So you shouldn't look for anything complicated, it's nothing more than the notation for elements of zero-th diagonal. In your example $c(4,0)=0$, $c(4,1)=1$, $c(4,2)=14$, $c(4,3)=36$, $c(4,4)=24$.

This yields the correct values for Stirling numbers of the first kind $S(4,0)=0$, $S(4,1)=1$, $S(4,2)=7$, $c(4,3)=6$, $c(4,4)=1$.

-
Thank you so much! – Gbean Dec 3 '11 at 18:59

Martin has already explained the notation, but you might also find the following connection with Stirling numbers of the second kind useful, since those are the ones mentioned in your title.

If you calculate the $c(n,k)$ for $n=0,1,2,3,4,5$, you get the following array of $0$-th diagonals:

   n\k:  0   1   2   3   4   5
---------------------------
0 |   1
1 |   0   1
2 |   0   1   2
3 |   0   1   6   6
4 |   0   1  14  36  24
5 |   0   1  30 150 240 120


This triangle can be found as A131689 at OEIS, where you can discover that the entry in row $n$, column $k$ is $$k!\left\{\matrix{n\\k}\right\},$$ where $\displaystyle\left\{\matrix{n\\k}\right\}$ is the Stirling number of the second kind. And sure enough, if we divide each entry in column $k$ by $k!$ we get the following table:

   n\k:  0   1   2   3   4   5
---------------------------
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


This is readily recognizable as the table of Stirling numbers of the second kind.

-

It's just a way to introduce notation c(i,j) for the elements of the table.

-
The book can be found online here: filetosi.files.wordpress.com/2010/12/combiatoric.pdf. My questions about c(p,k) begin at pg. 281, halfway through the page. I have read the rest of section 8.2, but there doesn't seem to be an explanation for what c(p,k) is. – Gbean Dec 3 '11 at 18:55