Треугольник колокола - Bell triangle

Построение треугольника Колокола

В математике Треугольник колокола представляет собой треугольник чисел, аналогичный Треугольник Паскаля, чьи значения считаются перегородки набора в котором данный элемент является самым большим одиночка. Он назван в честь его тесной связи с Номера звонков,^[1] которые можно найти по обе стороны треугольника, и которые, в свою очередь, названы в честь Эрик Темпл Белл. Треугольник Белла был независимо открыт несколькими авторами, начиная с Чарльз Сандерс Пирс  (1880 ), а также Александр Айткен  (1933 ) и Cohn et al. (1962), и по этой причине также был назван Массив Эйткена или Треугольник Пирса.^[2]

Ценности

Разные источники дают один и тот же треугольник в разной ориентации, некоторые из которых перевернуты.^[3] В формате, аналогичном формату треугольника Паскаля, и в порядке, указанном в Интернет-энциклопедия целочисленных последовательностей, его первые несколько строк:^[2]

                    1                 1     2              2     3     5           5     7    10    15       15    20    27    37    52    52    67    87   114   151   203203   255   322   409   523   674   877

строительство

Треугольник Колокольчика можно построить, поместив цифру 1 в его первую позицию. После этого размещения крайнее левое значение в каждой строке треугольника заполняется путем копирования самого правого значения в предыдущей строке. Остальные позиции в каждой строке заполняются по правилу, очень похожему на правило Треугольник Паскаля: они представляют собой сумму двух значений слева и вверху слева от позиции.

Таким образом, после первоначального размещения числа 1 в верхней строке это последняя позиция в своем ряду и копируется в крайнюю левую позицию в следующей строке. Третье значение в треугольнике, 2, является суммой двух предыдущих значений вверху слева и слева от него. Как последнее значение в своей строке, 2 копируется в третью строку, и процесс продолжается таким же образом.

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

В Номера звонков сами, на левой и правой сторонах треугольника, посчитайте количество способов разделение а конечный набор на подмножества, или, что то же самое, количество отношения эквивалентности на съемочной площадке.Сунь и Ву (2011) дайте следующую комбинаторную интерпретацию каждого значения в треугольнике. Вслед за Сун и Ву пусть А_{п, к} обозначают значение, которое k позиции слева в п-й ряд треугольника, вершина которого пронумерована А_1,1. потом А_{п, к} подсчитывает количество разбиений множества {1, 2, ...,п + 1}, в котором элемент k + 1 - единственный элемент этого набора, и каждый элемент с более высоким номером входит в набор из более чем одного элемента. Это, k +1 должен быть самым большим одиночка раздела.

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

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

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

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

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

В тех же обозначениях Сунь и Ву (2011) увеличьте треугольник с другой диагональю слева от других его значений, чисел

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

подсчет разделов одного и того же набора п +1 элемент, в котором только первый элемент является синглтоном. Их увеличенный треугольник^[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   203162   203   255   322   409   523   674   877

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

Альтернативная, но более техническая интерпретация чисел в том же увеличенном треугольнике дается формулой Причудливый и Квонг (2013).

Диагонали и суммы строк

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

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

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

Связанные конструкции

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

Заметки

использованная литература

• Айгнер, Мартин (1999), "Характеристика чисел Белла", Дискретная математика, 205 (1–3): 207–210, Дои:10.1016 / S0012-365X (99) 00108-9, Г-Н  1703260.
• Эйткен, А.С. (1933), «Проблема в комбинациях», Математические заметки, 28: 18–23, Дои:10.1017 / S1757748900002334.
• Кон, Мартин; Эвен, Шимон; Менгер, Карл младший; Хупер, Филип К. (1962), "Математические заметки: О количестве разбиений набора п отдельные объекты ", Американский математический ежемесячный журнал, 69 (8): 782–785, Дои:10.2307/2310780, Г-Н  1531841.
• Гарднер, Мартин (1978), «Колокола: универсальные числа, которые могут считать части набора, простые числа и даже рифмы», Scientific American, 238: 24–30, Дои:10.1038 / scientificamerican0578-24. Перепечатано с дополнением как «Звенящие храмовые колокола», глава 2 Фрактальная музыка, гиперкарты и многое другое ... Математические развлечения от Scientific American, W. H. Freeman, 1992, стр. 24–38.
• Пирс, К.С. (1880 г.), «Об алгебре логики», Американский журнал математики, 3 (1): 15–57, Дои:10.2307/2369442, JSTOR  2369442. Треугольник находится на стр. 48.
• Причудливый, Джоселин; Квонг, Харрис (2013), «Комбинаторная интерпретация каталонских таблиц разностей чисел Белла» (PDF), Целые числа, 13: A29.
• Шаллит, Джеффри (1980), «Треугольник для чисел Белла», Сборник рукописей, связанных с последовательностью Фибоначчи (PDF), Санта-Клара, Калифорния: Ассоциация Фибоначчи, стр. 69–71, Г-Н  0624091.
• Солнце, Идун; Ву, Сяоцзюань (2011 г.), «Самые большие синглтоны из множества разделов», Европейский журнал комбинаторики, 32 (3): 369–382, arXiv:1007.1341, Дои:10.1016 / j.ejc.2010.10.011, Г-Н  2764800.

внешние ссылки

• Вайсштейн, Эрик В. "Белл-треугольник". MathWorld.