Перестановки, размещения, сочетания

Читают «эн факториал»: $2! = 2$, $3! = 6$, $4! = 24$. Удобное свойство: $(n + 1)! = (n + 1) \cdot n!$.

Договорённость $0! = 1$ нужна, чтобы формулы для чисел сочетаний работали и при $k = 0$, $k = n$.

В 9 классе формулы получали правилом умножения. Теперь докажем их строго — методом математической индукции.

Перестановка из $n$ элементов — это расположение их в определённом порядке. Число перестановок обозначают $P_n$ («пэ из эн»). Из $x_1, x_2$ — две перестановки; из $x_1, x_2, x_3$ — шесть.

Доказательство. База: $P_1 = 1 = 1!$. Пусть $P_k = k!$. Чтобы получить все перестановки из $k + 1$ элементов, поставим на первое место любой элемент $x_j$ ($k + 1$ способ), а за ним остальные $k$ элементов всеми $P_k = k!$ способами.

Получаем $P_{k+1} = (k + 1) \cdot k! = (k + 1)!$ — по принципу индукции $P_n = n!$ для всех $n$.

1. Всего $P_6 = 720$. а) Первое место занято, остальные $5$ — в любом порядке: $5! = 120$.
2. б) Для $x_1$ четыре места из шести, остальные $5$ элементов — $5!$: $\ 4 \cdot 120 = 480$.
3. в) Два места заняты: $4! = 24$. $\$ г) Из случаев а) убираем случаи в): $120 - 24 = 96$.
4. д) Склеим $x_1$ и $x_6$ в один блок: $5$ «элементов» — $5!$ перестановок, внутри блока $2$ порядка: $2 \cdot 120 = 240$.

1. Мальчики и девочки чередуются: схема МДМДМД или ДМДМДМ — $2$ способа.
2. В каждой схеме мальчиков по их трём местам рассаживаем $3! = 6$ способами, девочек — тоже $6$.
3. По правилу умножения: $2 \cdot 6 \cdot 6 = 72$.

Размещение из $n$ элементов по $k$ ($k \le n$) — любой упорядоченный набор из $k$ элементов, составленный из $n$ данных элементов. Наборы различаются либо хотя бы одним элементом, либо порядком. Обозначение $A_n^k$ — «а из эн по ка».

Доказательство (индукция по $k$). $A_n^1 = n$. Пусть $A_n^i = n(n - 1)\ldots(n - i + 1)$. К каждому упорядоченному набору из $i$ элементов присоединяем ещё один из $n - i$ оставшихся: $A_n^{i+1} = A_n^i (n - i) = n(n - 1)\ldots(n - i)$.

В произведении $k$ множителей. При $k = n$ размещение — это перестановка: $A_n^n = n! = P_n$.

1. Путёвки разные — важно, кому какая досталась: упорядоченный выбор, размещения из $6$.
2. а) $A_6^2 = 6 \cdot 5 = 30$; б) $A_6^3 = 6 \cdot 5 \cdot 4 = 120$; в) $A_6^4 = 6 \cdot 5 \cdot 4 \cdot 3 = 360$.
3. Если бы путёвки были одинаковыми (№ 1.65), порядок был бы не важен — это уже сочетания.

Сочетание из $n$ элементов по $k$ ($1 \le k \le n$) — любая группа из $k$ этих элементов. Порядок не важен: переставив элементы сочетания, получим то же сочетание. Обозначение $C_n^k$ — «цэ из эн по ка».

Доказательство. Из $n$ элементов можно составить $C_n^k$ групп по $k$, в каждой группе — $P_k$ перестановок. Каждое размещение получается ровно один раз, поэтому $A_n^k = C_n^k \cdot P_k$.

Умножив числитель и знаменатель на $(n - k)!$, получим $C_n^k = \dfrac{n!}{k!(n - k)!}$. Считают $C_n^0 = 1$ — формула с факториалами это даёт.

Первое: $C_n^{n-k} = \dfrac{n!}{(n - k)!\,k!} = C_n^k$. Смысл: выбрать $k$ элементов — то же, что выбрать $n - k$ оставшихся.

Второе: $C_n^k + C_n^{k+1} = \dfrac{n!}{k!(n - k)!} + \dfrac{n!}{(k + 1)!(n - k - 1)!} = \dfrac{n!}{k!(n - k - 1)!}\left(\dfrac{1}{n - k} + \dfrac{1}{k + 1}\right) = \dfrac{n!\,(n + 1)}{(k + 1)!\,(n - k)!} = C_{n+1}^{k+1}$.

Смысл второго: группа из $k + 1$ элемента среди $n + 1$ либо содержит выделенный элемент (остальные $k$ — из $n$), либо не содержит (все $k + 1$ — из $n$).

Выпишем числа $C_n^0, C_n^1, \ldots, C_n^n$ строками. По второму свойству каждое число равно сумме двух соседних над ним: $C_4^1 + C_4^2 = 4 + 6 = 10 = C_5^2$.

По первому свойству строки симметричны. Края — единицы: $C_n^0 = C_n^n = 1$.

Сумма чисел строки $n$ равна $2^n$ — это число всех подмножеств множества из $n$ элементов (пример 5).

1. а) Партия — пара участников без порядка: $C_n^2 = \dfrac{n(n - 1)}{2} = 36$, $\ n^2 - n - 72 = 0$, $\ n = 9$ ($n = -8$ не подходит).
2. б) Команды из $2$, $3$ и $4$ человек: $C_6^2 + C_6^3 + C_6^4 = 15 + 20 + 15 = 50$.
3. По свойству $C_6^4 = C_6^2$ — второе слагаемое можно было не считать.

1. Каждый элемент либо входит в подмножество, либо нет — $2$ варианта, и выбор для разных элементов независим.
2. По правилу умножения: $2 \cdot 2 \cdot \ldots \cdot 2 = 2^n$ подмножеств (включая пустое и само множество).
3. Тот же ответ по сочетаниям: подмножеств из $k$ элементов $C_n^k$, поэтому $C_n^0 + C_n^1 + \ldots + C_n^n = 2^n$.

1. Исходы — пары из $8$ человек без порядка: $C_8^2 = \dfrac{8 \cdot 7}{2} = 28$.
2. Благоприятные — пары, где есть Б.: второго выбираем из $7$ остальных, $C_7^1 = 7$.
3. $P = \dfrac{7}{28} = 0{,}25$. Короче: двое из восьми, у каждого шанс $\dfrac28$.

1. Всего фломастеров $25$, пар $C_{25}^2 = \dfrac{25 \cdot 24}{2} = 300$.
2. Пара «синий и красный»: синий — $8$ способов, красный — $6$: $\ 8 \cdot 6 = 48$.
3. $P = \dfrac{48}{300} = 0{,}16$.

1. Нас интересуют только места девочек: пара стульев из $5$ — $C_5^2 = 10$ равновозможных исходов.
2. Соседних пар стульев за круглым столом столько же, сколько стульев: $5$.
3. $P = \dfrac{5}{10} = 0{,}5$.

• $P_n = n!$; $\ A_n^k = \dfrac{n!}{(n - k)!}$; $\ C_n^k = \dfrac{n!}{k!(n - k)!}$; все три формулы доказываются индукцией.
• $A_n^k = C_n^k \cdot P_k$: размещение = группа + порядок внутри неё.
• $C_n^k = C_n^{n-k}$, $\ C_n^k + C_n^{k+1} = C_{n+1}^{k+1}$ — треугольник Паскаля.
• Подмножеств у множества из $n$ элементов $2^n$.
• В ЕГЭ №4 выбор группы считаем сочетаниями: $P = \dfrac{C_{\ldots}\cdot C_{\ldots}}{C_n^k}$.