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

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$.

Answer 2

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

Answer 3

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.