# Bell numbers, recursions, bijections

The $n$th Bell number, named after Eric Temple Bell (although he was far from the first to think about them), is the number of partitions of a set of cardinality $n$. If they are written in the top row of this triangle, starting with the $0$th Bell number, which is $1$, and each number is the sum of the two above, it, then the numbers on the left edge are the Bell numbers starting with the $1$th Bell number (not to be confused with the $1$st Bell number....): $$\begin{array}{ccccccccccccc} 1 & & 1 & & 2 & & 5 & & 15 & & 52 & & 203 \\ & 2 & & 3 & & 7 & & 20 & & 67 & & 255 \\ & & 5 & & 10 & & 27 & & 87 & & 322 \\ & & & 15 & & 37 & & 114 & & 409 \\ & & & & 52 & & 151 & & 523 \\ & & & & & 203 & & 674 \\ & & & & & & 877 \end{array}$$ Thus suppose we have any finite initial part of the table: $$\begin{array}{ccccccccccccc} 1 & & 1 & & 2 & & 5 & & 15 \\ & 2 & & 3 & & 7 & & 20 \\ & & 5 & & 10 & & 27 \\ & & & 15 & & 37 \\ & & & & 52 \end{array}$$ The number at the very bottom tells us what number to write next in the top row, and thus we have a recursion that gives us the whole sequence of Bell numbers. Now of course this tells us that $$\sum_{i=1}^\ell \binom \ell i B_i = B_{\ell+1},\tag{TYPO HERE}$$ which is another (Or is it really the same one?) recursion formula for the Bell numbers.
Later edit: The line above should have started the summation at $0$ rather than $1$, thus: $$\sum_{i=0}^\ell \binom \ell i B_i = B_{\ell+1}$$ end of later edit

Now "everybody knows" (?) that much. (See Gian-Carlo Rota's paper "The Number of Partitions of a Set" in the 1964 volume of the American Mathematical Monthly.) But the triangular array implies more than that. Number the rows starting with $0$ and the entries in each row starting with $0$, so that $B_{j,i}$ is entry $i$ in row $j$. Then the triangular array tells us that $$\sum_{i=k}^\ell \binom{\ell-k}{i} B_{j,i} = B_{j+\ell-k,\,j}.\tag{TYPO HERE}$$ Later edit: The index $k$ above should have gone from $0$ to $\ell-k$. And since $\ell$ and $k$ appear only in the expression $\ell-k$, we may as well just use $\ell$ to denote what was called $\ell-k$. And we also fix another problem in the line below: $$\sum_{i=0}^\ell \binom \ell i B_{j,i+k} = B_{j+k-1,k}$$ end of later edit

So my questions are:

• How can $(1)$ be proved bijectively?
• Is $(1)$ in the literature somewhere (specify!)?
-
I'm surprised that two people voted for this before I fixed a hideous....um....typo....that said "permutations" where it should have said "partitions". They didn't comment on that. At any rate it's fixed now. –  Michael Hardy Apr 14 '12 at 17:57
What you need is an intuitive combinatorial description of the numbers $B_{j,i}$ appearing in the obscure triangular array you set up. –  Christian Blatter Apr 14 '12 at 18:18
I've found that recursion-formula in my article on Bell-numbers (see go.helms-net.de/math/binomial_new/04_5_SummingBellStirling.pdf) on page 6. Here it is derived by some property of the binomial-coefficients together with the Stirling-numbers 2nd kind. Perhaps there is something more interesting in it (however that's not "literature" and no proof is given...) –  Gottfried Helms Apr 14 '12 at 19:18
Might be in Comtet's book - I'm not in my office, so I can't check. –  Gerry Myerson Apr 14 '12 at 23:38
OK, I hope I've fixed the typos. –  Michael Hardy May 29 '12 at 2:01

For a bijective interpretation, you first need a combinatorial interpretation for the numbers.

A look at the encyclopedia of integer sequences suggests the following:

$B_{n,k}$ is the number of set partitions of $n+1$ elements where the element $n+1$ cannot be in the same part with another element $\ge k$. (Note that I have adhered to your choice of indexing in the order col/rows and in your table, $n$ starts at 0 and $k$ starts at 1.)

It is easy to check that this interpretation works by regarding the case that $n+1$ does not share a part with $k-1$ (giving $B_{n,k-1}$) and the case that $n+1$ does share part with $k-1$ (giving $B_{n,k-1}$).

For $k=1$, the element $n+1$ is forced to be a singleton, so we recover $B_n$. (And for $k=n+1$, the condition is empty, so we recover $B_{n+1}$.)

Your recursion (1) contains some typos, for that reason I won't write details, but the interpretation is straight-forward, that among a certain set of numbers (whose size corresponds to the size of the sub-triangle you are looking at), you choose those that go in the same part as $n+1$ and those that don't.

There can be no doubt that all this is well-known.

-
Interesting that there's that category of facts concerning which one cannot doubt that it's well-known without being able to cite anything. No one should publish the fact that $17\times 37= 629$ unless it's in something like a table of prime factorizations or a multiplication table, and then there are tables of identities published in place like CRC, and then there are miscellaneous facts like this one, that maybe no one tabulates. Might the internet change that? A wiki devoted to....."table"....of zillions of things like this? –  Michael Hardy May 18 '12 at 16:13
.....and I've finally printed this one, and will look at it more closely now. –  Michael Hardy May 28 '12 at 2:11