Изменения

Докажем, что <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{in}{ni}</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>