Номер звонка - Bell number

В комбинаторная математика, то Номера звонков посчитать возможное перегородки набора. Эти числа изучаются математиками с XIX века, и их корни уходят в средневековую Японию. В примере Закон Стиглера эпонимии, они названы в честь Эрик Темпл Белл, писавший о них в 1930-е гг.

Числа Белла обозначены Bп, куда п является целое число больше или равно нуль. Начиная с B0 = B1 = 1, первые несколько чисел Белла

1, 1, 2, 5, 15, 52, 203, 877, 4140, ... (последовательность A000110 в OEIS ).

Номер звонка Bп подсчитывает количество различных способов разбиения набора, в котором ровно п элементов, или, что то же самое, количество отношения эквивалентности в теме. Bп также подсчитывает количество различных схемы рифм за пстихотворения.[1]

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

Подсчет

Установить перегородки

Разделы наборов могут быть расположены в частичном порядке, показывая, что каждый раздел набора размера n "использует" один из разделов набора размера n-1.
52 перегородки набора из 5 элементов

В целом, 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. Начните с номера один. Выложите это в ряд отдельно. ()
  2. Начните новую строку с самого правого элемента из предыдущей строки как крайнего левого числа ( куда р последний элемент (я-1) -й ряд)
  3. Определите числа не в левом столбце, взяв сумму числа слева и числа над числом слева, то есть числа по диагонали вверх и влево от числа, которое мы вычисляем.
  4. Повторяйте шаг 3 до тех пор, пока не появится новая строка с числом больше, чем в предыдущей строке (выполняйте шаг 3, пока )
  5. Число в левой части данной строки - это Номер звонка для этой строки. ()

Вот первые пять рядов треугольника, построенного по этим правилам:

 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).

Смотрите также

Примечания

  1. ^ а б Гарднер 1978.
  2. ^ Уильямс 1945 приписывает это наблюдение Сильвио Минетоле Principii di Analisi Combinatoria (1909).
  3. ^ Клаэссон (2001).
  4. ^ Каллан (2006).
  5. ^ Слоан, Н. Дж. А. (ред.). «Последовательность A011971 (массив Эйткена)». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
  6. ^ Уилф 1994, п. 23.
  7. ^ Конвей и Гай (1996).
  8. ^ а б Флажолет и Седжвик 2009.
  9. ^ а б Рота 1964.
  10. ^ Уилф 1994, стр. 20-23.
  11. ^ а б Бендер и Уильямсон 2006.
  12. ^ Добинский 1877 г..
  13. ^ Беккер и Риордан (1948).
  14. ^ Херст и Шульц (2009).
  15. ^ Уильямс 1945.
  16. ^ Wagstaff 1996.
  17. ^ Саймон, Барри (2010). «Пример 15.4.6 (Асимптотика чисел Белла)». Комплексный анализ (PDF). С. 772–774. Архивировано из оригинал (PDF) на 2014-01-24. Получено 2012-09-02.
  18. ^ Энгель 1994.
  19. ^ Кэнфилд 1995.
  20. ^ Асаи, Кубо и Куо 2000.
  21. ^ Ловас (1993).
  22. ^ Кэнфилд, Род (июль 1994). "Разложение чисел Белла Мозера-Ваймана" (PDF). Получено 2013-10-24.
  23. ^ "93074010508593618333...83885253703080601131". 5000 наибольших известных простых чисел, основная база данных. Получено 2013-10-24.
  24. ^ Вайсштейн, Эрик В. «Простые числа целочисленных последовательностей». MathWorld.
  25. ^ Колокол 1934.
  26. ^ Колокол 1938.
  27. ^ Рота 1964. Однако Рота указывает неверную дату - 1934 год. Беккер и Риордан, 1948 г..
  28. ^ Кнут 2013.
  29. ^ Гарднер 1978 и Берндт 2011 также упомяните связь между числами Белла и Сказкой о Гэндзи, но менее подробно.
  30. ^ Берндт 2011.

Рекомендации

внешняя ссылка