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 and including also and, and for that reason has also been called Aitken's array or the Peirce triangle.
Values
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: 1 1 2 2 3 5 5 7 10 15 15 20 27 37 52 52 67 87 114 151 203 203 255 322 409 523 674 877
Construction
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.
Combinatorial interpretation
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. provide the following combinatorial interpretation of each value in the triangle. Following Sun and Wu, let An,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 A1,1. Then An,k counts the number of partitions of the set 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. For instance, the number 3 in the middle of the third row of the triangle would be labeled, in their notation, as A3,2, and counts the number of partitions of in which 3 is the largest singleton element. There are three such partitions: The remaining partitions of these four elements either do not have 3 in a set by itself, or they have a larger singleton set, and in either case are not counted in A3,2. In the same notation, augment the triangle with another diagonal to the left of its other values, of the numbers counting partitions of the same set of n + 1 items in which only the first item is a singleton. Their augmented triangle is 1 0 1 1 1 2 1 2 3 5 4 5 7 10 15 11 15 20 27 37 52 41 52 67 87 114 151 203 162 203 255 322 409 523 674 877 This triangle may be constructed similarly to the original version of Bell's triangle, but with a different rule for starting each row: the leftmost value in each row is the difference of the rightmost and leftmost values of the previous row. An alternative but more technical interpretation of the numbers in the same augmented triangle is given by.
Diagonals and row sums
The leftmost and rightmost diagonals of the Bell triangle both contain the sequence 1, 1, 2, 5, 15, 52,... of the Bell numbers. The next diagonal parallel to the rightmost diagonal gives the sequence of differences of two consecutive Bell numbers, 1, 3, 10, 37,..., and each subsequent parallel diagonal gives the sequence of differences of previous diagonals. In this way, as observed, this triangle can be interpreted as implementing the Gregory–Newton interpolation formula, which finds the coefficients of a polynomial from the sequence of its values at consecutive integers by using successive differences. This formula closely resembles a recurrence relation that can be used to define the Bell numbers. The sums of each row of the triangle, 1, 3, 10, 37,..., are the same sequence of first differences appearing in the second-from-right diagonal of the triangle. The nth number in this sequence also counts the number of partitions of n elements into subsets, where one of the subsets is distinguished from the others; for instance, there are 10 ways of partitioning three items into subsets and then choosing one of the subsets.
Related constructions
A different triangle of numbers, with the Bell numbers on only one side, and with each number determined as a weighted sum of nearby numbers in the previous row, was described by.
