Номер звонка
В комбинаторной математике числа Белла подсчитывают возможные разделы множества . Эти числа изучаются математиками с XIX века, а их корни уходят в средневековую Японию. В качестве примера закона эпонимии Стиглера они названы в честь Эрика Темпла Белла , который писал о них в 1930-х годах.
Числа Белла обозначаются , где целое число, большее или равное нулю . Начиная с , первые несколько чисел Белла
Номер Белла подсчитывает различные способы разбиения множества, имеющего ровно элементы или, что то же самое, отношения эквивалентности на нем. также подсчитывает различные схемы рифм для -строчные стихи. [1]
Эти числа не только появляются в задачах подсчета, но и имеют другую интерпретацию как моменты вероятностных распределений . В частности, это -й момент распределения Пуассона со средним значением 1.
Подсчет [ править ]
Установить разделы [ править ]
В общем, количество разделов набора размером . Раздел набора определяется как семейство непустых попарно непересекающихся подмножеств чей союз . Например, потому что набор из трех элементов можно разделить на 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]
- Начните с номера один. Поместите это отдельно в ряд. ( )
- Начните новую строку с самого правого элемента предыдущей строки как самого левого числа ( где r — последний элемент ( i -1)-й строки)
- Определите числа, отсутствующие в левом столбце, взяв сумму числа слева и числа над числом слева, то есть числа по диагонали вверх и слева от числа, которое мы вычисляем.
- Повторяйте шаг 3, пока не появится новая строка, в которой на одно число больше, чем в предыдущей строке (выполняйте шаг 3, пока )
- Число в левой части данной строки — это номер Белла для этой строки. ( )
Вот первые пять рядов треугольника, построенного по этим правилам:
Числа Белла появляются как на левой, так и на правой сторонах треугольника.
Свойства [ править ]
Формулы суммирования [ править ]
Числа Белла удовлетворяют рекуррентному соотношению, включающему биномиальные коэффициенты : [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) .
См. также [ править ]
Примечания [ править ]
- ^ Jump up to: Перейти обратно: а б Гарднер 1978 .
- ^ Халмос, Пол Р. (1974). Наивная теория множеств . Тексты для бакалавриата по математике. Спрингер-Верлаг, Нью-Йорк-Гейдельберг. стр. 27–28. ISBN 9781475716450 . МР 0453532 .
- ^ Уильямс 1945 приписывает это наблюдение книге Сильвио Минетолы Principii di Analisi Combinatoria (1909).
- ^ Классон (2001) .
- ^ Каллан (2006) .
- ^ Слоан, Нью-Джерси (ред.). «Последовательность A011971 (массив Эйткена)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
- ^ Уилф 1994 , с. 23.
- ^ Конвей и Гай (1996) .
- ^ Jump up to: Перейти обратно: а б Комацу, Такао; Пита-Руис, Клаудио (2018). «Некоторые формулы для чисел Белла» . Филомат . 32 (11): 3881–3889. дои : 10.2298/FIL1811881K . ISSN 0354-5180 .
- ^ Jump up to: Перейти обратно: а б Флажоле и Седжвик, 2009 .
- ^ Jump up to: Перейти обратно: а б Лотерея 1964 года .
- ^ Уилф 1994 , стр. 20–23.
- ^ Jump up to: Перейти обратно: а б Бендер и Уильямсон 2006 .
- ^ Добинский 1877 .
- ^ Беккер и Риордан (1948) .
- ^ Херст и Шульц (2009) .
- ^ Уильямс 1945 .
- ^ Вагстафф 1996 .
- ^ Саймон, Барри (2010). «Пример 15.4.6 (Асимптотика чисел колокола)». Комплексный анализ (PDF) . стр. 772–774. Архивировано из оригинала (PDF) 24 января 2014 г. Проверено 2 сентября 2012 г.
- ^ Энгель 1994 .
- ^ Кэнфилд 1995 .
- ^ Асаи, Кубо и Куо 2000 .
- ^ Райдер (1993) .
- ^ Кэнфилд, Род (июль 1994 г.). «Разложение чисел Белла Мозера-Ваймана» (PDF) . Проверено 24 октября 2013 г.
- ^ Слоан, Нью-Джерси (ред.). «Последовательность A051131» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
- ^ Белл 1934 .
- ^ Белл 1938 .
- ^ Рота 1964 . Однако Рота указывает неверную дату - 1934 год - для Беккера и Риордана (1948 год) .
- ^ Кнут 2013 .
- ^ Гарднер 1978 и Берндт 2011 также менее подробно упоминают связь между числами Белла и «Повестью о Гэндзи».
- ^ Берндт 2011 .
Ссылки [ править ]
- Асаи, Нобухиро; Кубо, Изуми; Куо, Хуэй-Сюн (2000). «Числа колоколов, логарифмическая вогнутость и логарифмическая выпуклость». Acta Applicandae Mathematicae . 63 (1–3): 79–87. arXiv : math/0104137 . дои : 10.1023/A:1010738827855 . МР 1831247 . S2CID 16533831 .
- Эйткен, AC (1933). «Проблема в комбинациях» . Математические заметки . 28 : 18–23. дои : 10.1017/S1757748900002334 .
- Беккер, Х.В.; Риордан, Джон (1948). «Арифметика чисел Белла и Стирлинга». Американский журнал математики . 70 (2): 385–394. дои : 10.2307/2372336 . JSTOR 2372336 . .
- Белл, ET (1934). «Экспоненциальные полиномы». Анналы математики . 35 (2): 258–277. дои : 10.2307/1968431 . JSTOR 1968431 . .
- Белл, ET (1938). «Итерированные экспоненциальные целые числа». Анналы математики . 39 (3): 539–557. дои : 10.2307/1968633 . JSTOR 1968633 . .
- Бендер, Эдвард А.; Уильямсон, С. Гилл (2006). «Пример 11.7, Установка разделов». Основы комбинаторики с приложениями (PDF) . Дувр. стр. 319–320. ISBN 0-486-44603-4 .
- Беренд, Д.; Тасса, Т. (2010). «Улучшенные оценки чисел Белла и моментов сумм случайных величин». Вероятность и математическая статистика . 30 (2): 185–205.
- Берндт, Брюс К. (2011). «Рамануджан протягивает руку из могилы, чтобы вырвать у вас ваши теоремы» (PDF) . Информационный бюллетень по математике в Азиатско-Тихоокеанском регионе . 1 (2): 8–13.
- де Брейн, Н.Г. (1981). Асимптотические методы анализа (3-е изд.). Дувр. п. 108.
- Каллан, Дэвид (2006). «Комбинаторная интерпретация собственной последовательности композиции» . Журнал целочисленных последовательностей . 9 (1): 06.1.4. arXiv : math/0507169 . Бибкод : 2005math......7169C . МР 2193154 .
- Кэнфилд, Э. Родни (1995). «Неравенство Энгеля для чисел Белла» . Журнал комбинаторной теории . Серия А. 72 (1): 184–187. дои : 10.1016/0097-3165(95)90033-0 . МР 1354972 .
- Классон, Андерс (2001). «Обобщенное избегание шаблонов». Европейский журнал комбинаторики . 22 (7): 961–971. arXiv : math/0011235 . дои : 10.1006/eujc.2001.0515 . МР 1857258 .
- Конвей, Джон Хортон ; Гай, Ричард К. (1996). «Знаменитые семейства чисел: числа Белла и числа Стирлинга». Книга чисел . Серия «Коперник». Спрингер. стр. 91–94 . ISBN 9780387979939 .
- Добинский, Г. (1877). «Итогирование ряда для m = 1, 2, 3, 4, 5, ...» . Архив Грюнерта . 61 : 333–336.
- Энгель, Конрад (1994). «О среднем ранге элемента в фильтре решетки разделов». Журнал комбинаторной теории . Серия А. 65 (1): 67–78. дои : 10.1016/0097-3165(94)90038-8 . МР 1255264 .
- Флажоле, Филипп ; Седжвик, Роберт (2009). «II.3 Сюръекции, разбиения множеств и слова». Аналитическая комбинаторика . Издательство Кембриджского университета. стр. 106–119 .
- Гарднер, Мартин (1978). «Колокола: универсальные числа, которые могут считать части множества, простые числа и даже рифмы». Научный американец . 238 (5): 24–30. Бибкод : 1978SciAm.238e..24G . doi : 10.1038/scientificamerican0578-24 . Перепечатано с приложением под названием «Звенящие храмовые колокола», глава 2 книги « Фрактальная музыка, гиперкарты и многое другое… Математические развлечения из журнала Scientific American» , WH Freeman, 1992, стр. 24–38.
- «Колокольные номера» . Энциклопедия математики . ЭМС Пресс . 2001 [1994].
- Херст, Грег; Шульц, Эндрю (2009). «Элементарное (теория чисел) доказательство сравнения Тушара». arXiv : 0906.0696 [ math.CO ].
- Кнут, Дональд Э. (2013). «Две тысячи лет комбинаторики». В Уилсоне, Робин; Уоткинс, Джон Дж. (ред.). Комбинаторика: древняя и современная . Издательство Оксфордского университета. стр. 7–37.
- Ловас, Л. (1993). «Раздел 1.14, Задача 9». Комбинаторные задачи и упражнения (2-е изд.). Амстердам, Нидерланды: Северная Голландия. п. 17. ISBN 9780821869475 . Збл 0785.05001 .
- Мозер, Лео ; Вайман, Макс (1955). «Асимптотическая формула для чисел Белла». Труды Королевского общества Канады, Раздел III . 49 : 49–54. МР 0078489 .
- Пирс, CS (1880). «Об алгебре логики». Американский журнал математики . 3 (1): 15–57. дои : 10.2307/2369442 . JSTOR 2369442 . .
- Рота, Джан-Карло (1964). «Количество разделов набора». Американский математический ежемесячник . 71 (5): 498–504. дои : 10.2307/2312585 . JSTOR 2312585 . МР 0161805 .
- Спайви, Майкл З. (2008). «Обобщенная рекуррентность чисел Белла» (PDF) . Журнал целочисленных последовательностей . 11 (2): Статья 08.2.5, 3. Бибкод : 2008JIntS..11...25S . МР 2420912 .
- Вагстафф, Сэмюэл С. (1996). «Факторизации Орифейля и период чисел Белла по простому модулю» . Математика вычислений . 65 (213): 383–391. Бибкод : 1996MaCom..65..383W . дои : 10.1090/S0025-5718-96-00683-7 . МР 1325876 .
- Уилф, Герберт С. (1994). Генерирующая функционалология (PDF) (2-е изд.). Бостон, Массачусетс: Академическая пресса. ISBN 0-12-751956-4 . Збл 0831.05001 .
- Уильямс, GT (1945). «Числа, генерируемые функцией e и х − 1 ". American Mathematical Monthly . 52 : 323–327. doi : /2305292 . JSTOR 2305292. . MR 0012612 10.2307
Внешние ссылки [ править ]
- Роберт Дикау. «Диаграммы чисел Белла» .
- Вайсштейн, Эрик В. «Номер звонка» . Математический мир .
- Готфрид Хелмс. «Дополнительные свойства и обобщение номеров звонков» (PDF) .