Изменения

Перейти к: навигация, поиск

Числа Белла

1 байт добавлено, 22:06, 6 января 2021
Доказательство
Майкл Спайви<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}-</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>, получаем:
Анонимный участник

Навигация