Aitken's array

In mathematics, the Bell triangle is a triangle of numbers analogous to Pascal's triangle, whose values count partitions of a set in which a given element is the largest singleton. It is named for its close connection to the Bell numbers, which may be found on both sides of the triangle, and which are in turn named after Eric Temple Bell. The Bell triangle has been discovered independently by multiple authors, beginning with Charles Sanders Peirce (1880) and including also Alexander Aitken (1933) and Cohn et al. (1962), and for that reason has also been called Aitken's array or the Peirce triangle.

Different sources give the same triangle in different orientations, some flipped from each other. In a format similar to that of Pascal's triangle, and in the order listed in the Online Encyclopedia of Integer Sequences, its first few rows are:

The Bell triangle may be constructed by placing the number 1 in its first position. After that placement, the leftmost value in each row of the triangle is filled by copying the rightmost value in the previous row. The remaining positions in each row are filled by a rule very similar to that for Pascal's triangle: they are the sum of the two values to the left and upper left of the position.

Thus, after the initial placement of the number 1 in the top row, it is the last position in its row and is copied to the leftmost position in the next row. The third value in the triangle, 2, is the sum of the two previous values above-left and left of it. As the last value in its row, the 2 is copied into the third row, and the process continues in the same way.

The Bell numbers themselves, on the left and right sides of the triangle, count the number of ways of partitioning a finite set into subsets, or equivalently the number of equivalence relations on the set. Sun & Wu (2011) provide the following combinatorial interpretation of each value in the triangle. Following Sun and Wu, let A_n,k denote the value that is k positions from the left in the nth row of the triangle, with the top of the triangle numbered as A_1,1. Then A_n,k counts the number of partitions of the set {1, 2, ..., n + 1} in which the element k + 1 is the only element of its set and each higher-numbered element is in a set of more than one element. That is, k + 1 must be the largest singleton of the partition.

...
Wikipedia