30
правок
Изменения
Нет описания правки
где <tex>k</tex> — число, не превышаемое слагаемыми, причем начальное значение <tex>k = n</tex>. Вывод формулы можно найти [[Нахождение количества разбиений числа на слагаемые | здесь]].
=== Разбиение на подмножества ==='''Разбиение''' множества <math>X</math> на '''на подмножества''' называется — это семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:
# <math>U_{\alpha} \cap U_{\beta} = \emptyset</math> для любых <math>\alpha, \beta \in A</math>, таких что <math>\alpha \not= \beta</math>;
# <math>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</math>.
Если задано множество из <tex>n</tex> элементов, которое необходимо разбить на <tex>k</tex> непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть (<tex dpi = "180">\lbrace{n-1\atop k-1}\rbrace</tex> способами), либо поместить его в некоторое подмножество (<tex>k</tex><tex dpi = "180">\lbrace{n-1\atop k}\rbrace</tex> способами, поскольку каждый из <tex dpi = "180">\lbrace{n-1\atop k}\rbrace</tex> способов распределения первых <tex>n-1</tex> элементов по <tex>k</tex> непустым частям дает <tex>k</tex> подмножеств, с которыми можно объединить последний элемент).
<tex>\begin{Bmatrix}
n \\
k
\end{Bmatrix} = \begin{cases}
k\begin{Bmatrix}
n-1 \\
k
\end{Bmatrix} + \begin{Bmatrix}
n-1 \\
k-1
\end{Bmatrix}, 0<k<n \\
0, k = 0 \\
0, n = 0 \\
0, k > n \\
1, k = n
\end{cases}
</tex>
== Источники ==
