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

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

Значения

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

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

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

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

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

A_n,0=1, 0, 1, 1, 4, 11, 41, 162, ...(Шаблон: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

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

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

Суммы диагоналей и строк

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

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

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

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

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

Литература

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

Ссылки

• Шаблон:Mathworld