🔀 Дискретка

Задачи на комбинаторику

Q: Насколько быстро растёт факториал и что делать с большими числами?

Стремительно: $10! = 3\,628\,800$, а $20!$ уже превышает $2 \cdot 10^{18}$ — больше, чем помещается в 64-битное целое. Поэтому в расчётах факториалы сокращают до умножения ($\frac{10!}{7!} = 10 \cdot 9 \cdot 8$), а не вычисляют по частям: это и быстрее, и не переполняет счёт.

Как отличить перестановки от размещений и сочетаний и не перепутать формулы: классификация подтипов, разбор пары задач, где решает одно слово «порядок», типичные ошибки и бесконечный генератор.

Сложность: Первый курс 5 уровней сложности бесконечный поток задач

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

Хорошая новость: почти вся учебная комбинаторика держится на двух вопросах. Первый — важен ли порядок? Второй — бывают ли повторения? Ответив на них, вы попадаете в одну из трёх формул: $n!$ , $A_{n}^{k}$ или $C_{n}^{k}$ . Плохая новость в том, что формулы студенты знают, а вот вопросы задать тексту задачи забывают — и решают сочетания там, где нужны размещения. Терминология собрана в размещениях и сочетаниях, алфавит обозначений — в термине факториал.

План страницы: таблица-распознавалка подтипов, разобранная пара задач, где всё решает одно слово, разбор типичных ошибок и встроенный тренажёр с задачами на перестановки, сочетания и размещения.

Отдельного упоминания заслуживает выборка с повторениями: если предметы после выбора возвращаются — цифры пароля, кнопки кодового замка — формула меняется. Упорядоченный выбор $k$ из $n$ с возвращением даёт $n^{k}$ : четырёхзначный код из десяти цифр — $1 0^{4} = 10000$ вариантов. Не возвращаем — работает $A_{n}^{k}$ , и тех же четырёх знаков останется $10 \cdot 9 \cdot 8 \cdot 7 = 5040$ . Разница между $10000$ и $5040$ — это разница между кодовым замком и надёжным кодовым замком.

Классификация: 5 подтипов#

Подтип	Как узнать	Метод решения
Перестановки	упорядочиваем все $n$ различных объектов целиком	$P_{n} = n!$ : пять книг на полке — $5! = 120$ способов
Размещения	выбираем $k$ из $n$ , порядок важен (медали, пароли, расписания)	$A_{n}^{k} = \frac{n !}{( n - k )!} = n (n - 1) \dots (n - k + 1)$
Сочетания	выбираем $k$ из $n$ , порядок не важен (дежурные, комиссии, руки)	$C_{n}^{k} = \frac{n !}{k ! ( n - k )!}$
Перестановки с повторениями	есть одинаковые предметы: буквы слова, шары двух цветов	$\frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}$ , где $n_{i}$ — размер каждой группы одинаковых
Правила суммы и произведения	в тексте стоят «или» и «и» между выборами	«или» — складываем варианты, «и» — умножаем

Два контрольных вопроса — «важен ли порядок?» и «есть ли повторения?» — выбирают формулу за вас

Разобранный пример#

В группе десять студентов. Вопрос а) сколькими способами можно выбрать трёх дежурных? Вопрос б) сколькими способами вручить троим золотую, серебряную и бронзовую медали? Числа и люди одни и те же, а ответы различаются в шесть раз — потому что в первом случае порядок не важен, а во втором важен.

Фиксируем данные: всего $n = 10$ человек, выбираем $k = 3$ .
Задача а: дежурные ничем не различаются между собой — тройка есть тройка. Порядок не важен, повторения невозможны: сочетания.
Считаем: $C_{10}^{3} = \frac{10 !}{3 ! \cdot 7 !} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120$ способов.
Задача б: медали разные — «первый, второй, третий» слушается порядка. Размещения без повторений.
Считаем: $A_{10}^{3} = 10 \cdot 9 \cdot 8 = 720$ вариантов.
Связь-проверка: $A_{10}^{3} = C_{10}^{3} \cdot 3! = 120 \cdot 6 = 720$ . Каждую тройку можно упорядочить $3!$ способами — поэтому размещений ровно в $k!$ раз больше.

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

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

мостик между сочетаниями и размещениями: упорядочить выбранное можно

k!

способами, поэтому

A

всегда больше

C

k!

раз

Правило произведения — двигатель всех трёх формул. Размещение $A_{n}^{k}$ — это $k$ последовательных выборов: у первого шага $n$ кандидатов, у второго $n - 1$ , и так до $n - k + 1$ ; перемножение шагов и даёт формулу. Сочетание получается делением на $k!$ — столько перестановок живёт внутри каждой группы. Понимание этого вывода страхует, когда формула забылась: достаточно выписать выборы по шагам и перемножить.

Типичные ошибки#

Сочетание принято за размещение. «Выбрать двух дежурных» — сочетание; «назначить старосту и заместителя» — размещение. Ищите в условии, различимы ли выбираемые роли.
Потерян $k!$ в знаменателе сочетаний. Формула $\frac{n !}{( n - k )!}$ без множителя $k!$ — это размещения, ответ получится в $k!$ раз больше правильного.
Правило произведения применено сложением. «Пиджак и брюки» умножаются; сложение оставлено для взаимоисключающих вариантов — «пиджак или пуловер».
Повторения не учтены. Перестановки букв слова «банан» — это $\frac{5 !}{2 ! 2 ! 1 !} = 30$ , а не $5! = 120$ : две «а» и две «н» неразличимы, и каждая расстановка посчитана в $2! \cdot 2!$ раз.
«Хотя бы один» считают перебором. Суммирование «ровно одна + ровно две + …» громоздко и проваливается на пропущенном случае; путь через дополнение короче и надёжнее.

Проверь себя+15 XP

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

Проверь себя+15 XP

Шесть спортсменов разыгрывают золото, серебро и бронзу. Сколько вариантов распределения медалей?

Тренируйся: встроенный тренажёр#

Практика качает главный навык темы — распознавание типа по тексту задачи, до всякой арифметики. Генератор на этой странице подбрасывает задачи по уровням: перестановки всех объектов (начальные уровни), затем сочетания «выбери дежурных», затем размещения «раздай медали». Отвечайте сначала вслух на два контрольных вопроса — порядок? повторения? — и только потом беритесь за формулу; разбор каждого решения покажет, где выбор свернулся не туда. Продолжить марафон можно в отдельном тренажёре по комбинаторике.

Частые вопросы

Чем сочетание отличается от размещения?

Порядком. Сочетание — просто группа выбранных объектов (дежурные, команда), размещение — упорядоченный выбор (медали, пароль, староста и заместитель). Числовой мостик: $A_{n}^{k} = C_{n}^{k} \cdot k!$ — каждую группу можно упорядочить $k!$ способами.

Как решать задачи «хотя бы один»?

Через противоположное событие: посчитайте варианты «ни одного» и вычтите из общего числа. Для «хотя бы один красный шар из трёх вытянутых» это $C_{n}^{3} - C_{n - k}^{3}$ , где $k$ — число красных. Такой путь короче перечисления «ровно один, ровно два, ровно три» и не теряет случаи.

Зачем комбинаторика в теории вероятностей?

Классическое определение вероятности — отношение числа благоприятных исходов к числу всех: $P = \frac{m}{n}$ . Оба числа — комбинаторные, поэтому задачи про карты, урны и лотереи начинаются с выбора формулы $A$ или $C$ . Без правильного знаменателя числитель бессмыслен.

Насколько быстро растёт факториал и что делать с большими числами?

Стремительно: $10! = 3628800$ , а $20!$ уже превышает $2 \cdot 1 0^{18}$ — больше, чем помещается в 64-битное целое. Поэтому в расчётах факториалы сокращают до умножения ( $\frac{10 !}{7 !} = 10 \cdot 9 \cdot 8$ ), а не вычисляют по частям: это и быстрее, и не переполняет счёт.

Что смотреть дальше#

Урок перестановки, размещения и сочетания — базовый блок дискретной математики.
Урок комбинаторика в курсе теории вероятностей — выборки как исходы.
Разбор как решать задачи на вероятность — куда комбинаторика превращается в вероятности.
Термин размещения и сочетания — формулы с расшифровкой и примерами.
Шпаргалка по комбинаторике — правила суммы и произведения, бином Ньютона, треугольник Паскаля.
Тренажёр по комбинаторике — бесконечный поток задач трёх типов с разбором.

Практика: встроенный тренажёр

+12 XP за верный ответ

Другие типы задач