[Math] Stirling Numbers of the Second Kind

Question

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.

Answer 1

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.