Изменения

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

Обсуждение:Числа Белла

69 байт убрано, 13:52, 10 января 2021
Лемма
:<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>.
16
правок

Навигация