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

${\begin{array}{lllll}1\\1&2\\2&3&5\\5&7&10&15\\15&20&27&37&52\\\end{array}}$

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

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

Значения

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

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

Комбинаторная интерпретация

Числа Белла с левой и правой сторон треугольника содержат число способов разбиения конечного множества на подмножества, или, эквивалентно, число возможных отношений эквивалентности на множестве. Сан и Ву дают следующую комбинаторную интерпретацию каждому значению в треугольнике. Пусть 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.

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

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

содержащими число разбиений того же множества из 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 способов разбить три элемента на подмножества и выбрать затем одно из подмножеств.

Связанные построения

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

Ссылки

• Weisstein, Eric W. Bell Triangle (англ.) на сайте Wolfram MathWorld.