Номер звонка

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

Числа Белла обозначаются , где целое число, большее или равное нулю . Начиная с , первые несколько чисел Белла

(последовательность A000110 в OEIS ).

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

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

Подсчет [ править ]

Установить разделы [ править ]

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

В общем, количество разделов набора размером . Раздел набора определяется как семейство непустых попарно непересекающихся подмножеств чей союз . Например, потому что набор из трех элементов можно разделить на 5 различных способов:

Как следует из приведенного выше обозначения множества, порядок подмножеств внутри семейства не учитывается; упорядоченные разделы подсчитываются по другой последовательности чисел — упорядоченным числам Белла . равно 1, поскольку существует ровно один раздел пустого множества . Этот раздел сам по себе является пустым набором; его можно интерпретировать как семейство подмножеств пустого множества, состоящее из нулевых подмножеств. Совершенно неверно , что все подмножества в этом семействе являются непустыми подмножествами пустого множества и что они являются попарно непересекающимися подмножествами пустого множества, потому что не существует подмножеств, обладающих этими маловероятными свойствами.

Разбиения множества взаимно однозначно соответствуют его отношениям эквивалентности . Это бинарные отношения , которые являются рефлексивными , симметричными и транзитивными . Отношение эквивалентности, соответствующее разделу, определяет два элемента как эквивалентные, если они принадлежат к одному и тому же подмножеству раздела, что и друг друга. И наоборот, каждое отношение эквивалентности соответствует разбиению на классы эквивалентности . [2] Следовательно, числа Белла также учитывают отношения эквивалентности.

Факторизации [ править ]

Если число без квадратов положительное целое число , что означает, что оно является произведением некоторого числа различных простых чисел , то дает количество различных мультипликативных разбиений . Это факторизации на числа больше единицы, рассматривая две факторизации как одинаковые, если они имеют одни и те же факторы в разном порядке. [3] Например, 30 является произведением трёх простых чисел 2, 3 и 5 и имеет = 5 факторизаций:

Схемы рифм [ править ]

Числа Белла также учитывают схемы рифм стихотворения n - строчного или строфы . Схема рифм описывает, какие строки рифмуются друг с другом, и поэтому ее можно интерпретировать как разделение набора строк на рифмующиеся подмножества. Схемы рифм обычно записываются как последовательность латинских букв, по одной в строке, причем строки рифмования имеют одинаковые буквы, а первые строки в каждом наборе рифм помечены в алфавитном порядке. Таким образом, 15 возможных схем четырехстрочных рифм — это AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC и ABCD. [1]

Перестановки [ править ]

Числа Белла возникают в задаче о перетасовке карт , упомянутой в приложении к Гарднеру (1978) . Если колоду из n карт перетасовать путем многократного удаления верхней карты и повторной вставки ее в любое место колоды (в том числе в исходное положение наверху колоды), ровно n повторений этой операции, то существует n н различные перетасовки, которые можно выполнить. Из них число, которое возвращает колоду в исходный отсортированный порядок, равно B n . Таким образом, вероятность того, что колода после такого перетасовывания окажется в исходном порядке, равна B n / n. н , что значительно больше, чем 1/ n ! вероятность, которая описывала бы равномерно случайную перестановку колоды.

С перетасовкой карт связано несколько других проблем подсчета особых видов перестановок , на которые также можно ответить с помощью чисел Белла. Например, n- е число Белла равно количеству перестановок n элементов, в которых никакие три значения, отсортированные в порядке, не имеют последних двух из этих трех последовательных значений. В обозначениях обобщенных шаблонов перестановок , где значения, которые должны быть последовательными, пишутся рядом друг с другом, а значения, которые могут появляться непоследовательно, разделяются тире, эти перестановки можно описать как перестановки, избегающие шаблона 1–23. Перестановки, избегающие обобщенных шаблонов 12-3, 32-1, 3-21, 1-32, 3-12, 21-3 и 23-1, также учитываются числами Белла. [4] Перестановки, в которых каждый шаблон 321 (без ограничения на последовательные значения) может быть расширен до шаблона 3241, также учитываются числами Белла. [5] Однако числа Белла растут слишком быстро, чтобы подсчитать перестановки, которые избегают закономерности, которая не была обобщена таким образом: согласно (теперь доказанной) гипотезе Стэнли – Уилфа число таких перестановок является одноэкспоненциальным, а числа Белла имеют более высокая асимптотическая скорость роста, чем эта.

Схема треугольника для расчетов [ править ]

Треугольный массив, правая диагональная последовательность которого состоит из чисел Белла.

Числа Белла можно легко вычислить, создав так называемый треугольник Белла , также называемый массивом Эйткена или треугольником Пирса в честь Александра Эйткена и Чарльза Сандерса Пирса . [6]

  1. Начните с номера один. Поместите это отдельно в ряд. ( )
  2. Начните новую строку с самого правого элемента предыдущей строки как самого левого числа ( где r — последний элемент ( i -1)-й строки)
  3. Определите числа, отсутствующие в левом столбце, взяв сумму числа слева и числа над числом слева, то есть числа по диагонали вверх и слева от числа, которое мы вычисляем.
  4. Повторяйте шаг 3, пока не появится новая строка, в которой на одно число больше, чем в предыдущей строке (выполняйте шаг 3, пока )
  5. Число в левой части данной строки — это номер Белла для этой строки. ( )

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

Числа Белла появляются как на левой, так и на правой сторонах треугольника.

Свойства [ править ]

Формулы суммирования [ править ]

Числа Белла удовлетворяют рекуррентному соотношению, включающему биномиальные коэффициенты : [7]

Это можно объяснить, заметив, что из произвольного раздела из n + 1 элементов удаление набора, содержащего первый элемент, оставляет раздел меньшего набора из k элементов для некоторого числа k , которое может находиться в диапазоне от 0 до n . Есть выбор k элементов, которые остаются после удаления одного набора, и B k вариантов их разделения.

Другая формула суммирования представляет каждое число Белла как сумму чисел Стирлинга второго рода.

Число Стирлинга — это количество способов разбить множество мощности n ровно на k непустые подмножества. Таким образом, в уравнении, связывающем числа Белла с числами Стирлинга, каждое разбиение, подсчитанное в левой части уравнения, учитывается ровно в одном из членов суммы в правой части, том, для которого k является числом наборов в разделе. [8]

Спиви (2008) дал формулу, объединяющую оба этих суммирования:

Применяя формулу обращения Паскаля к рекуррентному соотношению, получаем

которые можно обобщить следующим образом: [9]

Другие формулы конечных сумм, использующие числа Стирлинга первого рода, включают [9]

что упрощается с к

и с , к

которую можно рассматривать как формулу обращения чисел Стирлинга, примененную к формуле Спайви.

Генерирующая функция [ править ]

Экспоненциальная производящая функция чисел Белла равна

В этой формуле суммирование в середине — это общая форма, используемая для определения экспоненциальной производящей функции для любой последовательности чисел, а формула справа — это результат суммирования в конкретном случае чисел Белла.

Один из способов получения этого результата использует аналитическую комбинаторику — стиль математических рассуждений, в котором наборы математических объектов описываются формулами, объясняющими их конструкцию из более простых объектов, а затем этими формулами манипулируют для получения комбинаторных свойств объектов. На языке аналитической комбинаторики разбиение множества можно описать как множество непустых урн, в которых элементы, помеченные от 1 до n распределены , а комбинаторный класс всех разбиений (для всех n ) можно выразить обозначением

Здесь, — это комбинаторный класс, содержащий только один элемент размера один, элемент, который можно поместить в урну. Внутренний Оператор описывает набор или урну, содержащую один или несколько помеченных элементов, а внешний описывает общий раздел как набор этих урн. Затем экспоненциальную производящую функцию можно прочитать из этого обозначения, переведя оператор в показательную функцию, а ограничение непустоты ≥1 в вычитание на единицу. [10]

Альтернативный метод получения той же производящей функции использует рекуррентное соотношение для чисел Белла в терминах биномиальных коэффициентов, чтобы показать, что экспоненциальная производящая функция удовлетворяет дифференциальному уравнению . Саму функцию можно найти, решив это уравнение. [11] [12] [13]

Моменты вероятностных распределений

Числа Белла удовлетворяют формуле Добински. [14] [11] [13]

Эту формулу можно вывести путем расширения экспоненциальной производящей функции с использованием ряда Тейлора для экспоненциальной функции, а затем сбора членов с тем же показателем степени. [10] Это позволяет B n интерпретировать как n- й момент с распределения Пуассона ожидаемым значением 1.

е n- число Белла также является суммой коэффициентов n -го полного полинома Белла , который выражает n момент любого распределения вероятностей как функцию первых n кумулянтов .

Модульная арифметика [ править ]

Числа Белла подчиняются сравнению Тушара : если p — любое простое число , то [15]

или, обобщая [16]

Из-за сравнения Тушара числа Белла являются периодическими по модулю p для каждого простого числа p ; например, для p = 2 числа Белла повторяют закономерность нечет-нечет-чет с периодом три. Период этого повторения для произвольного простого числа p должен быть делителем

и для всех премьер и , или это именно этот номер (последовательность A001039 в OEIS ). [17] [18]

Период чисел Белла по модулю n равен

1, 3, 13, 12, 781, 39, 137257, 24, 39, 2343, 28531167061, 156, 25239592216021, 411771, 10153, 48, 51702516367896047761, 39 , 109912203092239643840221, 9372, 1784341, 85593501183, 949112181811268728834319677753, 312, 3905, 75718776648063, 117, 1647084, 91703076898614683377208150526107718802981, 30459, 568972471024107865287021434301977158534824 481, 96, 370905171793, 155107549103688143283, 107197717, 156, ... (последовательность A054767 в OEIS )

Интегральное представление [ править ]

Применение интегральной формулы Коши к экспоненциальной производящей функции дает комплексное интегральное представление

Некоторые асимптотические представления затем могут быть получены стандартным применением метода наискорейшего спуска . [19]

Бревно-вогнутость [ править ]

Числа Белла образуют логарифмически выпуклую последовательность . Разделив их на факториалы B n / n !, получим логарифмически вогнутую последовательность. [20] [21] [22]

Темпы роста [ править ]

несколько асимптотических Известно формул для чисел Белла. В Berend & Tassa (2010) были установлены следующие границы:

для всех положительных целых чисел ;

более того, если тогда для всех ,

где и Числа Белла также можно аппроксимировать с помощью функции Ламберта W , функции с той же скоростью роста, что и логарифм, как [23]

Мозер и Вайман (1955) установили расширение

равномерно для как , где и каждый и являются известными выражениями в . [24]

Асимптотическое выражение

была основана де Брюйном (1981) .

Простые числа Белла [ править ]

Гарднер (1978) поднял вопрос о том, являются ли бесконечно многие числа Белла простыми числами . Они называются простыми числами Белла . Первые несколько простых чисел Белла:

2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 (последовательность A05 1131 в ОЭИС )

соответствующие индексам 2, 3, 7, 13, 42 и 55 (последовательность A051130 в OEIS ). Следующее простое число Белла B 2841 , что примерно равно 9,30740105 × 10. 6538 . [25]

История [ править ]

Числа Белла названы в честь Эрика Темпла Белла , который написал о них в 1938 году, в продолжение статьи 1934 года, в которой он изучал полиномы Белла . [26] [27] Белл не утверждал, что открыл эти числа; в своей статье 1938 года он написал, что числа Белла «часто исследовались» и «много раз открывались заново». Белл цитирует несколько более ранних публикаций об этих числах, начиная с Добиньского (1877) , в котором приводится формула Добиньского для чисел Белла. Белл назвал эти числа «экспоненциальными числами»; название «числа Белла» и обозначение B n для этих чисел были даны им Беккером и Риорданом (1948) . [28]

Первое исчерпывающее перечисление наборов, по-видимому, произошло в средневековой Японии, где (вдохновленная популярностью книги «Сказка о Гэндзи салонная игра под названием «Гэндзи-ко» ») возникла .в котором гостям давали понюхать пять пачек благовоний и просили угадать, какие из них похожи друг на друга, а какие отличаются. 52 возможных решения, подсчитанные по числу колокола B 5 , были записаны с помощью 52 различных диаграмм, которые были напечатаны над заголовками глав в некоторых изданиях «Повести о Гэндзи». [29] [30]

Во Шриниваса Рамануджан исследовал как полиномы Белла, так и числа Белла. второй тетради [31] Ранние упоминания о треугольнике Белла , на обеих сторонах которого есть числа Белла, включают Пирса (1880) и Эйткена (1933) .

См. также [ править ]

Примечания [ править ]

  1. ^ Jump up to: Перейти обратно: а б Гарднер 1978 .
  2. ^ Халмос, Пол Р. (1974). Наивная теория множеств . Тексты для бакалавриата по математике. Спрингер-Верлаг, Нью-Йорк-Гейдельберг. стр. 27–28. ISBN  9781475716450 . МР   0453532 .
  3. ^ Уильямс 1945 приписывает это наблюдение книге Сильвио Минетолы Principii di Analisi Combinatoria (1909).
  4. ^ Классон (2001) .
  5. ^ Каллан (2006) .
  6. ^ Слоан, Нью-Джерси (ред.). «Последовательность A011971 (массив Эйткена)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
  7. ^ Уилф 1994 , с. 23.
  8. ^ Конвей и Гай (1996) .
  9. ^ Jump up to: Перейти обратно: а б Комацу, Такао; Пита-Руис, Клаудио (2018). «Некоторые формулы для чисел Белла» . Филомат . 32 (11): 3881–3889. дои : 10.2298/FIL1811881K . ISSN   0354-5180 .
  10. ^ Jump up to: Перейти обратно: а б Флажоле и Седжвик, 2009 .
  11. ^ Jump up to: Перейти обратно: а б Лотерея 1964 года .
  12. ^ Уилф 1994 , стр. 20–23.
  13. ^ Jump up to: Перейти обратно: а б Бендер и Уильямсон 2006 .
  14. ^ Добинский 1877 .
  15. ^ Беккер и Риордан (1948) .
  16. ^ Херст и Шульц (2009) .
  17. ^ Уильямс 1945 .
  18. ^ Вагстафф 1996 .
  19. ^ Саймон, Барри (2010). «Пример 15.4.6 (Асимптотика чисел колокола)». Комплексный анализ (PDF) . стр. 772–774. Архивировано из оригинала (PDF) 24 января 2014 г. Проверено 2 сентября 2012 г.
  20. ^ Энгель 1994 .
  21. ^ Кэнфилд 1995 .
  22. ^ Асаи, Кубо и Куо 2000 .
  23. ^ Райдер (1993) .
  24. ^ Кэнфилд, Род (июль 1994 г.). «Разложение чисел Белла Мозера-Ваймана» (PDF) . Проверено 24 октября 2013 г.
  25. ^ Слоан, Нью-Джерси (ред.). «Последовательность A051131» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
  26. ^ Белл 1934 .
  27. ^ Белл 1938 .
  28. ^ Рота 1964 . Однако Рота указывает неверную дату - 1934 год - для Беккера и Риордана (1948 год) .
  29. ^ Кнут 2013 .
  30. ^ Гарднер 1978 и Берндт 2011 также менее подробно упоминают связь между числами Белла и «Повестью о Гэндзи».
  31. ^ Берндт 2011 .

Ссылки [ править ]

Внешние ссылки [ править ]