Треугольник Белла

Треугольник Белла — это треугольник чисел, аналогичный треугольнику Паскаля, значения которого содержат число разбиений множества, в которых заданный элемент является наибольшим синглтоном. Треугольник назван по тесной связи с числами Белла, которые можно найти с обеих сторон треугольника, (названные именем Эрика Темпла Белла). Треугольник Белла был неоднократно открыт независимо несколькими авторами, начиная с Чарльза Сандерса Пирса и включая Александра Айткена и группу авторов — Кона, Ивена, Менгера и Хупера. По этой причине треугольник называется также массивом Айткена или треугольником Пирса

Значения 
Различные источники дают различные ориентации, иногда симметричные относительно друг друга. В формате, подобном треугольнику Паскаля, и с порядком элементов, как в «Энциклопедии целочисленных последовательностей», треугольник выглядит следующим образом

                     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

Построение 

Треугольник Белла можно построить путём размещения числа 1 в первой позиции. Затем все самые левые числа берутся равными последнему числу предыдущей строки. Остальные позиции строки заполняются аналогично правилу заполнения треугольника Паскаля — число равно сумме значений слева в той же строке и слева из предшествующей строки.

Таким образом, после копирования 1 во вторую строку, второе число в строке будет равно сумме двух единиц (из первой строки и из второй строки). Продолжаем в том же духе.

Комбинаторная интерпретация 
Числа Белла с левой и правой сторон треугольника содержат число способов разбиения конечного множества на подмножества, или, эквивалентно, число возможных отношений эквивалентности на множестве.
Сан и Ву дают следующую комбинаторную интерпретацию каждому значению в треугольнике. Пусть An,k означает число в k-ой позиции слева в n-ой строке треугольника. Число на вершине треугольника будет иметь обозначение A1,1. Тогда An,k равно числу разбиений множества {1, 2, ..., n + 1}, в которых элемент k + 1 является единственным элементом подмножества и каждое число, превосходящее его, содержится в подмножестве с более чем одним элементом. То есть k + 1 должен быть наибольшим синглтоном разбиения.

Например, число 3 в середине третьей строки треугольника в этих обозначениях есть A3,2 и подсчитывает число разбиений множества {1, 2, 3, 4}, в которых 3 является наибольшим синглтоном. Есть три таких разбиения:
 {1}, {2, 4}, {3}
 {1, 4}, {2}, {3}
 {1, 2, 4}, {3}.
Остальные разбиения этих четырёх элементов либо не содержат подмножество, состоящее лишь из элемента 3, либо они содержат больший синглтон {4}, а потому не учитываются в A3,2.

В тех же обозначениях Сан и Ву добавили в треугольник диагональ слева со значениями
 An,0=1, 0, 1, 1, 4, 11, 41, 162, ...()
содержащими число разбиений того же множества из n + 1 элементов, в которых только первый элемент является синглтоном. Их расширенный треугольник имеет вид

                        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

Этот треугольник можно построить аналогично исходной версии треугольника Белла с изменённым правилом формирования первого элемента строки — элемент равен разности последнего и первого элементов предыдущей строки.

Альтернативная, но более техническая интерпретация чисел в том же расширенном треугольнике дают Куэйнтенс и Квонг.

Суммы диагоналей и строк 
Левый и правый диагонали треугольника Белла содержат последовательность 1, 1, 2, 5, 15, 52, ... чисел Белла (в правой диагонали отсутствует первое число Белла). Следующая диагональ, параллельная крайней правой диагонали, даёт разности двух последовательных чисел Белла, 1, 3, 10, 37, ..., и каждая последующая параллельная диагональ содержит разности предыдущей диагонали.

Таким образом, как заметил Айткен, этот треугольник можно понимать как имплементацию интерполяционной формулы Ньютона для нахождения коэффициентов многочлена по его значениям в целочисленных точках. Эта формула имеет близкое сходство с рекуррентным отношением, которое можно использовать для определения чисел Белла.

Суммы по строкам треугольника, 1, 3, 10, 37, ..., совпадают с числами второй правой диагонали треугольника. Число с номером n в этой последовательности содержит число позиций n элементов в подмножествах, где одно из подмножеств отличается от остальных. Например, имеется 10 способов разбить три элемента на подмножества и выбрать затем одно из подмножеств.

Связанные построения 
Другой треугольник чисел с числами Белла на одной стороне, а каждое число определяется как взвешенная сумма близлежащих чисел в предыдущей строке, описал Айгнер.

Примечания

Литература 

 
 
 
 . Перепечатано с добавлением "The Tinkly Temple Bells", глава 2 Fractal Music, Hypercards, and more ... Mathematical Recreations from Scientific American, W. H. Freeman, 1992, стр. 24–38.
 . Треугольник описан на стр. 48.

Ссылки 
 

Треугольники чисел