6.3 Сочетания

9 класс · Вероятность◷ 55–65 минут◇ БазаНужно знать: размещения и факториал, правило произведения, классическая вероятность

Из $15$ учеников выбирают троих. Если это староста, заместитель и казначей — вариантов $A_{15}^3=2730$, мы посчитали это в прошлом уроке.

А если это просто трое дежурных, без должностей? Тогда наборы «Аня, Боря, Вера» и «Вера, Аня, Боря» — один и тот же вариант, а формула размещений посчитала их как разные.

Вопрос урока: на сколько именно завышает ответ формула размещений — и какая формула считает выбор без порядка?

◎ После урока ты сможешь

• выводить формулу числа сочетаний из числа размещений
• вычислять C(n, k) короткими сокращениями, а не через полные факториалы
• пользоваться симметрией C(n, k) = C(n, n − k) и правилом треугольника Паскаля
• применять сочетания к подсчёту вероятностей и подмножеств

Прогноз до вычислений

1. Каких вариантов больше: троек с должностями или троек дежурных? Во сколько раз?
2. Что больше: $C_{20}^{2}$ или $C_{20}^{18}$?
3. Сколько подмножеств у множества из трёх элементов? Перечисли их и запомни число.

От размещений к сочетаниям

Посчитаем тройки дежурных дважды и сравним.

Каждая тройка дежурных $\{A;B;V\}$ порождает ровно $3!=6$ размещений: $ABV$, $AVB$, $BAV$, $BVA$, $VAB$, $VBA$. Значит, размещений ровно в $3!$ раз больше, чем троек:

$A_{15}^3=C_{15}^3\cdot3!\quad\Longrightarrow\quad C_{15}^3=\frac{2730}{6}=455.$

∴ Число сочетаний

Сочетание из $n$ объектов по $k$ — это выбор $k$ объектов из $n$ без учёта порядка и без повторов. Число сочетаний обозначают $C_n^k$, и

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

Частные случаи: $C_n^0=C_n^n=1$, $C_n^1=n$, $C_n^{n-1}=n$.

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

$C_{10}^3=\frac{10\cdot9\cdot8}{1\cdot2\cdot3}=\frac{720}{6}=120.$

Симметрия

✦ Выбрать k — то же самое, что отложить n − k

Каждому выбору $k$ объектов отвечает ровно один «остаток» из $n-k$ объектов, и наоборот. Значит,

$C_n^k=C_n^{\,n-k}.$

Это не только красиво, но и полезно: $C_{20}^{18}$ считать через $18$ множителей мучительно, а через симметрию — мгновенно:

$C_{20}^{18}=C_{20}^{2}=\frac{20\cdot19}{2}=190.$

Треугольник Паскаля

Выпишем числа $C_n^0, C_n^1, \ldots, C_n^n$ строками, начиная с $n=0$:

$1$ $1\quad 1$ $1\quad 2\quad 1$ $1\quad 3\quad 3\quad 1$ $1\quad 4\quad 6\quad 4\quad 1$

По краям стоят единицы, а каждое внутреннее число равно сумме двух чисел над ним.

∴ Правило треугольника и сумма строки

Для $1\le k\le n-1$ выполняется правило Паскаля:

$C_n^k=C_{n-1}^{\,k-1}+C_{n-1}^{\,k}.$

Объяснение без вычислений: отметим один объект. Наборы из $k$ объектов делятся на два непересекающихся случая — отмеченный объект взят (тогда остальные $k-1$ выбираем из $n-1$) или не взят (тогда все $k$ выбираем из $n-1$). Дальше работает правило суммы.

Сумма всех чисел строки равна числу подмножеств:

$C_n^0+C_n^1+\ldots+C_n^n=2^n.$

Каждый элемент либо входит в подмножество, либо нет — это $n$ независимых шагов по $2$ варианта.

Управляемый эксперимент

Найди в треугольнике клетку $C_n^k$, её зеркального двойника $C_n^{\,n-k}$ и две клетки, из которых она получилась сложением.

Лаборатория выбора

Треугольник Паскаля и три формулы подсчёта

Выбери, что считаем, задай n и k — и посмотри, где ответ живёт в треугольнике. Числа строки с номером n — это в точности C(n, 0), C(n, 1), …, C(n, n).

строка 6

Сочетания C(n, k)Размещения A(n, k)Перестановки n!

Сколько всего объектов, n 6От 1 до 12; стрелки клавиатуры меняют n на 1.

Сколько выбираем, k 2От 0 до 6: выбрать больше, чем есть, нельзя.

Вопрос: сколькими способами можно выбрать 2 предмета из 6, если порядок внутри выбора не важен?

Три величины для одних и тех же n и k

Величина	Как считается	Значение
P6 = 6!	1 · 2 · … · 6	720
A(6, 2)	6 · 5	30
C(6, 2)	A(6, 2) : 2!	15

=

C(6, 2) = 6! : (2! · 4!) = 15.Симметрия: C(6, 2) = C(6, 4) — выбрать 2 значит отложить 4. Правило треугольника: 5 + 10 = 15. Сумма всей строки равна 64 — столько у множества из 6 элементов подмножеств.

↺ Вернуть пример

Проверь на числах: $C_6^2=15$, симметричная клетка $C_6^4$ содержит то же число, а над клеткой стоят $C_5^1=5$ и $C_5^2=10$; их сумма равна $15$. Сумма всей шестой строки равна $2^6=64$.

Команда из двух группРазбираем вместе

В классе $12$ юношей и $15$ девушек. Нужно собрать команду: $2$ юноши и $2$ девушки.

Порядок внутри группы не важен, поэтому считаем сочетания:

$C_{12}^2=\frac{12\cdot11}{2}=66,\qquad C_{15}^2=\frac{15\cdot14}{2}=105.$

Выбор идёт за два шага, и число вариантов второго шага не зависит от первого, поэтому работает правило произведения:

$66\cdot105=6930.$

Обрати внимание на сочетание правил: внутри группы — сочетания, между группами — умножение.

Лотерея «5 из 36»Разбираем вместе

Игрок отмечает $5$ номеров из $36$; порядок отметок не важен. Всего вариантов

$C_{36}^5=\frac{36\cdot35\cdot34\cdot33\cdot32}{1\cdot2\cdot3\cdot4\cdot5}=376\,992.$

Все билеты одинаково возможны, поэтому вероятность угадать все пять номеров равна

$P=\frac{1}{376\,992}\approx0{,}0000027.$

Полезно перевести это в понятную величину: если заполнять по одному билету в день, на перебор всех вариантов уйдёт больше тысячи лет.

Проверка понимания

Сколькими способами из 10 человек можно выбрать 3 в жюри (никаких должностей нет)?

• А. 720
• Б. 120
• В. 30

Типичная ошибка

! Забыли разделить на k! — или разделили лишний раз

«Из $10$ человек выбираем троих: $10\cdot9\cdot8=720$». Это ответ для задачи с должностями. Без должностей нужно ещё разделить на $3!$: получится $120$.

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

Есть и третья ловушка: делить на $k!$ в задачах, где объекты повторяются. Формула $C_n^k$ выведена для выбора без повторов; например, к задаче «сколько трёхзначных чисел из цифр $1$–$5$ с повторами» она отношения не имеет.

Контрольный вопрос всегда один: различает ли задача порядок внутри выбранного набора?

Практика

1. Вычисли $C_7^2$, $C_{10}^3$, $C_9^9$, $C_{12}^1$.
2. Найди $C_{20}^{18}$, не выписывая восемнадцати множителей.
3. Выпиши пятую строку треугольника Паскаля и проверь, что сумма её чисел равна $2^5$.
4. Из $15$ учеников выбирают $3$ дежурных. Сколько вариантов? А если это староста, заместитель и казначей?
5. Сколько диагоналей у выпуклого десятиугольника?
6. В турнире $12$ команд, каждая играет с каждой по одному разу. Сколько матчей?
7. Сколько пятикарточных наборов можно выбрать из колоды в $36$ карт?
8. В классе $12$ юношей и $15$ девушек. Сколькими способами выбрать $2$ юношей и $2$ девушек?
9. Сколько всего подмножеств у множества из $8$ элементов? Сколько среди них ровно трёхэлементных?
10. Реши уравнение $C_n^2=28$.
11. Проверь правило Паскаля для числа $C_7^3$.
12. В лотерее нужно угадать $5$ номеров из $36$. Какова вероятность угадать все пять?
13. Среди $10$ учеников трое — отличники. Сколькими способами выбрать команду из $4$ человек так, чтобы в ней был хотя бы один отличник?

Ответы и пояснения

1. $C_7^2=\dfrac{7\cdot6}{2}=21$; $C_{10}^3=\dfrac{10\cdot9\cdot8}{6}=120$; $C_9^9=1$; $C_{12}^1=12$.
2. По симметрии $C_{20}^{18}=C_{20}^{2}=\dfrac{20\cdot19}{2}=190$.
3. $1,\;5,\;10,\;10,\;5,\;1$; сумма равна $32=2^5$.
4. Дежурные: $C_{15}^3=\dfrac{15\cdot14\cdot13}{6}=455$. Должности: $A_{15}^3=2730$, что ровно в $3!=6$ раз больше.
5. Отрезков между вершинами $C_{10}^2=45$, из них $10$ — стороны. Диагоналей $45-10=35$.
6. $C_{12}^2=\dfrac{12\cdot11}{2}=66$ матчей.
7. $C_{36}^5=376\,992$.
8. $C_{12}^2\cdot C_{15}^2=66\cdot105=6930$.
9. Всего подмножеств $2^8=256$; трёхэлементных $C_8^3=\dfrac{8\cdot7\cdot6}{6}=56$.
10. $\dfrac{n(n-1)}{2}=28$, то есть $n^2-n-56=0$, откуда $n=8$ (корень $n=-7$ не подходит).
11. $C_7^3=\dfrac{7\cdot6\cdot5}{6}=35$, а $C_6^2+C_6^3=15+20=35$. Правило выполняется.
12. $P=\dfrac{1}{376\,992}\approx0{,}0000027$.
13. Через противоположный случай: всего команд $C_{10}^4=210$, команд без отличников $C_7^4=C_7^3=35$. Ответ: $210-35=175$.

Итог

• $C_n^k=\dfrac{A_n^k}{k!}=\dfrac{n!}{k!\,(n-k)!}$ — число способов выбрать $k$ объектов из $n$, если порядок не важен.
• Считай по короткой записи: $k$ убывающих множителей сверху, $k!$ снизу.
• Симметрия $C_n^k=C_n^{\,n-k}$ экономит вычисления, а правило Паскаля $C_n^k=C_{n-1}^{\,k-1}+C_{n-1}^{\,k}$ строит весь треугольник сложением.
• Сумма строки равна $2^n$ — числу всех подмножеств $n$-элементного множества.
• Задачи «хотя бы один» почти всегда короче считать через противоположный случай.

Дальше числа $C_n^k$ окажутся не только счётом наборов: они станут множителями в формуле вероятности для серии одинаковых независимых испытаний.

← Перестановки и размещения · Дальше: схема Бернулли →

Закончил урок?

Отметь прогресс — регистрация не нужна.

Отметить пройденным