Сочетания

Определение:

Сочетанием из [math]\displaystyle{ n }[/math] элементов по [math]\displaystyle{ k }[/math] называется неупорядоченная выборка без повторений объема [math]\displaystyle{ k }[/math] из [math]\displaystyle{ n }[/math]-элементного множества.

Не умаляя общности, можно называть сочетанием из [math]\displaystyle{ n }[/math] элементов по [math]\displaystyle{ k }[/math] неупорядоченный набор из [math]\displaystyle{ k }[/math] различных чисел, принадлежащих множеству [math]\displaystyle{ \{1, ..., n\} }[/math].

Количество различных сочетаний из [math]\displaystyle{ n }[/math] по [math]\displaystyle{ k }[/math] обозначают [math]\displaystyle{ C_n^k }[/math] или [math]\displaystyle{ \binom{n}{k} }[/math].

Пример 1

{{{content}}}

Пример 2

{{{content}}}

Утверждение:

Пусть [math]\displaystyle{ k,n\in\mathbb{N} }[/math] и [math]\displaystyle{ 1 \leq k \leq n }[/math]. Тогда [math]\displaystyle{ \binom{n}{k} = \frac{n!}{k!(n-k)!} }[/math].

Доказательство:

Действительно, каждому сочетанию из [math]\displaystyle{ n }[/math] по [math]\displaystyle{ k }[/math] соответствует [math]\displaystyle{ k! }[/math] различных размещений из [math]\displaystyle{ n }[/math] по [math]\displaystyle{ k }[/math] с различным порядком следования элементов. Тогда [math]\displaystyle{ \binom{n}{k} = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!} }[/math].

[math]\displaystyle{ \blacksquare }[/math]

Свойства числа сочетаний

[math]\displaystyle{ \binom{n}{k}\cdot\binom{k}{l} = \binom{n}{l}\cdot \binom{n-l}{k-l}. }[/math]

Действительно, [math]\displaystyle{ \binom{n}{k}\cdot\binom{k}{l}= \frac{n!}{k!(n-k)!}\cdot\frac{k!}{l!(k-l)!} \cdot \frac{(n-l)!}{(n-l)!}= \frac{n!}{l!(n-l)!}\cdot\frac{(n-l)!}{(k-l)!(n-k)!} = \binom{n}{l}\cdot \binom{n-l}{k-l}. }[/math]

Интуитивно формулу можно описать как разбиение множества из [math]\displaystyle{ n }[/math] элементов на три подмножества мощностей [math]\displaystyle{ l }[/math], [math]\displaystyle{ k-l }[/math], [math]\displaystyle{ n-k }[/math] соответственно. Левая часть равенства описывает выбор сначала [math]\displaystyle{ k }[/math] элементов из [math]\displaystyle{ n }[/math], а затем [math]\displaystyle{ l }[/math] элементов из выбранных [math]\displaystyle{ k }[/math]. Получим все варианты разбиения исходного множества на три подмножества указанных мощностей.

Правая часть равенства соответствует выбору сначала [math]\displaystyle{ l }[/math] элементов из [math]\displaystyle{ n }[/math], а затем [math]\displaystyle{ k-l }[/math] элементов из оставшихся [math]\displaystyle{ n-l }[/math]. Получим те же варианты подмножеств.