Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.