Размещения и сочетания

Пусть у нас есть множество из трех элементов $\left\{ a,b,c\right\}$ . Какими способами мы можем выбрать из этих элементов два? ab,ac,bc,ba,ca,cb .

Определение. Размещениями множества из различных элементов по элементов $(m\le n)$ называются комбинации, которые составлены из данных элементов по элементов и отличаются либо самими элементами, либо порядком элементов.

Число всех размещений множества из элементов по элементов обозначается через ${\sf A}_m^n$ (от начальной буквы французского слова “arrangement”, что означает размещение), где $n=1,2,\dots$ и $m=\overline{1,n}$ .

Теорема. Число размещений множества из элементов по элементов равно

${\sf A}_n^m=n(n-1)\dots(n-m+1).$

Доказательство. Пусть у нас есть элементы $a_1,a_2,\ldots,a_n$ . Пусть $a_{i_1},a_{i_2},\ldots,a_{im}$ — возможные размещения. Будем строить эти размещения последовательно. Сначала определим $a_{i_1}$ — первый элемент размещения. Из данной совокупности элементов его можно выбрать различными способами. После выбора первого элемента $a_{i_1}$ для второго элемента $a_{i_2}$ остается n-1 способов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:

${\sf A}_n^m=n(n-1)\cdot\dots\cdot(n-m+1).$

Пример. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?

Решение. Искомое число трехполосных флагов:

${\sf A}_5^3=5\cdot4\cdot3=60.$

Определение. Перестановкой множества из элементов называется расположение элементов в определенном порядке.

Так, все различные перестановки множества из трех элементов $\{ a,b,c\}$ — это

abc,acb,bac,bca,cab,cba.

Очевидно, перестановки можно считать частным случаем размещений при m=n .

Число всех перестановок из элементов обозначается ${\sf P}_n$ (от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле

${\sf P}_n=n(n-1)\cdot\ldots\cdot2\cdot1=n!$

Пример. Сколькими способами можно расставить 8 ладей на шахматной доске так, чтобы они не били друг друга?

Решение. Искомое число расстановки 8 ладей

${\sf P}_8=8!=40320.$

$\begin{tabular}{|c|c|c|c|} \hline $n$&$n!$&$n$&$n!$\\ \hline 0&1&6&720\\ \hline 1&1&7&5040\\ \hline 2&2&8&40320\\ \hline 3&6&9&362880\\ \hline 4&24&10&3628800\\ \hline 5&120&&\\ \hline \end{tabular}$

0!=1 по определению!

Определение. Сочетаниями из различных элементов по элементов называются комбинации, которые составлены из данных элементов по элементов и отличаются хотя бы одним элементом (иначе говоря, -элементные подмножества данного множества из элементов).

Как видим, в сочетаниях в отличие от размещений не учитывается порядок элементов. Число всех сочетаний из элементов по элементов в каждом обозначается ${\sf C}_n^k$ (от начальной буквы французского слова “combinasion”, что значит “сочетание”).

Числа ${\sf C}_n^k$

${\sf C}_5^{2}=10$

Все сочетания из множества $\{ a,b,c,d,e\}$ по два — ab,ac,ad,ae,bc,bd,be,cd,ce,de .

${\sf C}_n^0=1,{\sf C}_n^n=1,{\sf C}_n^1=n$ .

Свойства чисел ${\sf C}_n^k$

1. ${\sf C}_n^k={\sf C}_n^{n-k}$ .

Действительно, каждому -элементному подмножеству данного элементного множества соответствует одно и только одно n-k -элементное подмножество того же множества.

2. ${\sf C}_n^k={\sf C}_{n-1}^k+{\sf C}_{n-1}^{k-1}$ .

Действительно, мы можем выбирать подмножества из элементов следующим образом: фиксируем один элемент; число -элементных подмножеств, содержащих этот элемент, равно ${\sf C}_{n-1}^{k-1}$ ; число -элементных подмножеств,