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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
(Метки: правка с мобильного устройства, правка из мобильной версии)
(Доказательство)
(Метки: правка с мобильного устройства, правка из мобильной версии)
 
(не показано 8 промежуточных версий этого же участника)
Строка 5: Строка 5:
  
 
=== Доказательство ===
 
=== Доказательство ===
Докажем, что  <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+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>.
  
 
===2. Формула с числами Стирлинга второго рода===
 
===2. Формула с числами Стирлинга второго рода===
Строка 12: Строка 12:
 
где число Стирлинга <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> непустых подмножеств.
 
=== Доказательство ===
 
=== Доказательство ===
Посчитаем количество разбиений <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">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>
+
<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>.
  
 
===3. Формула объединяющая эти два суммирования===
 
===3. Формула объединяющая эти два суммирования===
Строка 19: Строка 19:
 
:<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">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">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_{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>.

Текущая версия на 21:55, 10 января 2021

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

1. Формула с биномиальными коэффициентами

Числа Белла удовлетворяют рекуррентному соотношению 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].

2. Формула с числами Стирлинга второго рода

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

[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. Формула объединяющая эти два суммирования

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

[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].
  1. Spivey, Michael Z. (2008). "A generalized recurrence for Bell numbers" . Journal of Integer Sequences. 11 (2): Article 08.2.5, 3. MR 2420912.