Треугольник колокола
В математике треугольник Белла — это треугольник чисел, аналогичный треугольнику Паскаля , значения которого подсчитывают разделы множества , в котором данный элемент является наибольшим одноэлементным . Оно названо в честь своей тесной связи с числами Белла . [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 203
203 255 322 409 523 674 877
Строительство
[ редактировать ]Треугольник Белла можно построить, поместив цифру 1 на первое место. После этого размещения самое левое значение в каждой строке треугольника заполняется путем копирования самого правого значения в предыдущей строке. Остальные позиции в каждой строке заполняются по правилу, очень похожему на правило треугольника Паскаля : они представляют собой сумму двух значений слева и вверху слева от позиции.
Таким образом, после первоначального размещения цифры 1 в верхней строке она является последней позицией в своей строке и копируется в самую левую позицию в следующей строке. Третье значение в треугольнике, 2, представляет собой сумму двух предыдущих значений слева и слева от него. В качестве последнего значения в своей строке 2 копируется в третью строку, и процесс продолжается таким же образом.
Комбинаторная интерпретация
[ редактировать ]на Сами числа Белла левой и правой сторонах треугольника подсчитывают количество способов разбиения на конечного множества подмножества или, что то же самое, количество отношений эквивалентности на множестве. Сан и Ву (2011) предлагают следующую комбинаторную интерпретацию каждого значения в треугольнике. Следуя Sun и Wu, пусть An ,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 равно 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 203
162 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] -е число n в этой последовательности также подсчитывает количество разбиений n элементов на подмножества, при которых одно из подмножеств отличается от других; например, существует 10 способов разбить три элемента на подмножества и затем выбрать одно из подмножеств. [6]
Связанные конструкции
[ редактировать ]Другой треугольник чисел, в котором числа Белла находятся только на одной стороне и где каждое число определяется как взвешенная сумма соседних чисел в предыдущей строке, был описан Айгнером (1999) .
Примечания
[ редактировать ]- ^ По мнению Гарднера (1978) , это название было предложено Джеффри Шаллитом , чья статья о том же треугольнике была позже опубликована как Шалит (1980) . Шалит, в свою очередь, благодарит Кона и др. (1962) для определения треугольника, но Кон и др. не назвал треугольник.
- ^ Jump up to: Перейти обратно: а б Слоан, Нью-Джерси (ред.). «Последовательность A011971 (массив Эйткена)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
- ↑ Например, Гарднер (1978) показывает две ориентации, обе отличающиеся от представленной здесь.
- ^ Слоан, Нью-Джерси (ред.). «Последовательность A106436» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
- ^ Гарднер (1978) .
- ^ Слоан, Нью-Джерси (ред.). «Последовательность A005493» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС. .
Ссылки
[ редактировать ]- Айгнер, Мартин (1999), «Характеристика чисел Белла», Discrete Mathematics , 205 (1–3): 207–210, doi : 10.1016/S0012-365X(99)00108-9 , MR 1703260 .
- Эйткен, AC (1933), «Проблема в комбинациях», Mathematical Notes , 28 : 18–23, doi : 10.1017/S1757748900002334 .
- Кон, Мартин; Даже Шимон ; Менгер, Карл младший ; Хупер, Филип К. (1962), «Математические заметки: о количестве разделений набора из n различных объектов», American Mathematical Monthly , 69 (8): 782–785, doi : 10.2307/2310780 , JSTOR 2310780 , MR 1531841 .
- Гарднер, Мартин (1978), «Колокола: универсальные числа, которые могут считать части множества, простые числа и даже рифмы», Scientific American , 238 : 24–30, Bibcode : 1978SciAm.238e..24G , doi : 10.1038/scientificamerican0578 -24 . Перепечатано с приложением под названием «Звенящие храмовые колокола», глава 2 книги « Фрактальная музыка, гиперкарты и многое другое… Математические развлечения» от Scientific American , WH Freeman, 1992, стр. 24–38.
- Пирс, CS (1880), «Об алгебре логики», American Journal of Mathematics , 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 , S2CID 30627275 .