Номер звонка

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

Числа Белла обозначаются B _n , где n - целое число, большее или равное нулю . Начиная с B ₀ = B ₁ = 1, первые несколько номеров Белла

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

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

А также появляется в задачах подсчета, эти числа имеют различную интерпретацию, а моменты из вероятностных распределений . В частности, B _n - это n- й момент распределения Пуассона со средним значением 1.

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

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

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

52 перегородки набора из 5 элементов

В общем, B _n - это количество разделов набора размера n . Разбиение множества S определяется как совокупность непустых, попарно непересекающихся подмножеств S , объединение которых S . Например, B ₃  = 5, потому что 3-элементный набор { a ,  b ,  c } может быть разделен 5 различными способами:

{{ a }, { b }, { c }}

{{ а }, { б , в }}

{{ b }, { a , c }}

{{ c }, { a , b }}

{{ а , б , в }}.

B ₀ равен 1, потому что есть ровно одно разделение пустого набора . Каждый член пустого множества - это непустое множество (что пусто верно ), а их объединение - это пустое множество. Следовательно, пустой набор - это единственное само по себе разделение. В соответствии с указанными выше обозначениями, мы не рассматриваем ни порядок блоков в разделе, ни порядок элементов в каждом блоке. Это означает, что следующие разделы считаются идентичными:

{{ b }, { a , c }}

{{ а , в }, { б }}

{{ b }, { c , a }}

{{ c , a }, { b }}.

Если вместо этого различные упорядочения наборов считаются разными разделами, то количество этих упорядоченных разделов задается упорядоченными числами Белла .

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

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

${\ Displaystyle 30 = 2 \ раз 15 = 3 \ раз 10 = 5 \ раз 6 = 2 \ раз 3 \ раз 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, также считаются числами Белла.^[3] Перестановки, в которых каждый шаблон 321 (без ограничения на последовательные значения) может быть расширен до шаблона 3241, также учитываются числами Белла. ^[4] Однако числа Белла растут слишком быстро, чтобы подсчитать перестановки, которые избегают паттерна, который не был обобщен таким образом: согласно (теперь доказанной) гипотезе Стэнли-Уилфа , количество таких перестановок является однократно экспоненциальным, а Числа Белла имеют более высокую скорость асимптотического роста, чем это.

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

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

1. Начните с номера один. Выложите это в ряд отдельно. ( )${\ displaystyle x_ {0,1} = 1}$
2. Начните новую строку с самого правого элемента из предыдущей строки как крайнего левого числа ( где r - последний элемент ( i -1) -й строки)${\ Displaystyle х_ {я, 1} \ leftarrow х_ {я-1, г}}$
3. Определите числа не в левом столбце, взяв сумму числа слева и числа над числом слева, то есть числа по диагонали вверх и влево от числа, которое мы вычисляем. ${\ displaystyle (x_ {i, j} \ leftarrow x_ {i, j-1} + x_ {i-1, j-1})}$
4. Повторяйте шаг три до тех пор, пока не появится новая строка с числом больше, чем в предыдущей строке (выполните шаг 3 до тех пор, пока )${\ displaystyle j = r + 1}$
5. Число в левой части данной строки - это номер звонка для этой строки. ( )${\ Displaystyle B_ {я} \ leftarrow x_ {я, 1}}$

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

 1 1 2 2 3 5 5 7 10 1515 20 27 37 52

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

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

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

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

${\ displaystyle B_ {n + 1} = \ sum _ {k = 0} ^ {n} {\ binom {n} {k}} B_ {k}.}$

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

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

${\ displaystyle B_ {n} = \ sum _ {k = 0} ^ {n} \ left \ {{n \ atop k} \ right \}.}$

Число Стирлинга - это количество способов разбить набор мощности n ровно на k непустых подмножеств. Таким образом, в уравнении, связывающем числа Белла с числами Стирлинга, каждое разбиение, подсчитанное в левой части уравнения, учитывается ровно в одном из членов суммы в правой части, для которой k является числом наборов в перегородке. ^[7]${\ Displaystyle \ влево \ {{п \ на вершине к} \ вправо \}}$

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

${\ displaystyle B_ {n + m} = \ sum _ {k = 0} ^ {n} \ sum _ {j = 0} ^ {m} \ left \ {{m \ atop j} \ right \} {n \ choose k} j ^ {nk} B_ {k}.}$

Функция генерации [ править ]

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

${\displaystyle B(x)=\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}=e^{e^{x}-1}.}$

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

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

${\displaystyle \mathrm {S\scriptstyle ET} (\mathrm {S\scriptstyle ET} _{\geq 1}({\mathcal {Z}})).}$

Вот комбинаторный класс, содержащий только один член первого размера, элемент, который можно поместить в урну. Внутренний оператор описывает набор или урну, которая содержит один или несколько помеченных элементов, а внешний описывает весь раздел как набор этих урн. Затем экспоненциальную производящую функцию можно считать из этой записи, переведя оператор в экспоненциальную функцию, а ограничение непустоты ≥1 - в вычитание на единицу. ^[8]${\displaystyle {\mathcal {Z}}}$${\displaystyle \mathrm {S\scriptstyle ET} _{\geq 1}}$${\displaystyle \mathrm {S\scriptstyle ET} }$${\displaystyle \mathrm {S\scriptstyle ET} }$

Альтернативный метод получения той же производящей функции использует рекуррентное соотношение для чисел Белла в терминах биномиальных коэффициентов, чтобы показать, что экспоненциальная производящая функция удовлетворяет дифференциальному уравнению . Саму функцию можно найти, решив это уравнение. ^{[9] [10] [11]}${\displaystyle B'(x)=e^{x}B(x)}$

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

Числа Белла удовлетворяют формуле Добинского ^{[12] [9] [11]}

${\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}.}$

Эта формула может быть получена путем расширения экспоненциальной производящей функции с использованием ряда Тейлора для экспоненциальной функции и последующего сбора членов с тем же показателем. ^[8] Это позволяет В _п следует интерпретировать как п - й момент в виде распределения Пуассона с ожидаемым значением 1.

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

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

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

${\displaystyle B_{p+n}\equiv B_{n}+B_{n+1}{\pmod {p}}}$

или, обобщая ^[14]

${\displaystyle B_{p^{m}+n}\equiv mB_{n}+B_{n+1}{\pmod {p}}.}$

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

${\displaystyle {\frac {p^{p}-1}{p-1}}}$

и для всех простых чисел p ≤ 101 и p = 113, 163, 167 или 173 это именно то число (последовательность A001039 в OEIS ). ^{[15] [16]}

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

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, 156, ... (последовательность A054767 в OEIS )

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

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

${\displaystyle B_{n}={\frac {n!}{2\pi ie}}\int _{\gamma }{\frac {e^{e^{z}}}{z^{n+1}}}\,dz.}$

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

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

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

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

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

${\displaystyle B_{n}<\left({\frac {0.792n}{\ln(n+1)}}\right)^{n}}$для всех натуральных чисел ;${\displaystyle n}$

кроме того, если тогда для всех ,${\displaystyle \varepsilon >0}$${\displaystyle n>n_{0}(\varepsilon )}$

${\displaystyle B_{n}<\left({\frac {e^{-0.6+\varepsilon }n}{\ln(n+1)}}\right)^{n}}$

где и . Числа Белла также могут быть аппроксимированы с использованием функции Ламберта W , функции с той же скоростью роста, что и логарифм, как ^[21]${\displaystyle ~n_{0}(\varepsilon )=\max \left\{e^{4},d^{-1}(\varepsilon )\right\}~}$${\displaystyle ~d(x):=\ln \ln(x+1)-\ln \ln x+{\frac {1+e^{-1}}{\ln x}}\,.}$

${\displaystyle B_{n}\sim {\frac {1}{\sqrt {n}}}\left({\frac {n}{W(n)}}\right)^{n+{\frac {1}{2}}}\exp \left({\frac {n}{W(n)}}-n-1\right).}$

Moser & Wyman (1955) установили расширение

${\displaystyle B_{n+h}={\frac {(n+h)!}{W(n)^{n+h}}}\times {\frac {\exp(e^{W(n)}-1)}{(2\pi B)^{1/2}}}\times \left(1+{\frac {P_{0}+hP_{1}+h^{2}P_{2}}{e^{W(n)}}}+{\frac {Q_{0}+hQ_{1}+h^{2}Q_{2}+h^{3}Q_{3}+h^{4}Q_{4}}{e^{2W(n)}}}+O(e^{-3W(n)})\right)}$

равномерно для as , where и each и являются известными выражениями в . ^[22]${\displaystyle h=O(\ln(n))}$${\displaystyle n\rightarrow \infty }$${\displaystyle B}$${\displaystyle P_{i}}$${\displaystyle Q_{i}}$${\displaystyle W(n)}$

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

${\displaystyle {\begin{aligned}{\frac {\ln B_{n}}{n}}&=\ln n-\ln \ln n-1+{\frac {\ln \ln n}{\ln n}}+{\frac {1}{\ln n}}+{\frac {1}{2}}\left({\frac {\ln \ln n}{\ln n}}\right)^{2}+O\left({\frac {\ln \ln n}{(\ln n)^{2}}}\right)\\&{}\qquad {\text{as }}n\to \infty \end{aligned}}}$

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

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

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

2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 (последовательность A051131 в OEIS )

соответствующие индексам 2, 3, 7, 13, 42 и 55 (последовательность A051130 в OEIS ).

Следующее простое число Белла - B ₂₈₄₁ , что примерно равно 9,30740105 × 10 ⁶⁵³⁸ . ^[23] По состоянию на 2018 год ^[update]это наибольшее известное простое число Белла. Фил Кармоди показал, что это вероятное простое число в 2002 году. После 17 месяцев вычислений с помощью программы Марселя Мартина ECPP Primo, Игнасио Ларроса Каньестро доказал, что оно является простым в 2004 году. Он исключил любые другие возможные простые числа ниже B ₆₀₀₀ , позже расширенные до B _30447. от Eric Weisstein . ^[24]

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

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

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

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

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

• Полиномы Тушара
• Каталонский номер

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

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

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

• Роберт Дикау. «Диаграммы чисел Белла» .
• Вайсштейн, Эрик В. «Белл-число» . MathWorld .
• Готфрид Хелмс. «Другие свойства и обобщение номеров звонка» (PDF) .