Bell triangle

Construction of the Bell triangle

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,[1] 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.[2]

Values

Different sources give the same triangle in different orientations, some flipped from each other.[3] In a format similar to that of Pascal's triangle, and in the order listed in the On-Line Encyclopedia of Integer Sequences (OEIS), its first few rows are:[2] 

                    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. Sun & Wu (2011) 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 {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.

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 {1, 2, 3, 4} in which 3 is the largest singleton element. There are three such partitions:

{1}, {2, 4}, {3}
{1, 4}, {2}, {3}
{1, 2, 4}, {3}.

The remaining partitions of these four elements either do not have 3 in a set by itself, or they have a larger singleton set {4}, and in either case are not counted in A3,2.

In the same notation, Sun & Wu (2011) augment the triangle with another diagonal to the left of its other values, of the numbers

An,0 = 1, 0, 1, 1, 4, 11, 41, 162, ...(sequence A000296 in the OEIS)

counting partitions of the same set of n + 1 items in which only the first item is a singleton. Their augmented triangle is[4] 

                       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 Quaintance & Kwong (2013).

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 (with the initial element missing in the case of the rightmost diagonal). 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 Aitken (1933) 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.[5] 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.[6]

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 Aigner (1999).

Notes

  1. ^ According to Gardner (1978), this name was suggested by Jeffrey Shallit, whose paper about the same triangle was later published as Shallit (1980). Shallit in turn credits Cohn et al. (1962) for the definition of the triangle, but Cohn et al. did not name the triangle.
  2. ^ a b Sloane, N. J. A. (ed.). "Sequence A011971 (Aitken's array)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
  3. ^ For instance, Gardner (1978) shows two orientations, both different from the one here.
  4. ^ Sloane, N. J. A. (ed.). "Sequence A106436". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
  5. ^ Gardner (1978).
  6. ^ Sloane, N. J. A. (ed.). "Sequence A005493". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation..

References