Числа Белла — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Получение с помощью чисел Стирлинга второго рода)
м (rollbackEdits.php mass rollback)
 
(не показано 78 промежуточных версий 9 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition = В комбинаторной математике '''числа Белла''' (''англ. Bell's numbers'') показывают количество возможных способов разбиения множества из ''n'' элементов на непустые подмножества.  
+
|definition = В комбинаторной математике '''числа Белла''' (''англ. Bell's numbers'') определяют количество возможных способов [[Комбинаторные объекты#Разбиение на подмножества|разбиения множества]] из <tex>n</tex> элементов на подмножества.  
 
}}
 
}}
 
Числа Белла начинаются с  <tex dpi="130">B_0=B_1=1</tex> и образуют последовательность:
 
Числа Белла начинаются с  <tex dpi="130">B_0=B_1=1</tex> и образуют последовательность:
 
:<tex dpi="130">1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437,  
 
:<tex dpi="130">1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437,  
\newline{} 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, ... </tex>
+
190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057\dots
<tex dpi="130">n</tex>- элемент чисел Белла, <tex dpi="130">B_n</tex>, показывает количество различных способов разбиения множества, то есть. количество [[Отношение эквивалентности|отношений эквивалентности]] в нем.
+
</tex>
Вне математики, похожие числа показывают количество различных схем рифмовки для <tex dpi="130">n</tex>-й строфы стихотворения. Эти числа изучались математиками с 17-го века, их корни уходят в средневековую Японию. Названы в честь Эрика Темпла Белла, который описал их в 1930-х годах.  
+
<tex dpi="130">n</tex>-й элемент множества чисел Белла, <tex dpi="130">B_n</tex>, определяет количество различных способов разбиения множества, то есть количество [[Отношение эквивалентности|отношений эквивалентности]] в нем.
 
==Подсчет==
 
==Подсчет==
Разбиения множеств могут быть расположены частично-упорядоченном виде. Каждое подмножество длины <tex dpi="130">n</tex> использует одно из подмножеств длины <tex dpi="130">n-1</tex>.
 
 
[[File:XxxCircles.png|400px|thumb|upright|52 разбиения множества из 5 элементов]]
 
[[File:XxxCircles.png|400px|thumb|upright|52 разбиения множества из 5 элементов]]
[[File:Order.png|400px|border|Разбиения множеств могут быть расположены частично-упорядоченном виде. Каждое подмножество длины n использует одно из подмножеств длины <tex dpi="130">n-1</tex>.]]
+
[[File:Order.png|400px|border]]
  
<tex dpi="130">B_n</tex> количество разбиений множества размера <tex dpi="130">n</tex>. Разбиение множества <tex dpi="130">S</tex> определяется как совокупность '''непустых, попарно непересекающихся подмножеств множества''' <tex dpi="130">S</tex>. Например, <tex>B_3 = 5</tex>, потому что множество, состоящее их <tex>3</tex> элементов  {''a'',&nbsp;''b'',&nbsp;''c''} может быть разделено <tex>5</tex> различным способами:
+
Разбиение множества <tex dpi="130">S</tex> определяется как совокупность '''попарно непересекающихся подмножеств множества''' <tex dpi="130">S</tex>. Например, <tex>B_3 = 5</tex>, потому что множество, состоящее их <tex>3</tex> элементов   <tex> \{ a, b , c \} </tex> может быть разделено <tex>5</tex> различными способами:
 +
 
 +
:<tex>  \{ a \} , \{ b \} , \{ c \} </tex>
 +
: <tex>  \{ a \} , \{b, c \} </tex>
 +
: <tex> \{ b \} , \{a, c \} </tex>
 +
: <tex> \{ c \} , \{ a, b \} </tex>
 +
: <tex> \{ a, b , c \} </tex>
 +
 
 +
<tex dpi="130">B_0 = 1</tex>, т.к. существует только одно возможное разбиение пустого множества. Пустое множество может разбиваться только на само себя.
 +
Как было обозначено выше, мы  '''не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них'''. Это означает, что данные разбиения являются идентичными:
 +
: <tex> \{ b \} , \{ a , c \} </tex>
 +
: <tex>\{ a, c\}, \{ b \} </tex>
 +
: <tex>\{ b \}, \{ c, a \} </tex>
 +
: <tex>\{ c, a \}, \{ b \} </tex>
  
: {''a''}, {''b''}, {''c''}
 
: {''a''}, {''b'', ''c''}
 
: {''b''}, {''a'', ''c''}
 
: {''c''}, {''a'', ''b''}
 
: {''a'', ''b'', ''c''}.
 
  
<tex dpi="130">B_0</tex> является <tex>1</tex>, т.к. существует только одно возможное разбиение пустого множества. Каждый элемент пустого множества является непустым множеством и их объединение является пустым множеством. Таким образом, пустое множество может разбиваться только на само себя.
 
Как было обозначено выше, мы  '''не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них '''. Это означает, что данные разбиения являются идентичными:
 
:{''b''}, {''a'', ''c''}
 
:{''a'', ''c''}, {''b''}
 
:{''b''}, {''c'', ''a''}
 
:{''c'', ''a''}, {''b''} .
 
 
В противном случае, если различные упорядочивания множеств считаются различными разбиениями, тогда количество таких упорядоченных разбиений называются '''упорядоченными числами Белла'''.
 
В противном случае, если различные упорядочивания множеств считаются различными разбиениями, тогда количество таких упорядоченных разбиений называются '''упорядоченными числами Белла'''.
  
Строка 31: Строка 32:
 
Если число <tex dpi="130">N</tex>является свободным от квадратов <ref>[[wikipedia:Square-free element|Wikipedia {{---}} Cвободные от квадратов числа]]</ref>, то <tex dpi="130">B_n</tex> показывает количество различных мультипликативных разбиений  <tex dpi="130">N</tex>.
 
Если число <tex dpi="130">N</tex>является свободным от квадратов <ref>[[wikipedia:Square-free element|Wikipedia {{---}} Cвободные от квадратов числа]]</ref>, то <tex dpi="130">B_n</tex> показывает количество различных мультипликативных разбиений  <tex dpi="130">N</tex>.
 
Если <tex dpi="130">N</tex> является квадратичным положительным целым числом  (является произведением некоторого числа <tex dpi="130">n</tex>  различных простых чисел), то <tex dpi="130">B_n</tex> дает '''число различных мультипликативных разбиений''' <tex dpi="130">N</tex>. Это является факторизацией <tex dpi="130">N</tex> в числа большие, чем <tex>1</tex> (рассматривая две факторизации как идентичные, если они имеют одинаковые факторы в другом порядке.) подтверждает это наблюдение Сильвио Минетоле<ref> Williams 1945 credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).</ref>.
 
Если <tex dpi="130">N</tex> является квадратичным положительным целым числом  (является произведением некоторого числа <tex dpi="130">n</tex>  различных простых чисел), то <tex dpi="130">B_n</tex> дает '''число различных мультипликативных разбиений''' <tex dpi="130">N</tex>. Это является факторизацией <tex dpi="130">N</tex> в числа большие, чем <tex>1</tex> (рассматривая две факторизации как идентичные, если они имеют одинаковые факторы в другом порядке.) подтверждает это наблюдение Сильвио Минетоле<ref> Williams 1945 credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).</ref>.
Например, <tex>30</tex> является произведением  <tex>3</tex> простых чисел <tex>2</tex>, <tex>3</tex>, and&nbsp;5, и имеет <tex dpi="130">N=5 </tex> факторизаций:  
+
Например, <tex>30</tex> является произведением  <tex>3</tex> простых чисел <tex>2</tex>, <tex>3</tex> и <tex>5</tex> и имеет <tex dpi="130">N=5 </tex> факторизаций:  
 
:<tex>30 = 2\times 15=3\times 10=5\times 6=2\times 3\times 5</tex>
 
:<tex>30 = 2\times 15=3\times 10=5\times 6=2\times 3\times 5</tex>
  
 
==Схемы рифмовки==
 
==Схемы рифмовки==
Числа Белла показывают ''количество схем рифмовки <tex dpi="130">n</tex>-ой строфы''. Схема рифмы описывает, какие строки рифмуются друг с другом, и поэтому может быть истолковано как разбиение множества строк в подмножества рифм. Таким образом, <tex>15</tex> возможных четверостиший схемами рифмовки являются:
+
Числа Белла показывают ''количество схем рифмовки на <tex dpi="130">n</tex> строках''. Схема рифмы описывает, какие строки рифмуются друг с другом, и поэтому может быть истолковано как отношение экивалентности на множестве строк. Таким образом, <tex>15</tex> возможных четверостиший схемами рифмовки являются:
<tex dpi="130"> \newline{} AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC,
+
<tex dpi="130"> AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC,
 
ABBA, ABBB, ABBC, ABCA, ABCB, ABCC,  ABCD</tex>.
 
ABBA, ABBB, ABBC, ABCA, ABCB, ABCC,  ABCD</tex>.
  
Строка 42: Строка 43:
  
 
===Формулы суммирования===
 
===Формулы суммирования===
Числа Белла удовлетворяют рекуррентному соотношению c участием биномиальных коэффициентов s:
+
====Биномиальные коэффициенты====
 +
Числа Белла удовлетворяют рекуррентному соотношению c участием биномиальных коэффициентов:
 
:<tex dpi = "150">B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.</tex>
 
:<tex dpi = "150">B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.</tex>
 +
==== Доказательство ====
 +
Докажем, что  <tex dpi = "150">B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_{n-k}.</tex> По определению <tex dpi = "150">B_{n}\ { — }\ </tex>число всех неупорядоченных подмножеств <tex>n</tex>-элементного множества. Посчитаем количество неупорядоченных подмножеств для <tex dpi= "150">(n+1)</tex>-элементного множества множества: Пусть <tex dpi= "150">x_1 \cup... \cup x_k\ { — }\ </tex>подмножества множества <tex dpi= "150">[1...n+1]</tex>. Пусть <tex dpi= "150">n+1\in x_k</tex>, тогда <tex dpi= "150">x_1 \cup... \cup x_{k-1}\ { — }\ </tex>подмножество множества <tex dpi="150">[1...n+1]</tex> \ <tex dpi= "150">x_k</tex>. Пусть <tex dpi= "150">|x_k|=i+1</tex>, где <tex dpi= "150">i\in [0;n]</tex>, тогда <tex dpi= "150">x_k</tex> можно выбрать <tex dpi= "150">\binom{n}{i}</tex> способами, а оставшиеся элементы разбить <tex dpi = "150">B_{n-i}</tex> способами. <tex dpi = "150">B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_{n-k}=</tex> <tex dpi = "150">\sum_{k=0}^{n} \binom{n}{n-k} B_{k}=</tex> <tex dpi= "150">\sum_{k=0}^{n} \binom{n}{k} B_k</tex>.
 +
 +
====Связь с числами Стирлинга второго рода====
 
Другая формула суммирования представляет каждое число Белла как сумму [[Числа Стирлинга второго рода|'''чисел Стирлинга второго рода''']]:
 
Другая формула суммирования представляет каждое число Белла как сумму [[Числа Стирлинга второго рода|'''чисел Стирлинга второго рода''']]:
:<tex dpi = "150">B_n=\sum_{k=0}^n \left\{{n\atop k}\right\}.</tex>
+
:<tex dpi = "150">B_n=\sum_{k=0}^n \left\{{n\atop k}\right\}</tex>,
Число Стирлинга <tex dpi = "150">\left\{{n\atop k}\right\}</tex> является количеством способов разбиения набора элементов <tex dpi = "150">n</tex> в ровно <tex dpi="150">k</tex> непустых подмножеств.  
+
где число Стирлинга <tex dpi = "150">\left\{{n\atop k}\right\}</tex> является количеством способов разбиения набора элементов <tex dpi = "150">n</tex> в ровно <tex dpi="150">k</tex> непустых подмножеств.
Michael Spivey<ref>Spivey, Michael Z. (2008). "A generalized recurrence for Bell numbers" . Journal of Integer Sequences. 11 (2): Article 08.2.5, 3. MR 2420912.</ref>  получил формулу, которая объединяет оба эти суммирования:
+
==== Доказательство ====
 +
Посчитаем количество подмножеств <tex dpi= "150">n</tex>-элементного множества. Нам нужно разбить <tex dpi= "150">n</tex>-элементное множество на <tex dpi= "150">k</tex> непустых подмножеств, где <tex dpi= "150">k</tex> от <tex dpi= "150">1</tex> до <tex dpi= "150">n</tex>. Пусть
 +
<tex dpi= "150">C\ { — }\ </tex>все подмножества <tex dpi= "150">n</tex>-элементного множества. Пусть <tex dpi= "150">A_k\ { — }\ </tex>разбиение <tex dpi= "150">n</tex>-элементного множества на <tex dpi= "150">k</tex> непустых подмножеств, тогда <tex dpi = "150"> C = \bigcup \limits_{k=1}^{n}A_k</tex>. <tex dpi = "150">|A_k|=\left\{{n\atop k}\right\}\ { — }\ </tex>по определению, тогда <tex dpi = "150">B_n=|C|=\sum_{k=1}^{n} \ |A_k|=\sum_{k=1}^n \left\{{n\atop k}\right\}=\sum_{k=0}^n \left\{{n\atop k}\right\}</tex>, т.к. <tex dpi = "150">\left\{{n\atop 0}\right\}=0</tex>.
 +
 
 +
====Объединяющая формула====
 +
Майкл Спайви<ref>Spivey, Michael Z. (2008). "A generalized recurrence for Bell numbers" . Journal of Integer Sequences. 11 (2): Article 08.2.5, 3. MR 2420912.</ref>  получил формулу, которая объединяет оба эти суммирования:
 
:<tex dpi = "150">B_{n+m} = \sum_{k=0}^n \sum_{j=0}^m \left\{{m\atop j}\right\} {n \choose k} j^{n-k} B_k.</tex>
 
:<tex dpi = "150">B_{n+m} = \sum_{k=0}^n \sum_{j=0}^m \left\{{m\atop j}\right\} {n \choose k} j^{n-k} B_k.</tex>
 +
==== Лемма ====
 +
<tex dpi = "150">B_{n+m}\ { — }\ </tex>количество способов разбить <tex dpi = "150">(n+m)</tex>-элементное множество на подмножества. Количество способов разбить <tex dpi = "150">m</tex>-элементное множество на <tex dpi = "150">j</tex> непустых подмножеств это <tex dpi = "150">\left\{{m\atop j}\right\}</tex>, где <tex dpi = "150">j</tex> меняется от <tex dpi = "150">1</tex> до <tex dpi = "150">m</tex>. Из оставшихся <tex dpi = "150">n</tex> объектов выберем <tex dpi = "150">k</tex>, для разделения их на новые подмножества, а оставшиеся <tex dpi = "150">n-k</tex> объектов распределим между <tex dpi = "150">j</tex> подмножествами, сформированных из <tex dpi = "150">m</tex>-элементного множества. <tex dpi = "150">B_{k}\ { — }\ </tex>количество разбиений <tex dpi = "150">k</tex>-элементного множества на подмножества и <tex dpi = "150">j^{n-k}</tex> способов разбить <tex dpi = "150">n-k</tex> элементов между <tex dpi = "150">j</tex> подмножествами. Значит <tex dpi = "150">j^{n-k} \left\{{n\atop k}\right\}\binom{n}{k} B_{k}</tex> способов разбить <tex dpi = "150">m</tex> элементов на <tex dpi = "150">j</tex> подмножеств и выбрать <tex dpi = "150">k</tex> элементов из <tex dpi = "150">n</tex>-элементного множества и выбрать <tex dpi = "150">k</tex> элементов из <tex dpi = "150">n </tex>-элементного множества и сформировать из них новые подмножества, а из оставшихся <tex dpi = "150">n-k</tex> объектов разделить между <tex dpi = "150">j</tex> множествами, сформированных из <tex dpi = "150">m</tex>-элементного множества.
 +
 +
==== Доказательство ====
 +
Суммируя подмножества, рассмотренные в лемме, меняя <tex dpi = "150">m</tex> и <tex dpi = "150">k</tex>, получаем:
 +
<tex dpi = "150">B_{n+m}=\sum_{k=0}^n \sum_{j=1}^m </tex><tex dpi = "150">\left\{{m\atop j}\right\}j^{n-k} \binom{n}{k} B_{k}=</tex><tex dpi = "150">B_{n+m}=\sum_{k=0}^n \sum_{j=0}^m </tex><tex dpi = "150">\left\{{m\atop j}\right\}j^{n-k} \binom{n}{k} B_{k}</tex> т.к. <tex dpi = "150">\left\{{m\atop 0}\right\}=0</tex>.
  
 
===Производящая функция===
 
===Производящая функция===
Экспоненциальной [[производящая функция|производящей функцией]] числе Белла является:
+
Экспоненциальной [[производящая функция|производящей функцией]] чисел Белла является:
 
:<tex dpi = "150">B(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.</tex>
 
:<tex dpi = "150">B(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.</tex>
 
Суммирование используется для определения экспоненциальной производящей функции для любой последовательности чисел. Правая часть является результатом выполнения суммирования в конкретном случае.
 
Суммирование используется для определения экспоненциальной производящей функции для любой последовательности чисел. Правая часть является результатом выполнения суммирования в конкретном случае.
Строка 57: Строка 74:
 
===Моменты распределения вероятностей===
 
===Моменты распределения вероятностей===
  
Числа Белла удовлетворяют '''формуле Добинского'''
+
Числа Белла удовлетворяют '''формуле Добинского''':
:<tex dpi = "180">B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}.</tex>
+
:<tex dpi = "150">B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}.</tex>
Эта формула может быть получена за счет расширения экспоненциальной производящей функции, используя  ряд Тейлора <ref>[[wikipedia:Taylor series|Ряд Тейлора]]</ref> для экспоненциальной функции, а затем собирая условия с аналогичным показателем экспоненты. <ref>Flajolet & Sedgewick (2009)</ref>.
+
Эта формула может быть получена за счет расширения экспоненциальной производящей функции, используя  ряд Тейлора<ref>[[wikipedia:Taylor series|Ряд Тейлора]]</ref> для экспоненциальной функции, а затем собирая условия с аналогичным показателем экспоненты.<ref>Flajolet & Sedgewick (2009)</ref>.
Это позволяет интерпретировать ''B<sub>n</sub>'' как <tex dpi="130">n</tex>-й момент Пуассоновского распределения с ожидаемым значением 1.
+
Это позволяет интерпретировать ''B<sub>n</sub>'' как <tex dpi="130">n</tex>-й момент Пуассоновского распределения с ожидаемым значением <tex>1</tex>.
  
 
===Интегральное представление===
 
===Интегральное представление===
Строка 71: Строка 88:
 
===Темпы роста===
 
===Темпы роста===
 
Известно несколько асимптотических формул для чисел Белла.
 
Известно несколько асимптотических формул для чисел Белла.
'''Беренд Тасса''' в <tex>2010-</tex>м<ref>Berend, D.; Tassa, T. (2010). "Improved bounds on Bell numbers and on moments of sums of random variables". Probability and Mathematical Statistics. 30 (2): 185–205.</ref>  установлил следующие границы:
+
'''Беренд Тасса''' в <tex>2010</tex>-м<ref>Berend, D.; Tassa, T. (2010). "Improved bounds on Bell numbers and on moments of sums of random variables". Probability and Mathematical Statistics. 30 (2): 185–205.</ref>  установлил следующие границы:
 
:<tex dpi = "150"> B_n < \left( \frac{0.792 n}{\ln( n+1)} \right)^n </tex> для всех положительных чисел  <tex>n</tex>;
 
:<tex dpi = "150"> B_n < \left( \frac{0.792 n}{\ln( n+1)} \right)^n </tex> для всех положительных чисел  <tex>n</tex>;
 
кроме того, если <tex> \varepsilon>0 </tex> затем для всех  <tex> n > n_0(\varepsilon) </tex>,
 
кроме того, если <tex> \varepsilon>0 </tex> затем для всех  <tex> n > n_0(\varepsilon) </tex>,
Строка 78: Строка 95:
 
<tex dpi = "150"> ~d(x)= \ln \ln (x+1) - \ln \ln x + \frac{1+e^{-1}}{\ln x}\,.
 
<tex dpi = "150"> ~d(x)= \ln \ln (x+1) - \ln \ln x + \frac{1+e^{-1}}{\ln x}\,.
 
</tex>
 
</tex>
Числа Белла могут быть аппроксимированы с помощью  функции Ламберта <tex>W</tex> <ref> [[wikipedia:Lambert W function|Функция Ламберта Вт]]</ref>, данная функция имеет такой же темп роста, как логарифм, как
+
Числа Белла могут быть аппроксимированы с помощью  функции Ламберта <tex>W</tex> <ref> [[wikipedia:Lambert W function|Функция Ламберта W]]</ref>, данная функция имеет такой же темп роста, как логарифм, как
 
:<tex dpi = "150">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). </tex>
 
:<tex dpi = "150">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). </tex>
  
Строка 84: Строка 101:
 
:<tex dpi = "150">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^2P_2}{e^{W(n)}} + \frac{Q_0 + hQ_1 + h^2Q_2 + h^3Q_3 + h^4Q_4}{e^{2W(n)}} + O(e^{-3W(n)}) \right)</tex>
 
:<tex dpi = "150">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^2P_2}{e^{W(n)}} + \frac{Q_0 + hQ_1 + h^2Q_2 + h^3Q_3 + h^4Q_4}{e^{2W(n)}} + O(e^{-3W(n)}) \right)</tex>
 
Асимптотическое выражение
 
Асимптотическое выражение
:<tex dpi = "150">
+
:<tex dpi = "150">  
$$ \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) $$
+
\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)
\newline {} \qquad \text{as }n\to\infty
+
\qquad \text{as }n\to\infty
 
</tex>
 
</tex>
 
Было установлено '''де Брайном'''<ref>de Bruijn, N.G. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108.</ref> в <tex>1981</tex> году.
 
Было установлено '''де Брайном'''<ref>de Bruijn, N.G. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108.</ref> в <tex>1981</tex> году.
Строка 96: Строка 113:
 
Числа Белла могут быть с легкостью '''вычислены''' с помощью '''треугольника Белла''', который также называют '''массивом Айткена''' или '''треугольником Пирса'''.
 
Числа Белла могут быть с легкостью '''вычислены''' с помощью '''треугольника Белла''', который также называют '''массивом Айткена''' или '''треугольником Пирса'''.
 
# Начнем с единицы.  Помещаем ее в верхнюю строку. (<tex> x_{0,1} = 1 </tex>)
 
# Начнем с единицы.  Помещаем ее в верхнюю строку. (<tex> x_{0,1} = 1 </tex>)
# Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. (<tex>x_{i,1} \leftarrow x_{i-1, r}</tex> где ''r'' последний элемент (''i''-1)-й строки)
+
# Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. (<tex>x_{i,1} \leftarrow x_{i-1, i}</tex>)
# Определим остальные элементы строки <tex>( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1} )</tex>  
+
#   Заполняем строчку <tex>i</tex> по формуле <tex> ( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1}) </tex> , начиная с <tex> j = 2 </tex>, пока <tex>j \leqslant i + 1 </tex>.
# Повторяем пункт 3, пока <tex> j = r + 1 </tex>)
 
 
# Крайнее левое число данной строки является числом Белла для этой строки. (<tex>B_i \leftarrow x_{i,1}</tex>)
 
# Крайнее левое число данной строки является числом Белла для этой строки. (<tex>B_i \leftarrow x_{i,1}</tex>)
 
Первые пять строк треугольника, построенного по этим правилам:
 
Первые пять строк треугольника, построенного по этим правилам:
Строка 115: Строка 131:
  
 
===Получение с помощью чисел Стирлинга второго рода===
 
===Получение с помощью чисел Стирлинга второго рода===
[[Числа Стирлинга второго рода|'''Числа Стирлинга второго рода''']]: связаны друг с другом по следующей формуле:
+
[[Числа Стирлинга второго рода|'''Числа Стирлинга второго рода''']] связаны друг с другом по следующей формуле:
 
<tex dpi="150">\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\}
 
<tex dpi="150">\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\}
 
</tex>
 
</tex>
Заполним таблицу [[Числа Стирлинга второго рода|'''чисел Стирлинга второго рода''']], используя данную формулу.
 
 
Число Стирлинга второго рода показывает количество способов разбиения множества из <tex>n</tex> элементов на <tex>k</tex> непустых подмножеств. Если сложить все числа Стирлинга второго рода, имеющих одинаковую  <tex>n</tex>, то получим количество способов разбиения множества из <tex>n</tex> элементов на  непустых подмножеств, то есть <tex>n</tex>-ое число Белла.
 
Число Стирлинга второго рода показывает количество способов разбиения множества из <tex>n</tex> элементов на <tex>k</tex> непустых подмножеств. Если сложить все числа Стирлинга второго рода, имеющих одинаковую  <tex>n</tex>, то получим количество способов разбиения множества из <tex>n</tex> элементов на  непустых подмножеств, то есть <tex>n</tex>-ое число Белла.
Соответственно, сумма чисел <tex>n</tex>-столбца таблицы будет являться  <tex>n</tex>-ымчислом Белла.
+
 
 +
Заполним таблицу чисел Стирлинга, используя формулу выше.
 +
Cумма чисел <tex>n</tex>-ой строки будет являться  <tex>n</tex>-ым числом Белла.
 
{| border="1"
 
{| border="1"
 
  |-
 
  |-

Текущая версия на 19:40, 4 сентября 2022

Определение:
В комбинаторной математике числа Белла (англ. Bell's numbers) определяют количество возможных способов разбиения множества из [math]n[/math] элементов на подмножества.

Числа Белла начинаются с [math]B_0=B_1=1[/math] и образуют последовательность:

[math]1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057\dots [/math]

[math]n[/math]-й элемент множества чисел Белла, [math]B_n[/math], определяет количество различных способов разбиения множества, то есть количество отношений эквивалентности в нем.

Подсчет

52 разбиения множества из 5 элементов

Order.png

Разбиение множества [math]S[/math] определяется как совокупность попарно непересекающихся подмножеств множества [math]S[/math]. Например, [math]B_3 = 5[/math], потому что множество, состоящее их [math]3[/math] элементов [math] \{ a, b , c \} [/math] может быть разделено [math]5[/math] различными способами:

[math] \{ a \} , \{ b \} , \{ c \} [/math]
[math] \{ a \} , \{b, c \} [/math]
[math] \{ b \} , \{a, c \} [/math]
[math] \{ c \} , \{ a, b \} [/math]
[math] \{ a, b , c \} [/math]

[math]B_0 = 1[/math], т.к. существует только одно возможное разбиение пустого множества. Пустое множество может разбиваться только на само себя. Как было обозначено выше, мы не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них. Это означает, что данные разбиения являются идентичными:

[math] \{ b \} , \{ a , c \} [/math]
[math]\{ a, c\}, \{ b \} [/math]
[math]\{ b \}, \{ c, a \} [/math]
[math]\{ c, a \}, \{ b \} [/math]


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

Факторизации

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

[math]30 = 2\times 15=3\times 10=5\times 6=2\times 3\times 5[/math]

Схемы рифмовки

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

Свойства

Формулы суммирования

Биномиальные коэффициенты

Числа Белла удовлетворяют рекуррентному соотношению c участием биномиальных коэффициентов:

[math]B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.[/math]

Доказательство

Докажем, что [math]B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_{n-k}.[/math] По определению [math]B_{n}\ { — }\ [/math]число всех неупорядоченных подмножеств [math]n[/math]-элементного множества. Посчитаем количество неупорядоченных подмножеств для [math](n+1)[/math]-элементного множества множества: Пусть [math]x_1 \cup... \cup x_k\ { — }\ [/math]подмножества множества [math][1...n+1][/math]. Пусть [math]n+1\in x_k[/math], тогда [math]x_1 \cup... \cup x_{k-1}\ { — }\ [/math]подмножество множества [math][1...n+1][/math] \ [math]x_k[/math]. Пусть [math]|x_k|=i+1[/math], где [math]i\in [0;n][/math], тогда [math]x_k[/math] можно выбрать [math]\binom{n}{i}[/math] способами, а оставшиеся элементы разбить [math]B_{n-i}[/math] способами. [math]B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_{n-k}=[/math] [math]\sum_{k=0}^{n} \binom{n}{n-k} B_{k}=[/math] [math]\sum_{k=0}^{n} \binom{n}{k} B_k[/math].

Связь с числами Стирлинга второго рода

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

[math]B_n=\sum_{k=0}^n \left\{{n\atop k}\right\}[/math],

где число Стирлинга [math]\left\{{n\atop k}\right\}[/math] является количеством способов разбиения набора элементов [math]n[/math] в ровно [math]k[/math] непустых подмножеств.

Доказательство

Посчитаем количество подмножеств [math]n[/math]-элементного множества. Нам нужно разбить [math]n[/math]-элементное множество на [math]k[/math] непустых подмножеств, где [math]k[/math] от [math]1[/math] до [math]n[/math]. Пусть [math]C\ { — }\ [/math]все подмножества [math]n[/math]-элементного множества. Пусть [math]A_k\ { — }\ [/math]разбиение [math]n[/math]-элементного множества на [math]k[/math] непустых подмножеств, тогда [math] C = \bigcup \limits_{k=1}^{n}A_k[/math]. [math]|A_k|=\left\{{n\atop k}\right\}\ { — }\ [/math]по определению, тогда [math]B_n=|C|=\sum_{k=1}^{n} \ |A_k|=\sum_{k=1}^n \left\{{n\atop k}\right\}=\sum_{k=0}^n \left\{{n\atop k}\right\}[/math], т.к. [math]\left\{{n\atop 0}\right\}=0[/math].

Объединяющая формула

Майкл Спайви[3] получил формулу, которая объединяет оба эти суммирования:

[math]B_{n+m} = \sum_{k=0}^n \sum_{j=0}^m \left\{{m\atop j}\right\} {n \choose k} j^{n-k} B_k.[/math]

Лемма

[math]B_{n+m}\ { — }\ [/math]количество способов разбить [math](n+m)[/math]-элементное множество на подмножества. Количество способов разбить [math]m[/math]-элементное множество на [math]j[/math] непустых подмножеств это [math]\left\{{m\atop j}\right\}[/math], где [math]j[/math] меняется от [math]1[/math] до [math]m[/math]. Из оставшихся [math]n[/math] объектов выберем [math]k[/math], для разделения их на новые подмножества, а оставшиеся [math]n-k[/math] объектов распределим между [math]j[/math] подмножествами, сформированных из [math]m[/math]-элементного множества. [math]B_{k}\ { — }\ [/math]количество разбиений [math]k[/math]-элементного множества на подмножества и [math]j^{n-k}[/math] способов разбить [math]n-k[/math] элементов между [math]j[/math] подмножествами. Значит [math]j^{n-k} \left\{{n\atop k}\right\}\binom{n}{k} B_{k}[/math] способов разбить [math]m[/math] элементов на [math]j[/math] подмножеств и выбрать [math]k[/math] элементов из [math]n[/math]-элементного множества и выбрать [math]k[/math] элементов из [math]n [/math]-элементного множества и сформировать из них новые подмножества, а из оставшихся [math]n-k[/math] объектов разделить между [math]j[/math] множествами, сформированных из [math]m[/math]-элементного множества.

Доказательство

Суммируя подмножества, рассмотренные в лемме, меняя [math]m[/math] и [math]k[/math], получаем: [math]B_{n+m}=\sum_{k=0}^n \sum_{j=1}^m [/math][math]\left\{{m\atop j}\right\}j^{n-k} \binom{n}{k} B_{k}=[/math][math]B_{n+m}=\sum_{k=0}^n \sum_{j=0}^m [/math][math]\left\{{m\atop j}\right\}j^{n-k} \binom{n}{k} B_{k}[/math] т.к. [math]\left\{{m\atop 0}\right\}=0[/math].

Производящая функция

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

[math]B(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.[/math]

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

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

Числа Белла удовлетворяют формуле Добинского:

[math]B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}.[/math]

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

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

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

[math] B_n = \frac{n!}{2 \pi i e} \int_{\gamma} \frac{e^{e^z}}{z^{n+1}} \, dz. [/math]

Логарифмическая вогнутость

Числа Белла формируют логарифмически выпуклую последовательность. Деление их на факториал, [math]\frac{B_n}{n!}[/math], дает логарифмически выпуклую последовательность.

Темпы роста

Известно несколько асимптотических формул для чисел Белла. Беренд Тасса в [math]2010[/math][7] установлил следующие границы:

[math] B_n \lt \left( \frac{0.792 n}{\ln( n+1)} \right)^n [/math] для всех положительных чисел [math]n[/math];

кроме того, если [math] \varepsilon\gt 0 [/math] затем для всех [math] n \gt n_0(\varepsilon) [/math],

[math] B_n \lt \left( \frac{e^{-0.6 + \varepsilon} n}{\ln(n+1)}\right)^n [/math]

где [math] ~n_0(\varepsilon) = \max\left\{e^4,d^{-1}(\varepsilon) \right\}~ [/math] и [math] ~d(x)= \ln \ln (x+1) - \ln \ln x + \frac{1+e^{-1}}{\ln x}\,. [/math] Числа Белла могут быть аппроксимированы с помощью функции Ламберта [math]W[/math] [8], данная функция имеет такой же темп роста, как логарифм, как

[math]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). [/math]

Мозер Л. и Вайман М.[9] установили расширение:

[math]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^2P_2}{e^{W(n)}} + \frac{Q_0 + hQ_1 + h^2Q_2 + h^3Q_3 + h^4Q_4}{e^{2W(n)}} + O(e^{-3W(n)}) \right)[/math]

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

[math] \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 [/math]

Было установлено де Брайном[10] в [math]1981[/math] году.

Получение

Вычисление с помощью треугольника Пирса

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

Числа Белла могут быть с легкостью вычислены с помощью треугольника Белла, который также называют массивом Айткена или треугольником Пирса.

  1. Начнем с единицы. Помещаем ее в верхнюю строку. ([math] x_{0,1} = 1 [/math])
  2. Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. ([math]x_{i,1} \leftarrow x_{i-1, i}[/math])
  3. Заполняем строчку [math]i[/math] по формуле [math] ( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1}) [/math] , начиная с [math] j = 2 [/math], пока [math]j \leqslant i + 1 [/math].
  4. Крайнее левое число данной строки является числом Белла для этой строки. ([math]B_i \leftarrow x_{i,1}[/math])

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

[math]1[/math]
[math]1[/math] [math]2[/math]
[math]2[/math] [math]3[/math] [math]5[/math]
[math]5[/math] [math]7[/math] [math] 10[/math] [math] 15[/math]
[math]15[/math] [math] 20[/math] [math]27[/math] [math]37[/math] [math]52[/math]

Получение с помощью чисел Стирлинга второго рода

Числа Стирлинга второго рода связаны друг с другом по следующей формуле: [math]\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\} [/math] Число Стирлинга второго рода показывает количество способов разбиения множества из [math]n[/math] элементов на [math]k[/math] непустых подмножеств. Если сложить все числа Стирлинга второго рода, имеющих одинаковую [math]n[/math], то получим количество способов разбиения множества из [math]n[/math] элементов на непустых подмножеств, то есть [math]n[/math]-ое число Белла.

Заполним таблицу чисел Стирлинга, используя формулу выше. Cумма чисел [math]n[/math]-ой строки будет являться [math]n[/math]-ым числом Белла.

n \ k [math]0[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]4[/math] Число Белла
[math]0[/math] [math]1[/math] [math]1[/math]
[math]1[/math] [math]0[/math] [math]1[/math] [math]1[/math]
[math]2[/math] [math] 0[/math] [math]1[/math] [math]1[/math] [math]2[/math]
[math]3[/math] [math]0[/math] [math]1[/math] [math]3[/math] [math]1[/math] [math]5[/math]
[math]4[/math] [math]0[/math] [math]1[/math] [math]7[/math] [math]6[/math] [math]1[/math] [math]15[/math]

См.также

Примeчания

  1. Wikipedia — Cвободные от квадратов числа
  2. Williams 1945 credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).
  3. Spivey, Michael Z. (2008). "A generalized recurrence for Bell numbers" . Journal of Integer Sequences. 11 (2): Article 08.2.5, 3. MR 2420912.
  4. Ряд Тейлора
  5. Flajolet & Sedgewick (2009)
  6. Формула Коши
  7. Berend, D.; Tassa, T. (2010). "Improved bounds on Bell numbers and on moments of sums of random variables". Probability and Mathematical Statistics. 30 (2): 185–205.
  8. Функция Ламберта W
  9. Moser, Leo; Wyman, Max (1955). "An asymptotic formula for the Bell numbers". Transactions of the Royal Society of Canada, Section III.
  10. de Bruijn, N.G. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108.

Источники информации

  • Bender Edward A.Williamson, S. Gill, Set Partitions, 319–320, 2006
  • Wikipedia —Bell numbers
  • Nobuhiro Izumi Hui-Hsiung "Acta Applicandae Texematicae",79–87.Bell numbers, log-concavity, and log-convexity 2000
  • Aitken A. C. Edinburgh Texematical Notes,18–23 A problem in combinations 1933
  • H. W.BeckerJohn Riordan "The arithmetic of Bell and Stirling numbers" American Journal of Texematics,1948,385–394
  • E. T.Bell Exponential polynomials,Annals of Texematics,1934, 258–277
  • E. T.Bell The iterated exponential integers,Annals of Texematics,1938,539–557