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!)?
Best Answer
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.