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

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

                    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 во вторую строку, второе число в строке будет равно сумме двух единиц (из первой строки и из второй строки). Продолжаем в том же духе.

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

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

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

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

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

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

В тех же обозначениях Сан и Ву^[8] добавили в треугольник диагональ слева со значениями

A_n,0=1, 0, 1, 1, 4, 11, 41, 162, …(последовательность A000296 в OEIS)

содержащими число разбиений того же множества из n + 1 элементов, в которых только первый элемент является синглтоном. Их расширенный треугольник имеет вид^[9]

                       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

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

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

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

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

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

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