Номер звонка - Bell number
В комбинаторная математика, то Номера звонков посчитать возможное перегородки набора. Эти числа изучаются математиками с XIX века, и их корни уходят в средневековую Японию. В примере Закон Стиглера эпонимии, они названы в честь Эрик Темпл Белл, писавший о них в 1930-е гг.
Числа Белла обозначены Bп, куда п является целое число больше или равно нуль. Начиная с B0 = B1 = 1, первые несколько чисел Белла
Номер звонка Bп подсчитывает количество различных способов разбиения набора, в котором ровно п элементов, или, что то же самое, количество отношения эквивалентности в теме. Bп также подсчитывает количество различных схемы рифм за пстихотворения.[1]
Эти числа не только появляются в задачах счета, но и имеют другую интерпретацию, так как моменты из распределения вероятностей. Особенно, Bп это пй момент распределение Пуассона с иметь в виду 1.
Подсчет
Установить перегородки
В целом, Bп это количество перегородки набора размеров п. Перегородка набора S определяется как набор непустых, попарно непересекающихся подмножеств S чей союз S. Например, B3 = 5, поскольку трехэлементный набор {а, б, c} можно разделить 5 различными способами:
- { {а}, {б}, {c} }
- { {а}, {б, c} }
- { {б}, {а, c} }
- { {c}, {а, б} }
- { {а, б, c} }.
B0 равно 1, потому что существует ровно одно разделение пустой набор. Каждый член пустого множества - непустое множество (то есть пусто правда ), а их объединение - пустое множество. Следовательно, пустой набор - это единственное само по себе разделение. В соответствии с указанными выше обозначениями, мы не рассматриваем ни порядок блоков в разделе, ни порядок элементов в каждом блоке. Это означает, что следующие разделы считаются идентичными:
- { {б}, {а, c} }
- { {а, c}, {б} }
- { {б}, {c, а} }
- { {c, а}, {б} }.
Если вместо этого различные порядки наборов считаются разными разделами, то количество этих заказанные перегородки дается заказанные номера Bell.
Факторизации
Если число N это свободный от квадратов положительный целое число (означает, что это произведение некоторого числа п различных простые числа ), тогда Bп дает количество различных мультипликативные разделы из N. Эти факторизации из N на числа больше единицы, рассматривая две факторизации как одинаковые, если они имеют одинаковые множители в разном порядке.[2] Например, 30 является произведением трех простых чисел 2, 3 и 5 и имеет B3 = 5 факторизаций:
Схемы рифм
Числа Bell также учитывают схемы рифм из п-линия стих или строфа. Схема рифм описывает, какие строки рифмуются друг с другом, и поэтому может интерпретироваться как разделение набора строк на рифмующиеся подмножества. Схемы рифм обычно записываются как последовательность латинских букв, по одной в строке, причем рифмующиеся строки имеют ту же букву, что и друг друга, а первые строки в каждом наборе рифм обозначаются в алфавитном порядке. Таким образом, 15 возможных четырехстрочных схем рифмы - это AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC и ABCD.[1]
Перестановки
Цифры Белла появляются на карточке шаркающий проблема, упомянутая в дополнении к Гарднер (1978). Если колода п карты перетасовываются путем многократного извлечения верхней карты и повторной вставки ее в любое место колоды (включая ее исходное положение наверху колоды), причем точно п повторений этой операции, то есть пп различные тасования, которые могут быть выполнены. Из них число, возвращающее колоду в исходный отсортированный порядок, точно равно Bп. Таким образом, вероятность того, что колода окажется в исходном порядке после перетасовки, равна Bп/пп, что значительно больше, чем 1 /п! вероятность, описывающая равномерно случайную перестановку колоды.
С перетасовкой карт связано несколько других проблем, связанных с подсчетом особых видов перестановки на которые также отвечают числа Bell. Например, пчисло Белла равно количеству перестановок на п элементы, в которых нет трех значений в отсортированном порядке, имеют последние два из этих трех последовательных. В обозначениях для обобщенных шаблоны перестановок где значения, которые должны быть последовательными, записываются рядом друг с другом, а значения, которые могут появляться не последовательно, разделяются тире, эти перестановки можно описать как перестановки, которые избегают шаблона 1-23. Перестановки, которые избегают обобщенных шаблонов 12-3, 32-1, 3-21, 1-32, 3-12, 21-3 и 23-1, также считаются числами Белла.[3] Перестановки, в которых каждый шаблон 321 (без ограничения на последовательные значения) может быть расширен до шаблона 3241, также учитываются числами Белла.[4] Однако числа Белла растут слишком быстро, чтобы подсчитать перестановки, которые избегают паттерна, который не был обобщен таким образом: согласно (теперь доказано) Гипотеза Стэнли – Уилфа, количество таких перестановок является однократно экспоненциальным, и числа Белла имеют более высокую скорость асимптотического роста, чем это.
Схема треугольника для расчетов
Числа Белла можно легко вычислить, создав так называемые Треугольник колокола, также называемый Массив Эйткена или Треугольник Пирса после Александр Айткен и Чарльз Сандерс Пирс.[5]
- Начните с номера один. Выложите это в ряд отдельно. ()
- Начните новую строку с самого правого элемента из предыдущей строки как крайнего левого числа ( куда р последний элемент (я-1) -й ряд)
- Определите числа не в левом столбце, взяв сумму числа слева и числа над числом слева, то есть числа по диагонали вверх и влево от числа, которое мы вычисляем.
- Повторяйте шаг 3 до тех пор, пока не появится новая строка с числом больше, чем в предыдущей строке (выполняйте шаг 3, пока )
- Число в левой части данной строки - это Номер звонка для этой строки. ()
Вот первые пять рядов треугольника, построенного по этим правилам:
1 1 2 2 3 5 5 7 10 1515 20 27 37 52
Цифры Белл появляются как на левой, так и на правой стороне треугольника.
Характеристики
Формулы суммирования
Числа Белла удовлетворяют отношение повторения с участием биномиальные коэффициенты:[6]
Это можно объяснить, заметив, что из произвольного разбиения п +1 элементов, удаление набора, содержащего первый элемент, оставляет раздел меньшего набора k предметы для некоторого числа k который может варьироваться от 0 до п. Есть выбор для k предметы, которые остаются после удаления одного набора, и Bk выбор того, как их разделить.
Другая формула суммирования представляет каждое число Белла как сумму Числа Стирлинга второго рода
Число Стирлинга это количество способов разбить набор мощности п точно в k непустые подмножества. Таким образом, в уравнении, связывающем числа Белла с числами Стирлинга, каждое разбиение, подсчитываемое в левой части уравнения, учитывается точно в одном из членов суммы в правой части, для которой k - количество наборов в разделе.[7]
Спайви (2008) дал формулу, которая объединяет оба этих суммирования:
Производящая функция
В экспоненциальная производящая функция чисел Белла
В этой формуле суммирование в середине является общей формой, используемой для определения экспоненциальной производящей функции для любой последовательности чисел, а формула справа является результатом выполнения суммирования в конкретном случае чисел Белла.
Один из способов получить этот результат использует аналитическая комбинаторика, стиль математических рассуждений, в котором наборы математических объектов описываются формулами, объясняющими их построение из более простых объектов, а затем этими формулами манипулируют для получения комбинаторных свойств объектов. На языке аналитической комбинаторики разбиение множества можно описать как множество непустых урны в какие элементы, обозначенные от 1 до п были распространены, и комбинаторный класс всех разделов (для всех п) может быть выражено обозначениями
Здесь, - это комбинаторный класс, состоящий только из одного члена первого размера, элемента, который можно поместить в урну. Внутренний оператор описывает набор или урну, содержащую один или несколько помеченных элементов, а внешний описывает общую перегородку как набор этих урн. Затем экспоненциальную производящую функцию можно считать из этой записи, переведя в экспоненциальную функцию, а ограничение непустоты ≥1 - в вычитание на единицу.[8]
Альтернативный метод получения той же производящей функции использует рекуррентное соотношение для чисел Белла в терминах биномиальных коэффициентов, чтобы показать, что экспоненциальная производящая функция удовлетворяет дифференциальное уравнение . Саму функцию можно найти, решив это уравнение.[9][10][11]
Моменты вероятностных распределений
Числа Белла удовлетворяют Формула Добинского[12][9][11]
Эта формула может быть получена путем расширения экспоненциальной производящей функции с использованием Серия Тейлор для экспоненциальной функции, а затем собрать члены с тем же показателем.[8]Это позволяет Bп интерпретироваться как пth момент из распределение Пуассона с ожидаемое значение 1.
В пчисло Белла также является суммой коэффициентов в пth полный полином Белла, что выражает пth момент любой распределение вероятностей как функция первого п кумулянты.
Модульная арифметика
Номера Bell подчиняются Конгруэнтность Тушара: Если п есть ли простое число тогда[13]
или, обобщая[14]
Из-за сравнения Тушара числа Белла периодичны по модулю п, для каждого простого числа п; например, для п = 2, числа Белла повторяют схему чет-нечет-нечет с периодом три. Период этого повторения для произвольного простого числа п, должно быть делителем
и для всех премьер п ≤ 101 и п = 113, 163, 167 или 173 именно это число (последовательность A001039 в OEIS ).[15][16]
Период чисел Белла по модулю п находятся
- 1, 3, 13, 12, 781, 39, 137257, 24, 39, 2343, 28531167061, 156, 25239592216021, 411771, 10153, 48, 51702516367896047761, 39, 109912203092239643840221, 9372, 1784341, 312391239643840221, 9372, 1784341, 85593127128343, 9683197128348 75718776648063, 117, 1647084, 91703076898614683377208150526107718802981, 30459, 568972471024107865287021434301977158534824481, 96, 370905171793, 155107549103688143283, 107197717, последовательность, A054767 в OEIS )
Интегральное представление
Применение Интегральная формула Коши к экспоненциальной производящей функции дает комплексное интегральное представление
Некоторые асимптотические представления могут быть получены стандартным применением способ наискорейшего спуска.[17]
Бревенчатая вогнутость
Числа Белла образуют логарифмически выпуклая последовательность. Разделив их на факториалы, Bп/п!, дает логарифмически вогнутую последовательность.[18][19][20]
Скорость роста
Несколько асимптотический формулы для чисел Белла известны. В Беренд и Тасса (2010) были установлены следующие границы:
- для всех положительных целых чисел ;
кроме того, если тогда для всех ,
куда иЧисла Белла также могут быть аппроксимированы с помощью W функция Ламберта, функция с той же скоростью роста, что и логарифм, как [21]
Мозер и Вайман (1955) установил расширение
равномерно для так как , куда и каждый и известные выражения в .[22]
Асимптотическое выражение
был создан де Брюйн (1981).
Белл простые числа
Гарднер (1978) поднял вопрос о том, являются ли бесконечно многие числа Белла простые числа. Первые несколько простых чисел Белла:
- 2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 (последовательность A051131 в OEIS )
соответствующие индексам 2, 3, 7, 13, 42 и 55 (последовательность A051130 в OEIS ).
Следующий Белл Прайм является B2841, что составляет примерно 9,30740105 × 106538.[23] По состоянию на 2018 год[Обновить], это наибольшее известное простое число Белла. Фил Кармоди показал, что это был вероятный прайм в 2002 году. После 17 месяцев вычислений с помощью метода Марселя Мартина ECPP программа Primo, Игнасио Ларроса Каньестро доказал, что это простое число в 2004 году. Он исключил любые другие возможные простые числа ниже B6000, позже расширенный до B30447 к Эрик Вайсштейн.[24]
История
Номера Bell названы в честь Эрик Темпл Белл, который писал о них в 1938 году, после работы 1934 года, в которой он изучал Полиномы Белла.[25][26] Белл не утверждал, что обнаружил эти числа; в своей статье 1938 года он писал, что числа Белла «часто исследовались» и «много раз открывались заново». Белл цитирует несколько более ранних публикаций по этим числам, начиная с Добиньский (1877) который дает Формула Добинского для чисел Белла. Белл назвал эти числа «экспоненциальными числами»; название «Белл-числа» и обозначения Bп за эти числа им дали Беккер и Риордан (1948).[27]
Первое исчерпывающее перечисление множества разделов, по-видимому, произошло в средневековой Японии, где (вдохновленные популярностью книги Сказка о Гэндзи ) салонная игра под названием Гэндзи-ко возникла, в которой гостям дали пять паковок благовоний, чтобы они понюхали, и их попросили угадать, какие из них такие же, а какие разные. 52 возможных решения, подсчитываемых числом Белла B5, были записаны 52 различными диаграммами, которые были напечатаны над заголовками глав в некоторых изданиях «Повести о Гэндзи».[28][29]
В Шриниваса Рамануджан Во второй записной книжке он исследовал как полиномы Белла, так и числа Белла.[30]Ранние ссылки на Треугольник колокола, на обеих сторонах которого есть числа Белла, включают Пирс (1880) и Эйткен (1933).
Смотрите также
Примечания
- ^ а б Гарднер 1978.
- ^ Уильямс 1945 приписывает это наблюдение Сильвио Минетоле Principii di Analisi Combinatoria (1909).
- ^ Клаэссон (2001).
- ^ Каллан (2006).
- ^ Слоан, Н. Дж. А. (ред.). «Последовательность A011971 (массив Эйткена)». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
- ^ Уилф 1994, п. 23.
- ^ Конвей и Гай (1996).
- ^ а б Флажолет и Седжвик 2009.
- ^ а б Рота 1964.
- ^ Уилф 1994, стр. 20-23.
- ^ а б Бендер и Уильямсон 2006.
- ^ Добинский 1877 г..
- ^ Беккер и Риордан (1948).
- ^ Херст и Шульц (2009).
- ^ Уильямс 1945.
- ^ Wagstaff 1996.
- ^ Саймон, Барри (2010). «Пример 15.4.6 (Асимптотика чисел Белла)». Комплексный анализ (PDF). С. 772–774. Архивировано из оригинал (PDF) на 2014-01-24. Получено 2012-09-02.
- ^ Энгель 1994.
- ^ Кэнфилд 1995.
- ^ Асаи, Кубо и Куо 2000.
- ^ Ловас (1993).
- ^ Кэнфилд, Род (июль 1994). "Разложение чисел Белла Мозера-Ваймана" (PDF). Получено 2013-10-24.
- ^ "93074010508593618333...83885253703080601131". 5000 наибольших известных простых чисел, основная база данных. Получено 2013-10-24.
- ^ Вайсштейн, Эрик В. «Простые числа целочисленных последовательностей». MathWorld.
- ^ Колокол 1934.
- ^ Колокол 1938.
- ^ Рота 1964. Однако Рота указывает неверную дату - 1934 год. Беккер и Риордан, 1948 г..
- ^ Кнут 2013.
- ^ Гарднер 1978 и Берндт 2011 также упомяните связь между числами Белла и Сказкой о Гэндзи, но менее подробно.
- ^ Берндт 2011.
Рекомендации
- Асаи, Нобухиро; Кубо, Идзуми; Куо, Хуэй-Сюн (2000). «Белловые числа, логарифмическая вогнутость и логарифмическая выпуклость». Acta Applicandae Mathematicae. 63 (1–3): 79–87. arXiv:математика / 0104137. Дои:10.1023 / А: 1010738827855. Г-Н 1831247.CS1 maint: ref = harv (ссылка на сайт)
- Эйткен, А.С. (1933). «Проблема в комбинациях». Математические заметки. 28: 18–23. Дои:10.1017 / S1757748900002334.CS1 maint: ref = harv (ссылка на сайт)
- Becker, H.W .; Риордан, Джон (1948). «Арифметика чисел Белла и Стирлинга». Американский журнал математики. 70: 385–394. Дои:10.2307/2372336. JSTOR 2372336.CS1 maint: ref = harv (ссылка на сайт).
- Белл, Э. Т. (1934). «Экспоненциальные многочлены». Анналы математики. 35: 258–277. Дои:10.2307/1968431. JSTOR 1968431.CS1 maint: ref = harv (ссылка на сайт).
- Белл, Э. Т. (1938). «Повторяющиеся экспоненциальные целые числа». Анналы математики. 39: 539–557. Дои:10.2307/1968633. JSTOR 1968633.CS1 maint: ref = harv (ссылка на сайт).
- Бендер, Эдвард А .; Уильямсон, С. Гилл (2006). «Пример 11.7, Установка разделов». Основы комбинаторики с приложениями (PDF). Дувр. С. 319–320. ISBN 0-486-44603-4.CS1 maint: ref = harv (ссылка на сайт)
- Berend, D .; Тасса, Т. (2010). «Улучшенные оценки чисел Белла и моментов сумм случайных величин». Вероятность и математическая статистика. 30 (2): 185–205.CS1 maint: ref = harv (ссылка на сайт)
- Берндт, Брюс С. (2011). «Рамануджан протягивает руку из могилы, чтобы вырвать у вас ваши теоремы» (PDF). Информационный бюллетень по математике в Азиатско-Тихоокеанском регионе. 1 (2): 8–13.CS1 maint: ref = harv (ссылка на сайт)
- де Брёйн, Н. (1981). Асимптотические методы в анализе (3-е изд.). Дувр. п. 108.CS1 maint: ref = harv (ссылка на сайт)
- Каллан, Дэвид (2006). «Комбинаторная интерпретация собственной последовательности для композиции». Журнал целочисленных последовательностей. 9 (1): 06.1.4. arXiv:математика / 0507169. Bibcode:2005математика ...... 7169C. Г-Н 2193154.CS1 maint: ref = harv (ссылка на сайт)
- Кэнфилд, Э. Родни (1995). «Неравенство Энгеля для чисел Белла». Журнал комбинаторной теории. Серия А. 72 (1): 184–187. Дои:10.1016/0097-3165(95)90033-0. Г-Н 1354972.CS1 maint: ref = harv (ссылка на сайт)
- Клаэссон, Андерс (2001). «Избегание генерализованного паттерна». Европейский журнал комбинаторики. 22 (7): 961–971. arXiv:математика / 0011235. Дои:10.1006 / eujc.2001.0515. Г-Н 1857258.CS1 maint: ref = harv (ссылка на сайт)
- Конвей, Джон Хортон; Гай, Ричард К. (1996). «Знаменитые семейства чисел: числа Белл и числа Стирлинга». Книга чисел. Серия Коперник. Springer. стр.91–94. ISBN 9780387979939.CS1 maint: ref = harv (ссылка на сайт)
- Добинский, Г. (1877). "Summirung der Reihe мех м = 1, 2, 3, 4, 5, …". Архив Грюнерта. 61: 333–336.CS1 maint: ref = harv (ссылка на сайт)
- Энгель, Конрад (1994). «О среднем ранге элемента в фильтре решетки разделов». Журнал комбинаторной теории. Серия А. 65 (1): 67–78. Дои:10.1016/0097-3165(94)90038-8. Г-Н 1255264.CS1 maint: ref = harv (ссылка на сайт)
- Флажоле, Филипп; Седжвик, Роберт (2009). «II.3 Сюрприз, разделы множества и слова». Аналитическая комбинаторика. Издательство Кембриджского университета. стр.106 –119.CS1 maint: ref = harv (ссылка на сайт)
- Гарднер, Мартин (1978). «Колокола: универсальные числа, которые могут считать части набора, простые числа и даже рифмы». Scientific American. 238: 24–30. Bibcode:1978SciAm.238e..24G. Дои:10.1038 / scientificamerican0578-24.CS1 maint: ref = harv (ссылка на сайт) Перепечатано с дополнением как «Звонкие храмовые колокола», глава 2 Фрактальная музыка, гиперкарты и многое другое ... Математические развлечения от Scientific American, W. H. Freeman, 1992, стр. 24–38.
- "Белл-числа", Энциклопедия математики, EMS Press, 2001 [1994]
- Херст, Грег; Шульц, Эндрю (2009). «Элементарное (теории чисел) доказательство сравнения Тушара». arXiv:0906.0696 [math.CO ].CS1 maint: ref = harv (ссылка на сайт)
- Кнут, Дональд Э. (2013). «Две тысячи лет комбинаторики». У Уилсона, Робина; Уоткинс, Джон Дж. (Ред.). Комбинаторика: древнее и современное. Издательство Оксфордского университета. С. 7–37.CS1 maint: ref = harv (ссылка на сайт)
- Ловас, Л. (1993). «Раздел 1.14, проблема 9». Комбинаторные задачи и упражнения (2-е изд.). Амстердам, Нидерланды: Северная Голландия. п. 17. Zbl 0785.05001.CS1 maint: ref = harv (ссылка на сайт)
- Мозер, Лев; Вайман, Макс (1955). «Асимптотическая формула для чисел Белла». Сделки Королевского общества Канады, Раздел III. 49: 49–54. Г-Н 0078489.CS1 maint: ref = harv (ссылка на сайт)
- Пирс, К.С. (1880). «Об алгебре логики». Американский журнал математики. 3 (1): 15–57. Дои:10.2307/2369442. JSTOR 2369442.CS1 maint: ref = harv (ссылка на сайт).
- Рота, Джан-Карло (1964), «Число перегородок в комплекте», Американский математический ежемесячный журнал, 71 (5): 498–504, Дои:10.2307/2312585, Г-Н 0161805CS1 maint: ref = harv (ссылка на сайт)
- Спайви, Майкл З. (2008). «Обобщенная повторяемость чисел Белла» (PDF). Журнал целочисленных последовательностей. 11 (2): Статья 08.2.5, 3. Г-Н 2420912.CS1 maint: ref = harv (ссылка на сайт)
- Вагстафф, Сэмюэл С. (1996). «Аурифейлевы факторизации и период чисел Белла по простому модулю». Математика вычислений. 65 (213): 383–391. Bibcode:1996MaCom..65..383 Вт. Дои:10.1090 / S0025-5718-96-00683-7. Г-Н 1325876.CS1 maint: ref = harv (ссылка на сайт)
- Уилф, Герберт С. (1994). Генерацияфункционологии (PDF) (2-е изд.). Бостон, Массачусетс: Academic Press. ISBN 0-12-751956-4. Zbl 0831.05001.CS1 maint: ref = harv (ссылка на сайт)
- Уильямс, Г. Т. (1945). "Числа, генерируемые функцией ееИкс − 1". Американский математический ежемесячный журнал. 52: 323–327. Дои:10.2307/2305292. JSTOR 2305292. Г-Н 0012612.CS1 maint: ref = harv (ссылка на сайт)
внешняя ссылка
- Роберт Дикау. «Диаграммы Белл-чисел».
- Вайсштейн, Эрик В. "Колокольный номер". MathWorld.
- Готфрид Хелмс. «Дополнительные свойства и обобщение номеров звонка» (PDF).