В математике треугольник Белла - это треугольник чисел, аналогичный треугольнику Паскаля , значения которого подсчитывают разбиения множества, в котором данный элемент является наибольшим синглетом . Он назван из-за его тесной связи с числами Белла , [1] которые можно найти по обе стороны треугольника, и которые, в свою очередь, названы в честь Эрика Темпл Белла . Треугольник Белла был независимо открыт несколькими авторами, начиная с Чарльза Сандерса Пирса ( 1880 г. ), а также включая Александра Эйткена ( 1933 г. ) и Кон и др. (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 копируется в третью строку, и процесс продолжается таким же образом.
Комбинаторная интерпретация
Эти цифры Bell сами, на левой и правой сторон треугольника, подсчитать число способов разбиения на конечное множество на подмножества, или что то же самое число отношений эквивалентности на множестве. Sun & Wu (2011) предоставляют следующую комбинаторную интерпретацию каждого значения в треугольнике. Следуя за Сун и Ву, пусть 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 .
В тех же обозначениях Sun & Wu (2011) дополняют треугольник другой диагональю слева от других значений чисел.
подсчет разделов одного и того же набора из n + 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
Этот треугольник может быть построен аналогично исходной версии треугольника Белла, но с другим правилом для начала каждой строки: крайнее левое значение в каждой строке - это разность крайнего правого и крайнего левого значений предыдущей строки.
Альтернативная, но более техническая интерпретация чисел в том же увеличенном треугольнике дана Quaintance & Kwong (2013) .
Диагонали и суммы строк
И крайняя левая, и крайняя правая диагонали треугольника Белла содержат последовательность 1, 1, 2, 5, 15, 52, ... чисел Белла (с отсутствующим начальным элементом в случае крайней правой диагонали). Следующая диагональ, параллельная самой правой диагонали, дает последовательность разностей двух последовательных чисел Белла, 1, 3, 10, 37, ..., а каждая последующая параллельная диагональ дает последовательность разностей предыдущих диагоналей.
Таким образом, как заметил Эйткен (1933) , этот треугольник можно интерпретировать как реализацию формулы интерполяции Грегори – Ньютона , которая находит коэффициенты многочлена из последовательности его значений в последовательных целых числах с использованием последовательных разностей. Эта формула очень похожа на рекуррентное соотношение, которое можно использовать для определения чисел Белла.
Суммы каждой строки треугольника 1, 3, 10, 37, ... представляют собой ту же последовательность первых разностей, которые появляются на второй справа диагонали треугольника. [5] п е число в этой последовательности также рассчитывает количество перегородок из п элементов на подмножества, где один из подмножеств отличаются от других; например, есть 10 способов разбить три элемента на подмножества и затем выбрать одно из подмножеств. [6]
Связанные конструкции
Другой треугольник чисел с числами Белла только на одной стороне и с каждым числом, определяемым как взвешенная сумма ближайших чисел в предыдущей строке, был описан Эйгнером (1999) .
Заметки
- ↑ Согласно Гарднеру (1978) , это имя было предложено Джеффри Шаллитом , чья статья о том же треугольнике была позже опубликована как Шаллит (1980) . Shallit, в свою очередь, считает, что Cohn et al. (1962) для определения треугольника, но Cohn et al. не назвал треугольник.
- ^ а б Слоан, Н. Дж. А. (ред.). «Последовательность A011971 (массив Эйткена)» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS.
- ^ Например, Гарднер (1978) показывает две ориентации, обе отличные от представленной здесь.
- ^ Слоан, Н. Дж. А. (ред.). «Последовательность A106436» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS.
- ^ Гарднер (1978) .
- ^ Слоан, Н. Дж. А. (ред.). «Последовательность A005493» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS..
Рекомендации
- Aigner, Martin (1999), "Характеристика чисел Белла", Дискретная математика , 205 (1-3): 207-210, DOI : 10.1016 / S0012-365X (99) 00108-9 , MR 1703260.
- Aitken, AC (1933), "Проблема в сочетаниях", Математические заметки , 28 : 18-23, DOI : 10,1017 / S1757748900002334.
- Кон, Мартин; Даже, Шимон ; Менгер, Карл младший ; Хупер, Philip K. (1962), "Математические заметки: О числе разбиений множества п различных объектов", American Mathematical Monthly , 69 (8): 782-785, DOI : 10,2307 / 2310780 , MR 1531841.
- Гарднер, Мартин (1978), «Колокола: универсальные числа, которые могут подсчитывать части множества, простые числа и даже рифмы», Scientific American , 238 : 24–30, DOI : 10.1038 / Scientificamerican0578-24. Перепечатано с дополнением под названием «Звонкие храмовые колокола», глава 2 книги « Фрактальная музыка, гиперкарты и др.». «Математические развлечения от Scientific American» , WH Freeman, 1992, стр. 24–38.
- Пирса, CS (1880), "Об алгебре логики", Американский журнал математики , 3 (1): 15-57, DOI : 10,2307 / 2369442 , JSTOR 2369442. Треугольник находится на стр. 48.
- Причудливый, Джоселин; Квонг, Харрис (2013), «Комбинаторная интерпретация таблиц разностей каталонских и беллских чисел» (PDF) , Целые числа , 13 : A29.
- Шаллит, Джеффри (1980), «Треугольник для чисел Белла», Сборник рукописей, относящихся к последовательности Фибоначчи (PDF) , Санта-Клара, Калифорния: Ассоциация Фибоначчи, стр. 69–71, MR 0624091.
- Солнце, Идун; Ву, Сяоцзюань (2011), «Самые большие синглтоны множественных разделов», Европейский журнал комбинаторики , 32 (3): 369–382, arXiv : 1007.1341 , doi : 10.1016 / j.ejc.2010.10.011 , MR 2764800.
Внешние ссылки
- Вайсштейн, Эрик В. «Белл-треугольник» . MathWorld .