Калькулятор перестановок, размещений и сочетаний

В классе двадцать пять человек, и каждое утро решаются три похожие, но разные задачи: кого назначить парой дежурных, кому вести журнал вместе с заместителем и в каком порядке класс пойдёт к доске. Задачи кажутся одинаковыми — «выбрать из 25», — но ответы разные: пар дежурных получается 300, вариантов пары «староста плюс заместитель» — 600, а очередей из всего класса больше, чем атомов в горном массиве. Разница в двух вопросах: выбираем мы всех или только часть, и важен ли порядок внутри выбора. Раздел математики, который отвечает на такие вопросы, называется комбинаторикой, и калькулятор выше считает все три ответа за секунду — а ниже разберём, откуда берутся его формулы и почему они работают. Само слово происходит от латинского combinare — «соединять»: мы комбинируем элементы набора и считаем, сколько разных соединений можно собрать.

Три главных расчёта: все или часть, важен ли порядок

Комбинаторика различает три ситуации. Перестановки $P_n$ — расстановки всех n предметов в ряд: очередь к доске, порядок фотографий в альбоме, порядок букв в анаграмме — берутся все предметы, и порядок важен. Размещения $A_n^k$ — упорядоченные выборки части предметов: «первое и второе место в забеге», «президент и вице-президент клуба» — берём k из n, и роли различаются. Сочетания $C_n^k$ — выборки без учёта порядка: дежурные, команда на сборы, набор конфет в пакет — спрашивают «кого», а не «в каком порядке». С тремя формулами школьники знакомятся в курсе алгебры, а уверенно применяют их на задачах ОГЭ и ЕГЭ. Отсюда простое правило выбора формулы: спрашивают про все предметы — это перестановки; про часть — смотри на порядок: важен — размещения, не важен — сочетания.

Перестановка P(n)#

Упорядочивание всех n предметов без повторений; ответ равен факториалу n!

Размещение A(n, k)#

Выбор k предметов из n с учётом порядка; формула n!/(n − k)!

Сочетание C(n, k)#

Выбор k предметов из n без учёта порядка; формула n!/(k!(n − k)!)

Факториал n!#

Произведение всех натуральных чисел от 1 до n; по соглашению 0! = 1

Внутри всех трёх формул живёт факториал — произведение всех натуральных чисел от 1 до n, которое записывают восклицательным знаком: $n!=1\cdot 2\cdot 3\cdots n$. По соглашению $0!=1$: пустое произведение считается единицей, и это не прихоть математиков — ровно один способ ничего не выбрать, поэтому формулы с нулём работают без оговорок. Растёт факториал пугающе быстро: $5!=120$, $10!=3628800$, а $25!\approx 1,55\cdot 10^{25}$ — столько очередей из 25 человек существует на свете, хотя людей на планете всего восемь миллиардов. Именно поэтому в калькуляторе n ограничено числом 170: факториал 171 уже не помещается в число двойной точности.

Правило умножения: фундамент всех формул

Прежде чем учить формулы, освоь правило умножения: если первый выбор можно сделать m способами, а второй — n способами независимо от первого, то пара выбирается m на n способами. Меню из трёх супов, четырёх вторых и двух напитков даёт $3\cdot 4\cdot 2=24$ обеда; четырёхзначный PIN-код — $10\cdot 10\cdot 10\cdot 10=10000$ вариантов; гардероб из трёх футболок и двух джинсов — шесть комплектов. Правило работает и в обратную сторону: если нужен вариант «или то, или это», способы складываются, а не умножаются. Из этого правила выводятся и все формулы комбинаторики: выбирая k предметов из n по одному, на первом шаге есть n кандидатов, на втором уже n − 1, и так до n − k + 1 — так рождается формула размещений.

Лотерея «5 из 36» и треугольник Паскаля

Классический пример сочетаний — числовая лотерея: билет «5 из 36» — это выбор пяти чисел из тридцати шести, и порядок выпадения бочонков ничего не решает. Всего комбинаций $C_{36}^5=\frac{36\cdot 35\cdot 34\cdot 33\cdot 32}{1\cdot 2\cdot 3\cdot 4\cdot 5}=376992$, поэтому шанс угадать все пять чисел одним билетом — один к 376 992, примерно как выбрать наугад одного конкретного жителя Астрахани. Если бы порядок был важен, вариантов стало бы в $5!=120$ раз больше: $A_{36}^5=45239040$. Считать такие числа вручную не нужно — калькулятор выдаёт их мгновенно; понимать же стоит, почему шанс так мал и как быстро он падает с каждым новым числом в билете.

Сочетания спрятаны и в треугольнике Паскаля — арифметической пирамиде, где каждое число равно сумме двух над ним. Если нумеровать строки с нуля, то n-я строка — это в точности $C_n^0,C_n^1,\dots ,C_n^n$: седьмая строка выглядит как 1, 7, 21, 35, 35, 21, 7, 1. Симметрия строки отражает симметрию сочетаний: $C_n^k=C_n^{n-k}$ — выбрать, кого взять с собой в поход, всё равно что выбрать, кто останется дома. Треугольник строится без всяких факториалов, одними сложениями, поэтому его удобно использовать как шпаргалку: пока n невелико, сочетание достаётся из пирамиды быстрее, чем считается по формуле. По строке заодно видно, как сочетания нарастают к середине и снова спадают к краям: самое большое число стоит ровно посередине.

Мостик к вероятности: комбинаторика на ЕГЭ

Классическая вероятность определяется как отношение числа благоприятных исходов к числу всех возможных, и в задачах с равновозможными исходами без комбинаторики не обойтись. Пример из колоды: из 36 карт достают три; всего способов $C_{36}^3=7140$, а способов достать три туза — $C_4^3=4$, значит вероятность равна $\frac{4}{7140}\approx 0,00056$. Такие конструкции — основа заданий на вероятность в ЕГЭ: сначала считаем общее число исходов сочетаниями, потом благоприятное, потом делим. Важно честно применять правило «порядок не важен» к обеим дробям: если в числителе сочетания, то и в знаменателе должны быть сочетания — смешение формул даёт неверный ответ.

Комбинаторика разошлась далеко за пределы экзаменов. В информатике число перестановок оценивает стойкость паролей: восьмизначный код без ограничений — миллиарды вариантов для перебора. В генетике правило умножения даёт решётку Пеннета и расщепление 9:3:3:1. В химии сочетаниями считают, сколькими способами атомы занимают позиции в молекуле, в логистике — варианты распределения смен и маршрутов. Формулы при этом остаются теми же тремя, что и в школьной тетради: $P_n=n!$, $A_n^k=\frac{n!}{(n-k)!}$, $C_n^k=\frac{n!}{k!(n-k)!}$. Введи в калькулятор условие своей задачи, сверь пошаговое решение с ручным — и выбор формулы станет рефлексом.