"Сколькими способами можно..." Так начинаются задачи из области комбинаторики, то есть задачи на подсчет числа вариантов. Часто (хотя и не всегда) из маленьких исходных чисел получаются огромные, астрономические ответы. Это явление носит название "экспоненциальный взрыв" и мы с ним уже сталкивались. Иногда это на пользу, например в криптографии. Всё на виду, но вариантов перебрать надо многовато. Впрочем, обо всем по порядку. Цель заметки - собрать все основные формулы (вот редко когда они действительно все присутствуют) и показать, хоть примерно, откуда они берутся. И иллюстрировать я буду примерами игривыми и/или хулиганскими: я предупредил.
Итак, начнем с перестановок. Дано n предметов, их нужно расставить в разном порядке. Сколькими способами это можно сделать?
У вас есть семь подруг, каждую ночь вы проводите с другой. Сколько у вас может быть разных недель, когда расписание встреч не повторялось ни разу? Можно ли за год ни разу не повторять недельное расписание? А за десять лет? А за сто?
Решением является факториал: произведение всех чисел от 1 до данного числа. Обозначается он восклицательным знаком: n!. Доказательство очень просто и опирается на индукцию. В самом деле, если у вас один предмет (одна подруга), то и вариант один. Если же для n предметов формула верна, то для n+1 тоже, так как вы можете выбрать перестановку n предметов и потом в любую из n+1 позиций (перед первым или после любого из n) всунуть еще один предмет. Получается, что на каждую из n! перестановок приходится n+1, что и дает (n+1)!.
Факториал быстро растет. Быстрее экспоненты. Так что число перестановок даже для скромных n очень велико. Так, 5!=120, 6!=720, 7!=5040. То есть число недель с уникальным расписанием ночей больше пяти тысяч. В году 52 недели (и еще день-два), так что получается около 96 лет. Ста точно хватит. Десяти - точно нет.
Вот еще пример. В русском языке свободный порядок слов, то есть основной смысл фразы, как правило, сохраняется. Но тонкости есть, их через порядок слов (в том числе) и передают. Например, из фразы "я люблю тебя" можно составить 3!=6 фраз перестановкой слов, и у всех немного разное звучание. Смотрим:
Я люблю тебя. Я тебя люблю. Тебя люблю я. Тебя я люблю. Люблю тебя я. Люблю я тебя.
Ну и, в общем-то, шестерым можно честно говорить, что такую фразу ты никому до нее не говорил.
Итальянцам с их te amo сложнее, ну им красивостей наплести несложно. Нам, в общем-то, тоже.
Теперь заметим, что по сути мы выбирали упорядоченные наборы из n предметов из n возможных без повторения. А что, если выбирать меньше? То есть, есть N предметов, надо выбрать n, причем порядок важен. Сколько есть вариантов?
У красотки есть 10 поклонников, она желает ходить в кино в четыре раза в неделю, каждый раз с другим. Сколько недель будет иметь уникальное расписание встреч? На десятилетие хватит? А на век?
Понятно, что рассуждение то же самое. Можно упорядочить все N предметов (N! вариантов), но только порядок первых n важен, остальные все равно не участвуют. А их N-n штук, и перестановок у них (N-n)!. Все такие перестановки можно объединить в одну, так что ответ
N! / (N-n)!
Это число называется почему-то число размещений и оно тоже довольно быстро растет. По сути, нам надо перемножить все числа от N-n+1 до N. А не вычислять факториалы и потом делить! (Формально можно и так, но вычислительно это очень затратно).
В частности, в задаче выше получим 10∙9∙8∙7=5040. Да, опять. За сто лет красавица справится. За десять - точно нет.
Теперь можно заодно уж рассмотреть число вариантов без учета порядка. То есть предметов N, выбрать надо n, повторяться нельзя, но порядок теперь роли не играет.
Это число сочетаний, оно же биномиальный коэффициент. Получается из предыдущей формулы делением на число перестановок: теперь все варианты, отличающиеся только порядком, идентичны. Получается
N! / (N-n)! / n!.
Это число может быть велико, но растет не так стремительно. В частности, для десяти поклонников и четырех вечерах в неделю получается всего-то 10∙9∙8∙7/(1∙2∙3∙4)=10∙3∙7=210. Недель. Это четыре года. Почти.
Пример. Сколько коктейлей из трех ингредиентов можно смешать, располагая десятью ингредиентами? Повторять нельзя (три ингредиента должны быть различны), порядок роли не играет, так и так придется смешать (но не взбалтывать). Делим 10! на (10-3)!, получаем 10∙9∙8; делим это на 1∙2∙3=6 и получаем 120.
Вернемся к проблемам красавиц. Если ей нужно расписание встреч, по 4 в неделю, выбор из 10 поклонников, порядок не важен - то это число сочетаний. Посмотрим на проблему с другой стороны: у нее имеется четыре ответа "да" и шесть ответов "нет", и надо их расположить различными способами в рядочек. Эту задачу мы решили. А если ответов больше двух?
Например, ответов три, в том числе "нет", "да, ужин при свечах", "да, завтрак в постели". Первых шесть, вторых два, третьих тоже два.
Формула аналогична. Если есть N предметов, их надо разложить по k коробкам, в каждой k(i) штук, то число вариантов получается делением N! на факториалы всех k(i). В случае с красавицей "коробок" три, количества заданы, делим 10! на 6! и два раза на 2!=2. Получаем 10∙9∙8∙7/4 = 10∙9∙2∙7, что равно 1260.
Теперь перейдем к выбору с повторами: когда можно предмет использовать два и более раз. Пусть дано n предметов и надо выбрать k из них, порядок не важен, и предмет можно использовать более одного раза.
Например, у вас семь подруг и вы хотите каждую ночь проводить с подругой (не обязательно с разными); сколько недель будут иметь различное расписание?
Это число называется числом сочетаний с повторениями и выражается через число сочетаний из n+k-1 по k. Ответ в задаче получается делением (7+7-1)!=13! на 7! и (13-7)!=5!, что дает
13∙12∙11∙10∙9∙8/(1∙2∙3∙4∙5)=13∙11∙9∙8=10296 недель.
Почти 200 лет.
Давайте разберем пример попроще, про пиццу. По акции большая скидка на пять видов пиццы. Вы хотите заказать две пиццы; сколько у вас вариантов? По формуле получается число сочетаний из 5+2-1=6 по 2, то есть 15. Проверим.
Ну, если пиццы разные, то это любая из пяти первая и любая из четырех оставшихся вторая, что дает 20 вариантов. Но нам не важен порядок, поэтому делим пополам: 1,2 и 2,1 это один и тот же вариант. Получается 10 вариантов. Теперь совпадающие варианты: их пять. Вот и 15 в целом.
А сколько всего способов выбрать две пиццы из пяти возможных, с учетом порядка, повторы допускаются? Это упорядоченный выбор с повторением. Первая любая, вторая тоже, третья тоже... получается степень. Пять в квадрате, 25 вариантов. Излишне говорить, что степень растет очень быстро.
И вот получается тот самый экспоненциальный взрыв в чистом виде! Нот всего семь, но мелодий из семи нот (семи подряд, каждая может быть любой из семи) имеется более 800 тысяч. Правда, не все одинаково хороши. Букв 33 (добавив пробелы, знаки препинания, цифры, пусть будет 50), но текстов из ста символов неимоверно много. В общем-то, в их числе всё, что было или будет написано.
Правда, есть другой интересный эффект: основная часть этого совершенно неинтересна. И это не исключение, это правило. Из текстов почти все бессмысленны, из вещественных чисел почти все невычислимы, из функций почти все разрывны (а то и неизмеримы, но тут есть тонкости).
В языке, как правило, есть избыточность, так что потеря или замена символа или даже слова, как правило, не приводит к утрате или подмене смысла. При сжатии информации избыточность устраняется, так что информация становится более уязвимой к повреждениям.
А что, если буквы повторяются? Скажем, сколько слов можно составить из букв слова "молоко"? Букв всего шесть, но три повторяются. Если мы считаем все "о" разными, то получаем 6!=720 вариантов. Но перестановки на множестве букв "о" роли не играют, так что варианты группируются по 3!=6. Делим и получаем 5!=120. Вот сколько слов можно составить, только вот осмысленное среди них, вроде как, только одно.
Можно посмотреть на эту задачу как на число сочетаний с повторами. У нас четыре предмета: м, о, л, к, и мы хотим взять одну м, три о, по одной л и к, что и дает (1+3+1+1)!/1!/3!/1!/1!=120.
Вернемся к перестановкам. Всего их n!, а сколько из них таких, что ни один предмет не остался на месте? Формула такая:
Это приблизительно равно n!/e и называется перестановки без совпадений или беспорядком.
Удачных вам перестановок!