Урок 5. Комбинаторика: учимся считать варианты

Математика

🎯 Что ты узнаешь

Правило суммы («или») и правило произведения («и») — два кита всех подсчётов.
Как рисовать дерево вариантов, чтобы ничего не пропустить.
Что такое перестановки и факториал n! (сколькими способами выстроить в ряд).
Как считать сочетания $C_{n}^{k}$ : выбор нескольких предметов, когда порядок неважен.
Хитрый приём «подсчёт двумя способами»: как рукопожатия помогают проверять формулы.
Метод «звёзды и палочки»: как раскладывать одинаковые предметы по коробкам.
Принцип дополнения: иногда проще посчитать «плохие» варианты и вычесть их.

📖 Разбираемся в теме

Вопрос на засыпку: сколькими способами можно перетасовать обычную колоду из 52 карт? Ответ настолько огромен, что в него трудно поверить: число с 68 нулями. Это больше, чем число атомов во всей нашей Галактике. А значит, скорее всего, КАЖДЫЙ раз, когда кто-то хорошо тасует колоду, получается порядок карт, который не выпадал НИ РАЗУ за всю историю человечества. Как такое вообще можно посчитать, не перебирая варианты? Этим и занимается комбинаторика — наука считать, не пересчитывая.

Главная мысль всей комбинаторики простая: вместо того чтобы перечислять все варианты по одному, мы ищем способ их сосчитать сразу. Как кассир в магазине не пересчитывает деньги по одной монетке, а раскладывает их стопками и умножает. Дальше мы соберём несколько таких «стопок»-приёмов, и ты увидишь, что почти любая задача — это комбинация из них.

Правило произведения («и»)

Представь: утром ты выбираешь футболку (их у тебя 3) и шорты (их 2). Сколько разных нарядов получится? Для каждой из 3 футболок есть 2 варианта шорт: 3·2 = 6 нарядов.

Правило произведения. Если первое действие можно сделать a способами, и для каждого из них второе действие можно сделать b способами, то оба действия вместе можно сделать a·b способами.

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

Почему именно умножаем, а не складываем? Разложи наряды в таблицу: 3 строки (футболки) и 2 столбца (шорты). Каждая клеточка — это один наряд. А сколько клеток в таблице $3 \times 2$ ? Ровно $3 \cdot 2 = 6$ . Умножение — это и есть «сколько клеток в прямоугольнике». Вот и вся тайна правила произведения.

💡 Лайфхак: Если сомневаешься, умножать или складывать, спроси себя: «Я делаю оба действия вместе (И) или выбираю одно из двух (ИЛИ)?» Наряд — это футболка И шорты, оба сразу → умножаем.

Правило суммы («или»)

Теперь другое. У тебя на полке 3 книги про космос и 4 книги про динозавров. Сколько способов взять одну книгу? Можно взять про космос (3 способа) ИЛИ про динозавров (4 способа): 3 + 4 = 7.

Правило суммы. Если есть две группы вариантов, не пересекающиеся между собой, и в первой a вариантов, а во второй b, то всего вариантов a + b.

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

⚠️ Осторожно: Правило суммы работает, только если группы НЕ пересекаются. Если бы одна книга была и про космос, и про динозавров (например, «Динозавры на Марсе»), мы бы посчитали её дважды и ошиблись. Тогда её надо вычесть один раз: это называется принципом включения-исключения, но об этом как-нибудь потом.

📌 Запомни: «и» → умножаем, «или» → складываем. Это самый частый компас в комбинаторике. Прочитал условие, нашёл в нём «и» или «или», и сразу понятно, что делать со способами.

Дерево вариантов

Когда хочется всё «увидеть», рисуют дерево. От стартовой точки рисуют ветки — варианты первого действия. От каждой ветки — варианты второго действия, и так далее. Число «листьев» (концов веток) и есть число всех комбинаций.

Например, бросаем монетку дважды. Первый бросок: О или Р (две ветки). От каждой — снова О или Р. Получается 2·2 = 4 листа: ОО, ОР, РО, РР. Дерево заодно показывает, чему равны все варианты, и это удобно для проверки.

Рис. 1. Дерево бросков монетки: 2 · 2 = 4 листа

Дерево — это не просто картинка, а «правило произведения в лицах». От старта выходит 2 ветки, от каждой ещё по 2, вот тебе и $2 \cdot 2$ . Если бы монетку бросили три раза, было бы $2 \cdot 2 \cdot 2 = 8$ листьев. Дерево незаменимо, когда вариантов немного и хочется быть уверенным, что ничего не потерял.

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

Сколькими способами 3 ребёнка (Аня, Боря, Витя) могут встать в очередь?

На первое место — любой из 3 (3 способа).
На второе место — любой из 2 оставшихся (2 способа).
На третье — последний оставшийся (1 способ).

По правилу произведения: 3·2·1 = 6 способов.

Произведение всех чисел от 1 до n называют факториалом и обозначают n! (читается «эн факториал»):

n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n .

Например: 3! = 6, 4! = 24, 5! = 120. Растёт очень быстро!

🤔 А знаешь ли ты? Тот самый невероятный ответ про колоду из начала урока — это и есть факториал 52! (число способов выстроить 52 карты в ряд). Факториал растёт так бешено, что уже 13! больше шести миллиардов. Поэтому-то полностью перебрать все варианты в больших задачах не может даже суперкомпьютер, и приходится считать с умом.

Перестановки. Число способов выстроить n различных предметов в ряд равно n!.

📌 Запомни: Заметь удобное свойство: $n! = n \cdot (n - 1)!$ . Например, $5! = 5 \cdot 4!$ . Это значит, что каждый следующий факториал получается из предыдущего простым умножением: не нужно каждый раз считать всё произведение заново.

Сочетания: когда порядок неважен

Иногда нам не важен порядок. Например: из 4 друзей нужно выбрать 2 в команду. Команда {Аня, Боря} — это та же команда, что {Боря, Аня}. Порядок не считается!

Тут нельзя просто перемножать, потому что мы посчитаем одни и те же команды по нескольку раз. Идея-спасение: посчитать с учётом порядка, а потом поделить на число лишних повторов.

Посчитаем с порядком: первого выбираем 4 способами, второго — 3 способами, итого $4 \cdot 3 = 12$ упорядоченных пар. Но каждую команду из 2 человек мы так посчитали $2! = 2$ раза (Аня-Боря и Боря-Аня). Делим: $12/2 = 6$ команд.

Число способов выбрать k предметов из n, когда порядок неважен, обозначают $C_{n}^{k}$ (читается «цэ из n по k» или «биномиальный коэффициент n по k»). Для вычисления используется формула:

C_{n}^{k} = \frac{n !}{k ! \cdot ( n - k )!} .

Здесь $n!$ — все перестановки предметов, $k!$ убирает лишний порядок среди выбранных, а $(n - k)!$ — среди оставшихся. На практике то же самое считают короче: сверху пишут $k$ убывающих множителей от $n$ , снизу — $k!$ . Это одно и то же, ведь $n \cdot (n - 1) \cdot \dots (k множителей) = \frac{n !}{( n - k )!}$ .

Для нашего примера: $C_{4}^{2} = \frac{4 \cdot 3}{2 !} = \frac{12}{2} = 6$ . Сходится!

💡 Лайфхак: Число множителей сверху и снизу одинаковое. Хочешь $C_{n}^{k}$ ? Пиши сверху k чисел вниз от n ( $n, n - 1, \dots$ ), а снизу — k чисел вверх от 1 ( $1, 2, \dots, k$ ). Например $C_{6}^{3} = \frac{6 \cdot 5 \cdot 4}{1 \cdot 2 \cdot 3} = \frac{120}{6} = 20$ .

Приятное свойство симметрии. Выбрать 2 предмета из 4, которые берём, — то же самое, что выбрать 2 предмета, которые НЕ берём. Поэтому $C_{4}^{2} = C_{4}^{2}$ ; а вот $C_{6}^{4} = C_{6}^{2} = 15$ . В общем виде:

C_{n}^{k} = C_{n}^{n - k} .

Это часто спасает от долгих вычислений: считай ту сторону, где чисел меньше.

Подсчёт двумя способами (и рукопожатия)

Есть красивый приём: посчитать одну и ту же величину ДВУМЯ разными способами. Раз это одна и та же величина, ответы обязаны совпасть, и это либо даёт формулу, либо проверяет её.

Классика — задача про рукопожатия. На встрече 6 друзей, и каждый пожал руку каждому по одному разу. Сколько было рукопожатий?

Способ 1 (через сочетания). Рукопожатие — это выбор пары из 6 человек, порядок неважен (я пожал тебе руку = ты пожал мне). Значит, $C_{6}^{2} = \frac{6 \cdot 5}{2} = 15$ .

Способ 2 (посчитаем «руки»). Каждый из 6 человек пожал руку 5 другим, получается $6 \cdot 5 = 30$ . Но так каждое рукопожатие посчитано дважды (по разу с каждой стороны), поэтому делим на 2: $30/2 = 15$ .

Оба способа дали 15. Отлично, формула работает! Кстати, отсюда общая формула: число рукопожатий среди n человек равно $C_{n}^{2} = \frac{n ( n - 1 )}{2}$ .

Рис. 2. 6 друзей, каждый с каждым: 15 линий-рукопожатий

🤔 А знаешь ли ты? Эти числа — 1, 3, 6, 10, 15, 21… — называются треугольными, потому что из стольких кружочков складывается треугольник (как шары в бильярдной пирамиде). И число рукопожатий среди n человек — всегда треугольное число!

Звёзды и палочки

Как посчитать, сколькими способами разложить одинаковые предметы по коробкам? Тут блестяще работает приём «звёзды и палочки».

Задача: у нас 4 одинаковые конфеты (звёздочки ★), их надо раздать 3 детям (кому-то может не достаться ни одной). Сколькими способами?

Хитрость: выложим 4 звёздочки в ряд и поставим 2 палочки-перегородки, которые делят ряд на 3 части (первому — до первой палочки, второму — между палочками, третьему — после второй). Например:

⋆ ⋆ ∣ ⋆ ∣ ⋆ это 2, 1, 1

⋆ ⋆ ⋆ ⋆ ∣ ∣ это 4, 0, 0

Каждая раскладка конфет — это своя расстановка звёзд и палочек! Всего в ряду $4 + 2 = 6$ значков, и надо выбрать, на каких 2 местах из 6 стоят палочки. А это сочетания: $C_{6}^{2} = 15$ .

💡 Лайфхак: Общее правило: чтобы разложить n одинаковых предметов по k коробкам, ставим $k - 1$ палочку среди n звёзд, всего $n + k - 1$ значков, и выбираем места для палочек: $C_{n + k - 1}^{k - 1}$ . Но запоминать формулу не обязательно, важнее понять сам фокус со звёздами и палочками.

Принцип дополнения

Иногда посчитать «то, что нужно», трудно, а вот «всё минус ненужное» — легко. Это и есть принцип дополнения:

(хорошие) = (всего) - (плохие) .

Пример: сколько трёхзначных чисел содержат ХОТЯ БЫ одну цифру 7? Считать «хотя бы одну» напрямую муторно: 7 может стоять в одном разряде, в двух, во всех трёх… Легче наоборот.

Всего трёхзначных чисел: от 100 до 999, это $900$ штук.
Чисел БЕЗ единой семёрки: первая цифра — из 1–9 без 7, это 8 вариантов; вторая — из 0–9 без 7, это 9; третья — тоже 9. Итого $8 \cdot 9 \cdot 9 = 648$ .
Значит, с хотя бы одной семёркой: $900 - 648 = 252$ .

📌 Запомни: Слова «хотя бы один», «не менее одного», «есть среди них» — почти всегда сигнал: считай через дополнение. Найди «всего» и вычти «ни одного».

✍️ Разбор примеров

Пример 1. Сколько двузначных чисел можно составить из цифр 1, 2, 3, если цифры можно повторять? А если повторять нельзя?

Как рассуждаем. Двузначное число — это «первая цифра И вторая цифра». Видишь «И»? Значит, работает правило произведения.

С повторениями: первую цифру выбираем из {1,2,3} — 3 способа; вторую тоже из {1,2,3} — снова 3 способа. Итого 3·3 = 9. (Это 11, 12, 13, 21, 22, 23, 31, 32, 33.)

Без повторений: первую цифру выбираем 3 способами, а вторую — уже из 2 оставшихся (одну цифру использовали). Итого 3·2 = 6. (Это 12, 13, 21, 23, 31, 32.)

Ответ: 9 с повторениями, 6 без повторений.

Пример 2. В сетке нужно пройти из левого нижнего угла A в правый верхний угол B, двигаясь только вправо или вверх по линиям. Сетка 2×2 клетки. Сколько разных маршрутов?

⏱ Попробуй сам прямо сейчас: нарисуй сетку 2×2 и впиши в каждый узел, сколькими путями в него можно попасть. Потом читай дальше.

Как рассуждаем. Чтобы попасть из A в B по сетке 2×2, нужно сделать 2 шага вправо (П) и 2 шага вверх (В), всего 4 шага в каком-то порядке. Каждый маршрут — это последовательность из двух букв П и двух букв В, например ППВВ или ПВПВ.

Удобно считать по-другому, через клетки (метод подсчёта путей): в каждый узел сетки впишем число путей, которыми в него можно прийти. В нижний ряд и левый столбец — везде по 1 способу (идти только прямо). А в любой внутренний узел приходим либо снизу, либо слева, поэтому число путей в него = сумма путей в узел слева и в узел снизу. Заполняя сетку, в углу B получим 6.

Рис. 3. В каждый узел вписано число путей; в углу B получается 6

Можно проверить перечислением: ППВВ, ПВПВ, ПВВП, ВППВ, ВПВП, ВВПП — ровно 6.

🤔 А знаешь ли ты? Тот же ответ даёт и формула сочетаний! Маршрут — это выбор, на каких 2 из 4 шагов мы идём вправо: $C_{4}^{2} = \frac{4 \cdot 3}{2} = 6$ . А числа в узлах сетки, если приглядеться, — это тот самый треугольник Паскаля, где каждое число равно сумме двух над ним. Одна задача — три разных взгляда, и все сходятся!

Ответ: 6 маршрутов.

Пример 3. Сколькими способами 5 детей могут встать в очередь?

Как рассуждаем. Это чистые перестановки 5 предметов. На первое место — 5 кандидатов, на второе — 4 оставшихся, потом 3, 2 и наконец 1. По правилу произведения: 5·4·3·2·1 = 5! = 120.

Ответ: 120 способов.

Пример 4. Сколько различных «слов» (любых буквосочетаний, не обязательно осмысленных) можно получить, переставляя буквы слова КОТ? А слова МАМА?

Как рассуждаем. В слове КОТ все три буквы разные. Значит, это обычные перестановки трёх букв: 3! = 6 (КОТ, КТО, ОКТ, ОТК, ТКО, ТОК).

А вот в МАМА есть повторы: две буквы М и две буквы А. Если бы все четыре буквы были разными, было бы 4! = 24 перестановки. Но из-за повторов многие из них выглядят одинаково. Две буквы М можно поменять местами, слово не изменится, это «лишний» множитель 2! = 2. То же с двумя А — ещё множитель 2! = 2. Поэтому настоящих разных слов: 4! / (2!·2!) = 24 / 4 = 6... проверим перечислением: МАМА, МААМ, ММАА, ААММ, АМАМ, АММА — да, ровно 6.

💡 Лайфхак: Когда среди элементов есть одинаковые, всегда действуй так: сначала посчитай, как будто все они разные (через факториал), а потом подели на факториал числа повторов каждого сорта. Этот приём «посчитал лишнее — поделил на повторы» спасает в куче задач.

Ответ: КОТ — 6 слов; МАМА — 6 различных слов.

Пример 5. Сколько существует трёхзначных чисел, у которых все три цифры разные?

Как рассуждаем. Строим число по разрядам, помня про правило произведения и про важную тонкость: первая цифра не может быть 0 (иначе число не трёхзначное).

Сотни (первая цифра): любая из 1–9, ноль нельзя — 9 вариантов.
Десятки (вторая цифра): любая цифра 0–9, кроме уже использованной в сотнях. Всего цифр 10, одну заняли — 9 вариантов (ноль здесь уже можно!).
Единицы (третья цифра): любая из 10, кроме двух уже использованных — 8 вариантов.

По правилу произведения: 9·9·8 = 648.

⚠️ Осторожно: Главная ловушка тут — начать с нуля. Всегда сначала разбирайся с самым «стеснённым» разрядом: здесь это сотни, у которых запрет на ноль. Если начать со свободной цифры, легко запутаться в подсчёте оставшихся.

Ответ: 648 чисел.

Пример 6. На полке стоят 4 разные книги. Сколькими способами можно выбрать 2 из них (порядок неважен: просто пара книг)?

Как рассуждаем. Сначала посчитаем С УЧЁТОМ порядка: первую книгу выбираем 4 способами, вторую — 3 способами из оставшихся, всего 4·3 = 12 упорядоченных пар. Но порядок нам неважен: пара (книга1, книга2) и (книга2, книга1) — это одна и та же пара книг. Значит, каждую пару мы посчитали ровно дважды. Делим на 2: 12 / 2 = 6.

Так считаются сочетания: считаем «как будто порядок важен», а потом делим на число перестановок выбранной группы (для 2 книг это 2! = 2). На языке формул это ровно $C_{4}^{2} = \frac{4 \cdot 3}{2} = 6$ . Перечислим для надёжности (книги A, B, C, D): AB, AC, AD, BC, BD, CD — ровно 6 пар.

Ответ: 6 способов.

Пример 7. В классе 12 человек: 7 девочек и 5 мальчиков. Сколькими способами выбрать команду из 3 человек, если в ней должна быть ровно 1 девочка и 2 мальчика?

Как рассуждаем. Команда собирается из двух частей: 1 девочка и 2 мальчика. Эти два выбора делаются вместе (нужна и девочка, И мальчики), а слово «И» — это правило произведения: посчитаем каждый выбор отдельно и перемножим.

Шаг 1. Выбираем 1 девочку из 7. Порядок тут ни при чём. Мы просто указываем, кто вошёл в команду, поэтому это сочетание:

C_{7}^{1} = \frac{7 !}{1 ! \cdot 6 !} = 7.

Что и логично: одну девочку из семи можно выбрать ровно 7 способами.

Шаг 2. Выбираем 2 мальчиков из 5. Команда — это набор, порядок в нём неважен (Петя и Вася — та же пара, что Вася и Петя), поэтому снова сочетание:

C_{5}^{2} = \frac{5 !}{2 ! \cdot 3 !} = \frac{5 \cdot 4}{2} = 10.

Шаг 3. Соединяем через «И». К каждой из 7 выбранных девочек подходит любая из 10 пар мальчиков. Значит, всего команд:

7 \cdot 10 = 70.

💡 Лайфхак: Задачи «выбери команду с условиями» почти всегда разбиваются на независимые выборы, соединённые словом «И». Считай каждый выбор через $C_{n}^{k}$ отдельно, а потом перемножай.

Ответ: 70 способов.

Пример 8. Сколько существует трёхзначных чисел, в которых есть хотя бы одна цифра 5?

Как рассуждаем. Слова «хотя бы одна» — сигнал считать через дополнение (принцип дополнения). Посчитаем «всего» и вычтем «ни одной пятёрки».

Всего трёхзначных чисел: от 100 до 999 — это $900$ штук.
Чисел без единой пятёрки считаем по правилу произведения, разряд за разрядом, а потом перемножаем:
- Сотни (первая цифра): ноль впереди трёхзначного числа не ставят, поэтому берём из 1–9 (это 9 цифр). Пятёрку брать нельзя, выкидываем её → остаётся 8 вариантов.
- Десятки (вторая цифра): годится любая из 0–9 (10 цифр), кроме пятёрки → 9 вариантов.
- Единицы (третья цифра): точно так же 9 вариантов.
Каждый разряд выбираем независимо от других, поэтому по правилу произведения перемножаем: $8 \cdot 9 \cdot 9 = 648$ чисел без пятёрки.
С хотя бы одной пятёркой: $900 - 648 = 252$ .

Ответ: 252 числа.

💡 Запомни главное

«И» — перемножаем варианты (правило произведения). «ИЛИ» — складываем (правило суммы, если группы не пересекаются).

n! = 1·2·…·n — число способов выстроить n разных предметов в ряд (перестановки).
Когда выбираешь нескольких и порядок неважен (сочетания $C_{n}^{k}$ ): посчитай с учётом порядка, потом раздели на число перестановок выбранной группы. Формула: $C_{n}^{k} = \frac{n !}{k ! ( n - k )!} = \frac{n ( n - 1 ) \dots}{k !}$ (по k множителей сверху и снизу).
Полезные свойства сочетаний: $C_{n}^{k} = C_{n}^{n - k}$ (считай ту сторону, где чисел меньше); число рукопожатий среди n человек — $C_{n}^{2} = \frac{n ( n - 1 )}{2}$ .
Подсчёт двумя способами: считай одно и то же двумя путями; ответы обязаны совпасть, это лучшая проверка.
Звёзды и палочки — приём для раскладки одинаковых предметов по коробкам.
Принцип дополнения: «хотя бы один» → считай «всего» − «ни одного».
Если есть повторяющиеся одинаковые элементы, дели на факториал числа повторов каждого.
Первая цифра числа не может быть 0 — частая ловушка.
Сомневаешься, нарисуй дерево вариантов или перечисли маленький случай для проверки.

📝 Домашнее задание

В кафе 3 вида мороженого и 4 вида сиропа. Сколькими способами можно заказать одну порцию мороженого с одним сиропом?
Сколько трёхзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если цифры можно повторять?
Сколькими способами 6 человек могут сесть на 6 стульев в ряд?
Сколько различных «слов» можно получить, переставляя буквы слова КНИГА? А слова КОЛОБОК?
Из класса в 10 человек нужно выбрать двоих дежурных (оба равноправны, порядок неважен). Сколькими способами это можно сделать?
Сколько существует четырёхзначных чисел, все цифры которых разные?
В меню 2 первых блюда, 3 вторых и 2 десерта. Сколькими способами можно составить обед из одного первого, одного второго и одного десерта?
⭐ Сколькими способами можно разменять 10 рублей монетами достоинством 1, 2 и 5 рублей?