Три основные формулы
Комбинаторика отвечает на вопрос «сколькими способами?». Всё сводится к выбору из n элементов и двум вопросам: важен ли порядок и можно ли повторять элементы.
Перестановки P(n) = n! — все n различных элементов выстраиваются в ряд. Например, 5 человек можно рассадить на 5 стульях 5! = 120 способами.
Размещения A(n, k) = n!/(n − k)! — из n элементов выбирают k, порядок важен. Золото, серебро и бронзу среди 10 участников можно раздать 10·9·8 = 720 способами.
Сочетания C(n, k) = n!/(k!·(n − k)!) — из n элементов выбирают k, порядок не важен. Команду из 5 человек из 12 можно составить C(12, 5) = 792 способами. Сочетание получается из размещения делением на k!: каждый набор из k элементов учтён k! раз в разных порядках.
Повторения
Если элементы можно выбирать повторно, размещения с повторениями равны nᵏ: код замка из 4 цифр — 10⁴ = 10 000 вариантов. Сочетания с повторениями — C(n + k − 1, k): набор из 3 пирожных трёх видов можно выбрать C(5, 3) = 10 способами.
Если среди n элементов есть одинаковые (n₁ одного вида, n₂ другого и так далее), число различных перестановок равно n!/(n₁!·n₂!·…·n_m!). Так считают анаграммы: в слове «математика» 10 букв, из них м — 2, а — 3, т — 2, остальные по одной, поэтому 10!/(2!·3!·2!) = 151 200 слов.
Как отличить формулы
Спросите себя: если поменять элементы местами, получится другой результат? Если да — это размещения или перестановки, если нет — сочетания. Если выбираются все элементы — перестановки. Если один и тот же элемент можно взять снова — формулы с повторениями.
Большие числа
Числа в комбинаторике растут очень быстро: 20! уже больше двух квинтиллионов, а 100! содержит 158 цифр. Калькулятор считает точно, без округления, и разбивает цифры на группы для удобства чтения.
Связь с вероятностью
Классическая вероятность — это отношение числа благоприятных исходов к числу всех равновозможных. Оба числа чаще всего считают именно через сочетания, например шанс угадать 6 номеров из 49 равен 1/13 983 816.