9 класс Вероятность и статистика Элементы комбинаторики

Перестановки, факториал, сочетания

Содержание

В уроке «Комбинаторное правило умножения» мы считали способы по дереву выборов: каждый шаг — ярус, каждый способ — путь от корня до листа, а число путей равно произведению чисел ветвей на ярусах. В этом уроке рассмотрим два частых случая: расстановку предметов в ряд и выбор, в котором порядок не важен. Из них появятся факториал, перестановки и сочетания.

Вопрос, на который ответим в конце урока. В лото «6 из 45» игрок отмечает в билете $6$ чисел из $45$. Сколькими способами можно заполнить билет и каков шанс угадать все шесть чисел?

На каждом ярусе ветвей на одну меньше

Три флажка $A$, $B$ и $C$ вешают в ряд. Построим дерево выборов. Первый ярус — какой флажок висит первым: $3$ ветви. Второй флажок выбираем из двух оставшихся: из каждого узла выходят $2$ ветви. Третьему месту достается последний флажок: $1$ ветвь.

Дерево расстановок флажков A, B, C: на ярусах 3, 2 и 1 ветвь, листьев 3 · 2 · 1 = 6 = 3! — Ветвей на ярусах $3$, $2$, $1$ — путей $3 \cdot 2 \cdot 1 = 6$: ровно шесть расстановок флажков

По правилу умножения путей $3 \cdot 2 \cdot 1 = 6$: $ABC$, $ACB$, $BAC$, $BCA$, $CAB$, $CBA$. Для четырех флажков ярусов четыре, а путей $4 \cdot 3 \cdot 2 \cdot 1 = 24$. Произведения «от $n$ вниз до $1$» встречаются так часто, что для них ввели короткую запись.

Определение

Факториал числа $n$ (читается «эн факториал») — произведение всех натуральных чисел от $1$ до $n$:

$$n!=1 \cdot 2 \cdot \ldots \cdot n$$

По договоренности $0!=1$.

Почему $0!=1$? Каждый следующий факториал получается из предыдущего умножением: $n!=n \cdot (n-1)!$. При $n=1$ это дает $1!=1 \cdot 0!$, а $1!=1$, значит, $0!=1$. По смыслу дерева так и есть: ноль предметов можно расставить одним способом — ничего не ставить.

Сравним факториал с удвоением $2n$ и квадратом $n \cdot n$:

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
$n!$	$1$	$1$	$2$	$6$	$24$	$120$	$720$	$5040$
$2n$	$0$	$2$	$4$	$6$	$8$	$10$	$12$	$14$
$n \cdot n$	$0$	$1$	$4$	$9$	$16$	$25$	$36$	$49$

Ошибка

Решавр пишет: «$5!=2 \cdot 5=10$, а $0!=0$».

Проверим по таблице. При $n=3$ действительно $3!=6=2 \cdot 3$, но это совпадение. Уже $4!=24$, а $2 \cdot 4=8$; $5!=120$, а не $10$.

Где сломалось рассуждение: факториал — произведение всех чисел от $1$ до $n$, а не удвоение и не квадрат. И $0!$ — не «умножение на нуль»: нуля среди множителей нет, $0!=1$.

Факториал растет очень быстро, но в дробях его удобно сокращать: $n!=n \cdot (n-1)!$, поэтому общий «хвост» числителя и знаменателя уходит.

Пример 1

Задача. Вычислите $\dfrac{7!}{5!}$.

Решение. $7!=7 \cdot 6 \cdot 5!$, поэтому $\dfrac{7!}{5!}=\dfrac{7 \cdot 6 \cdot 5!}{5!}=7 \cdot 6=42$. Перемножать $5040$ и $120$ не нужно.

Ответ: $42$.

Интересный факт: откуда знак «!»

Скрыть

Запись $n!$ предложил французский математик Кристиан Крамп в 1808 году. До этого произведение $1 \cdot 2 \cdot \ldots \cdot n$ записывали по-разному; короткий знак Крампа прижился и стал общепринятым.

{"questions":[{"content":"Решавр заполнил таблицу: $0! = 0$, $1! = 1$, $2! = 2$, $3! = 6$, $4! = 8$. Какие записи неверны?[[choice-1]]","widgets":{"choice-1":{"type":"choice","options":["$0! = 0$","$4! = 8$","$2! = 2$","$1! = 1$","$3! = 6$"],"explanations":["","","Верно: два множителя, $1 \\cdot 2 = 2$","Верно: в произведении один множитель $1$","Верно: $1 \\cdot 2 \\cdot 3 = 6$; здесь $n!$ случайно совпало с $2n$"],"answer":[0,1]}},"hints":["$n!$ — произведение всех чисел от $1$ до $n$; по договоренности $0! = 1$.","$4! = 1 \\cdot 2 \\cdot 3 \\cdot 4 = 24$, а не $2 \\cdot 4$.","Неверны записи $0! = 0$ и $4! = 8$."],"level":"повышенный","step":1},{"content":"Вычислите $\\dfrac{8!}{6!}$. [[input-1]]","widgets":{"input-1":{"type":"input","answer":"56"}},"hints":["$8! = 8 \\cdot 7 \\cdot 6!$, поэтому $6!$ сокращается.","$\\dfrac{8!}{6!} = 8 \\cdot 7 = 56$."],"step":1}],"mix":1}

Сколькими способами можно выстроить ряд

Флажки из прошлого раздела можно заменить чем угодно: книгами на полке, бегунами на дорожках, буквами в слове. Каждый способ расставить все предметы в ряд — один путь дерева, где ярусов столько же, сколько предметов, а ветви убывают от $n$ до $1$. Например, $8$ бегунов по $8$ дорожкам можно расставить $8!=40\,320$ способами.

Определение

Перестановка — порядок расположения $n$ различных предметов в ряд. Число перестановок обозначают $P_n$ (читается «пэ из эн»):

$$P_n=n!$$

Дерево остается таким ровным, пока нет дополнительных условий. Пусть двое обязаны стоять рядом. Тогда число ветвей на ярусе зависит от того, кто уже встал, и считать по ярусам неудобно. В таком случае сначала выполняем самое строгое условие: объединяем этих двоих в одну фишку.

Двое рядом: Аня и Боря — одна фишка, 4! = 24 ряда, внутри фишки 2 порядка, всего 2 · 4! = 48 — Аня и Боря — одна фишка: в ряду $4$ фишки, это $4!$ рядов, и внутри фишки $2$ порядка

Пример 2

Задача. Пять друзей — Аня, Боря, Вика, Гриша и Даша — встают в ряд для фото. Аня и Боря хотят стоять рядом. Сколько существует способов встать?

Решение. 1) Объединим Аню и Борю в одну фишку. Теперь в ряду $4$ фишки: $4!=24$ способа. 2) Внутри фишки два порядка: «Аня, Боря» или «Боря, Аня». 3) Шаги идут подряд, перемножаем: $2 \cdot 24=48$.

Проверка смысла: без условия рядов $5!=120$, и подходит только часть из них — $48$ меньше $120$.

Ответ: $48$.

{"questions":[{"content":"Шесть гостей рассаживают на шесть стульев, стоящих в ряд. Какое выражение дает число способов рассадки?[[choice-1]]","widgets":{"choice-1":{"type":"choice","options":["$6 \\cdot 6$","$2 \\cdot 6$","$6!$","$6+5+4+3+2+1$"],"explanations":["Гость, который уже сел, не может занять второй стул: ветвей на каждом ярусе на одну меньше","Это удвоение, а не факториал: уже $4! = 24$, а $2 \\cdot 4 = 8$","","Числа ветвей ярусов сложили, а выборы идут подряд — их перемножают"],"answer":[2]}},"hints":["Постройте дерево: на первый стул — 6 гостей, на второй — 5 оставшихся, и так до одного.","Ярусы идут подряд — числа ветвей перемножают: $6 \\cdot 5 \\cdot 4 \\cdot 3 \\cdot 2 \\cdot 1 = 6!$."],"step":1},{"content":"Четыре друга садятся в один ряд. Катя и Дима хотят сидеть рядом. Сколько существует способов рассадки? [[input-1]]","widgets":{"input-1":{"type":"input","answer":"12"}},"hints":["Объединим Катю и Диму в одну фишку: теперь в ряду 3 фишки — $3! = 6$ способов.","Внутри фишки двое могут поменяться: умножаем на 2.","$2 \\cdot 3! = 12$."],"level":"повышенный","step":1}],"mix":1}

Когда порядок не важен, пути склеиваются

Из четырех учеников — А, Б, В, Г — выбирают двух дежурных. Дерево выборов: первого дежурного — $4$ ветви, второго — $3$, путей $4 \cdot 3=12$. Но путь «сначала А, потом Б» и путь «сначала Б, потом А» дают одну и ту же пару дежурных.

Дерево «2 из 4»: 12 листьев, листья одного состава соединены дугами, пар 12 : 2! = 6, а не 12 — $12$ листьев склеиваются по два: пар дежурных $12 : 2 = 6$

Склеим листья с одинаковым составом. В каждой группе два листа — столько, сколькими способами можно упорядочить двух человек: $2!=2$. Групп $12 : 2=6$: АБ, АВ, АГ, БВ, БГ, ВГ.

Для троек из тех же учеников путей $4 \cdot 3 \cdot 2=24$, а каждая тройка встречается среди них $3!=6$ раз — по числу ее перестановок. Троек $24 : 6=4$: АБВ, АБГ, АВГ, БВГ.

Определение

Сочетание из $n$ по $k$ — набор $k$ предметов из $n$, порядок не важен. Число сочетаний обозначают $C_n^k$ (читается «цэ из эн по ка»).

Правило

Число сочетаний равно числу путей дерева из $k$ ярусов, деленному на $k!$:

$$C_n^k=\frac{n \cdot (n-1) \cdot \ldots \cdot (n-k+1)}{k!}$$

Почему делим именно на $k!$. В числителе $k$ множителей — это пути дерева из $k$ ярусов, то есть упорядоченные выборы. Каждый набор из $k$ предметов встречается среди путей столько раз, сколько у него перестановок, то есть $k!$. Все группы одного размера, поэтому деление выполняется нацело.

sostav-ne-menyaetsya

Ошибка

Решавр рассуждает: «Выбрать $2$ дежурных из $4$ учеников — это $4 \cdot 3=12$ способов».

Проверим перечислением: АБ, АВ, АГ, БВ, БГ, ВГ — пар всего $6$. Решавр посчитал пару «А и Б» дважды: как АБ и как БА.

Где сломалось рассуждение: правило умножения считает пути дерева, то есть выборы с порядком, а в задаче важен только состав. Число $12$ было бы верным, если бы выбирали старосту и заместителя: у них разные роли.

{"questions":[{"content":"Решавр решил две задачи одинаково: $6 \\cdot 5 = 30$. Задача 1: из $6$ учеников выбрать старосту и его заместителя. Задача 2: из $6$ учеников выбрать двух дежурных. Где Решавр ошибся?[[choice-1]]","widgets":{"choice-1":{"type":"choice","options":["Ни в одной: в обеих задачах по $30$ способов","В обеих: шаги надо сложить, верно $6 + 5 = 11$","Во второй: каждая пара дежурных посчитана дважды, верно $30 : 2 = 15$","В первой: роли не важны, верно $30 : 2 = 15$"],"explanations":["Во второй задаче «Аня и Боря» и «Боря и Аня» — одни и те же дежурные","Два выбора подряд перемножают; сумма считает людей, а не пары","","Староста Аня с заместителем Борей и староста Боря с заместителем Аней — разные выборы"],"answer":[2]}},"hints":["Поменяйте выбранных местами: в какой задаче получится тот же результат?","Дежурные «Аня и Боря» и «Боря и Аня» — одна пара: каждая пара посчитана дважды.","Ошибка во второй задаче: $30 : 2 = 15$."],"level":"повышенный","step":1},{"content":"[[matcher-1]]","widgets":{"matcher-1":{"type":"matcher","labels":["Выстроить $5$ учеников в очередь","Выбрать из $5$ учеников старосту и заместителя","Выбрать из $5$ учеников двух дежурных"],"items":["$5!$","$5 \\cdot 4$","$\\dfrac{5 \\cdot 4}{2}$","$5 + 4$"]}},"instruction":"Соотнесите задачу и вычисление","hints":["Очередь — все $5$ учеников в ряд: перестановки, $5!$.","Староста и заместитель — роли разные, порядок важен: $5 \\cdot 4$.","Дежурные — пара без ролей, порядок не важен: $\\dfrac{5 \\cdot 4}{2}$. Сумма $5 + 4$ не подходит ни к одной задаче."],"step":1},{"content":"Из 7 учеников нужно выбрать команду из 3 человек для конкурса. Сколькими способами это можно сделать? [[input-1]]","widgets":{"input-1":{"type":"input","answer":"35"}},"hints":["Порядок в команде не важен: считаем сочетания.","$C_7^3 = \\dfrac{7 \\cdot 6 \\cdot 5}{3!} = \\dfrac{210}{6} = 35$."],"step":1}],"mix":1}

Формула числа сочетаний и быстрый счет

Числитель $n \cdot (n-1) \cdot \ldots \cdot (n-k+1)$ — это $n!$ без «хвоста» $(n-k)!$, то есть $\frac{n!}{(n-k)!}$. Например, $5 \cdot 4=\frac{5!}{3!}$. Подставим это в правило из прошлого раздела.

Правило

Число сочетаний из $n$ по $k$:

$$C_n^k=\frac{n!}{k! \, (n-k)!}$$

Для вычислений удобнее сокращенная запись: в числителе $k$ убывающих чисел, начиная с $n$, в знаменателе $k!$.

Выбрать 2 из 5 — то же разбиение, что оставить 3: C₅² = C₅³ = 10 — Выбрать $2$ предмета из $5$ — то же, что выбрать $3$, которые останутся: $C_5^2 = C_5^3 = 10$

Если заменить $k$ на $n-k$, множители $k!$ и $(n-k)!$ в знаменателе поменяются местами, а произведение не изменится, поэтому $C_n^k=C_n^{n-k}$. Смысл виден на рисунке: каждый способ выбрать $k$ предметов одновременно выбирает $n-k$ оставшихся. Если $k$ больше половины $n$, выгодно перейти к $n-k$: множителей станет меньше.

Обратите внимание

$C_n^0=C_n^n=1$: не взять ничего и взять все можно одним способом. Формула дает то же самое именно потому, что $0!=1$. А $C_n^1=n$: один предмет из $n$ выбирают $n$ способами.

Пример 3

Задача. Вычислите: а) $C_{10}^3$; б) $C_{12}^{10}$.

Решение. а) $C_{10}^3=\dfrac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1}=\dfrac{720}{6}=120$.

б) Десять множителей в числителе не нужны: $C_{12}^{10}=C_{12}^2=\dfrac{12 \cdot 11}{2 \cdot 1}=66$.

Ответ: а) $120$; б) $66$.

{"questions":[{"content":"Число $C_{11}^{8}$ равно [[fill_choice-1]].","widgets":{"fill_choice-1":{"type":"fill_choice","options":["$C_{11}^{3}$","$C_{8}^{3}$","$C_{11}^{9}$","$11 \\cdot 10 \\cdot 9$"],"answer":0}},"instruction":"Выберите вариант","hints":["Выбрать $8$ предметов из $11$ — то же, что выбрать $3$, которые останутся.","$11-8 = 3$, поэтому $C_{11}^{8} = C_{11}^{3} = 165$."],"step":1},{"content":"Из 9 разных лотерейных билетов наугад вытягивают 3. Сколько существует способов выбрать такую тройку билетов? [[input-1]]","widgets":{"input-1":{"type":"input","answer":"84"}},"hints":["Порядок вытягивания не важен: считаем сочетания $C_9^3$.","$C_9^3 = \\dfrac{9 \\cdot 8 \\cdot 7}{3 \\cdot 2 \\cdot 1} = 84$."],"step":1}],"mix":1}

Важен ли порядок: проверка перестановкой

Перед подсчетом задайте вопрос: если поменять выбранных местами, получится другой результат? Староста Аня с заместителем Борей — не то же, что староста Боря с заместителем Аней: роли разные, порядок важен, ответ дает правило умножения. Дежурные Аня и Боря — те же, что Боря и Аня: порядок не важен, листья склеиваются, делим на $k!$.

Проверка «поменяем местами»: порядок важен — правило умножения; не важен — делим на k!, сочетания — Поменяли выбранных местами и получили другой результат — правило умножения; тот же набор — делим на $k!$

Рукопожатие — пара людей без порядка. Если в комнате $10$ человек и каждый пожал руку каждому, рукопожатий $C_{10}^2=\frac{10 \cdot 9}{2}=45$. Так же считают матчи кругового турнира, где каждая команда играет с каждой один раз.

Сочетания нужны и в вероятности: они дают число всех исходов в формуле вероятности $P=\frac{m}{N}$ из урока «Вероятность случайного события». Если выбор состоит из двух частей, считаем каждую часть сочетаниями и перемножаем, как шаги дерева.

Ровно одна девочка среди троих дежурных: 1 из 12 способов и 2 из 8, 12 · 28 = 336 из 1140 троек — Одна девочка из $12$ и двое мальчиков из $8$ — шаги подряд: $12 \cdot 28 = 336$

Пример 4

Задача. В классе $20$ учеников: $12$ девочек и $8$ мальчиков. Жребием выбирают $3$ дежурных. Найдите вероятность того, что среди них ровно одна девочка.

Решение. 1) Все исходы — тройки без порядка: $N=C_{20}^3=\dfrac{20 \cdot 19 \cdot 18}{6}=1140$. 2) Благоприятные: девочку выбираем $12$ способами, двух мальчиков — $C_8^2=28$ способами, шаги подряд: $m=12 \cdot 28=336$. 3) $P=\dfrac{336}{1140}=\dfrac{28}{95}\approx 0{,}29$.

Ответ: $\frac{28}{95}$.

Вернемся к лото «6 из 45». Порядок чисел в билете не важен, значит, это сочетания:

$$C_{45}^6=\frac{45 \cdot 44 \cdot 43 \cdot 42 \cdot 41 \cdot 40}{6!}=8\,145\,060$$

Все наборы равновозможны, и выигрышный из них только один. Вероятность угадать все шесть чисел одним билетом равна $\frac{1}{8\,145\,060}$ — меньше одной восьмимиллионной.

{"questions":[{"content":"Распределите задачи по тому, важен ли порядок выбора.[[grouper-1]]","widgets":{"grouper-1":{"type":"grouper","labels":["Порядок важен","Порядок не важен"],"items":[["Выбрать старосту и его заместителя из 10 учеников","Составить код из 3 разных цифр"],["Выбрать 2 дежурных из 10 учеников","Выбрать 3 книги в поездку из 8"]]}},"instruction":"Распределите задачи по группам","hints":["Порядок важен, если после перестановки выбранных получается другой результат (разные роли, разные места).","Порядок не важен, если получается тот же набор.","Ответ: порядок важен — староста с заместителем; код из цифр. Не важен — дежурные; книги в поездку."],"step":1},{"content":"На встрече 8 человек, каждый пожал руку каждому ровно один раз. Сколько всего было рукопожатий? [[input-1]]","widgets":{"input-1":{"type":"input","answer":"28"}},"hints":["Каждый пожал руку 7 людям: $8 \\cdot 7 = 56$ — но каждое рукопожатие посчитано дважды.","Делим на 2: $56 : 2 = 28$."],"step":1},{"content":"В коробке 7 красных и 2 синих шара. Достают сразу 3 шара. Сколькими способами можно выбрать тройку шаров, чтобы среди них был ровно один синий? [[input-2]]","widgets":{"input-2":{"type":"input","answer":"42"}},"hints":["Один синий выбираем из 2: 2 способа.","Двух красных — из 7 без порядка: $C_7^2 = 21$.","Шаги подряд — перемножаем: $2 \\cdot 21 = 42$."],"level":"повышенный","step":1}],"mix":1}

Вывод

Факториал, перестановки и сочетания позволяют посчитать варианты, не рисуя все ветви дерева: так находят число всех исходов для вероятности, число матчей турнира, шанс в лотерее. Главное — до подсчета решить, важен ли порядок: мысленно поменяйте выбранных местами. Чтобы вспомнить формулы, представьте дерево выборов: ветви убывают — это $n!$; листья с одинаковым составом склеиваются по $k!$ — это $C_n^k$.

Случай	Что в дереве	Сколько способов
Все $n$ предметов в ряд	Ветви $n$, $n-1$, …, $1$	$P_n=n!$
Выбор с ролями (порядок важен)	$k$ ярусов убывающих ветвей	$n \cdot (n-1) \cdot \ldots \cdot (n-k+1)$
Набор без порядка	Листья склеены по $k!$	$C_n^k=\frac{n!}{k! \, (n-k)!}$
Двое стоят рядом	Двое — одна фишка	$2 \cdot (n-1)!$

Часто задаваемые вопросы

Где сочетания пригодятся дальше?

В следующем уроке числа $C_n^k$ сложатся в треугольник Паскаля, и вы увидите, как они связаны между собой. Еще сочетания дают число исходов в задачах на вероятность: выбор команды, билеты, шары из коробки.

Чем сочетания отличаются от правила умножения?

Правило умножения считает пути дерева, то есть выборы с порядком. Сочетания — те же пути, но склеенные в группы с одинаковым составом. Поэтому число сочетаний в $k!$ раз меньше числа упорядоченных выборов.

Как быстро понять, важен ли порядок?

Мысленно поменяйте двух выбранных местами. Если получилось другое (другие роли, другое число, другое место в очереди), порядок важен. Если получился тот же набор (команда, букет, пара дежурных), порядок не важен.

Почему число сочетаний всегда целое, хотя мы делим?

Пути дерева разбиваются на группы с одинаковым составом, и в каждой группе ровно $k!$ путей. Значит, число путей делится на $k!$ нацело, а частное — число групп.

Зачем нужен $0!$, если ничего не умножаем?

Без договоренности $0!=1$ формула $C_n^k=\frac{n!}{k! \, (n-k)!}$ не работала бы при $k=0$ и $k=n$. С ней формула дает $C_n^0=C_n^n=1$ — столько способов не взять ничего или взять все.

Награды за урок

Проверим знания по теме?

Перестановки, факториал, сочетания

Пройти тест