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!)?