Комбинаторика

Комбинаторика - это раздел математики, который отвечает на вопросы из серии "а сколькими способами ...", "сколько есть возможных вариантов", и тому подобные.

Комбинаторика несложный раздел математики, т.к. большую ее часть можно объяснить без предварительных знаний. Мы постоянно сталкиваемся с подобными задачами в жизни.

В этой статье мы познакомимся с основными понятиями комбинаторики:

• перестановки
• сочетания
• размещения
• биномиальные коэффициенты, бином Ньютона и треугольник Паскаля

Множества

Мы часто встречаем объекты, которые входят в группу по определенному признаку. Это может быть все что угодно - группа людей в классе, набор цветных ручек, числа кратные 2, стая гусей, набор букв. Всех их объединяет наличие какого-то признака, по которому все они входят в такую группу. Такие группы в математике называются множествами. Обычно множества обозначаются заглавными буквами (А, В, С), а элементы множества - маленькими буквами в фигурных скобках, например

• {красный, синий, зеленый} - множество цветов
• {2, 4, 6, 8} - множество натуральных чисел, меньше 10

Или с помощью некоторого определения, где символ | можно заменить на слово "которые", "такие что" и т.д. Например

• {цвета | присутствуют в радуге}
• {страны | находятся в Европе}

В общем виде множество выглядит так

Отношение порядка и упорядоченность

На множестве может быть задано отношение порядка. Простыми словами это означает следующее: возьмем 2 любые объекта из множества. Можем ли мы сказать, что первый элемент больше второго? Или что первый элемент не больше второго?

Если мы можем разместить все элементы множества в порядке от самого меньшего к самому большему, говорят что на множестве задан линейный порядок. Например, в множестве {1, 2, 5}. Если порядок задан только для некоторых элементов, то говорят что задан частичный порядок.

Здесь нам нужно только понять одну простую мысль. Множества мы можем рассматривать как набор элементов, в котором нам или важен порядок, или неважен.

Например, представим футбольную команду из 11 человек. Если мы захотим написать имена всех игроков в виде списка, нам не так важно, в каком порядке они будут перечислены. Но если мы скажем что на первом месте находится вратарь, на 2 - левый крайний защитник, на 3 - левый центральный защитник и т.д. - то порядок записи игроков важен, и это строгий порядок. А если мы скажем, что на 1 месте находится вратарь, на местах с 2 по 5 - защитники, с 6 по 9 - полузащитники и т.д. - то для нас важен порядок, но это частичный порядок. Неважно кто из защитников будет стоять на 2, а кто на 4 месте - главное чтобы они были на местах защитников.

Пример разбираемого множества

Все примеры будут приведены для множества 5-ти книг (довольно хороших, присмотритесь к ним). Вот они

• Архитектура компьютера (Э.Таненбаум, Т.Остин) - книга 1
• Алгоритмы. Руководство по разработке (Стивен Скиена) - книга 2
• Компьютрные сети. Нисходящий подход (Джеймс Куроуз, Кит Росс) - книга 3
• Код (Чарльз Петцольд) - книга 4
• Язык программирования С (Деннис Ритчи, Брайан Керниган) - книга 5

Для простоты я буду ссылаться на эти книги просто как на соответствующий номер книги от 1 до 5.

Правило суммы и произведения

Вы приходите в книжный магазин и видите на полке 5 книг, приведенных выше. Вы собираетесь купить 1 из них. Логично, что если у вас есть 5 книг и вы хотите купить одну из них у вас есть 5 различных вариантов. В общем случае, если у вас есть множество размера N (или мощности N, мощность - размер множества), то количество способов выбрать 1 предмет из N равен N.

Затем вы приходите в другой магазин, в котором есть все те же 5 книг, но на двух полках. На первой стоят полки 1, 2, 3, а на другой - 4 и 5. Заметим, что эти множества не пересекаются, т.е. каждая книга есть или на 1 полке, или на 2, но не на обеих. Тогда количество способов взять 1 книгу с полки 1 ИЛИ полки 2 - также 5, или (3+2). Это - правило суммы.

Но если вы захотите взять 2 книги - одну с первой, а вторую с 2 - то сколько тогда вариантов есть? На первой полке есть 3 книги и мы можем взять любую из 3-х, на второй любую из 2-х, но мы можем взять любую книгу с полки 1 для любой с полки 2 (и наоборот), т.е. всего вариантов - 6, или 3 * 2 (количество прямых). Это правило произведения.

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

Итак, мы купили все 5 книг, пришли домой и поставили их в ряд на полку с номерами от 1 до 5. Теперь представим, мы будем читать книги в соответствии с порядком, в котором они стоят - сначала архитектуру, потом алгоритмы, сети и т.д. Мы можем изменить порядок - например, начать с языка си и закончить архитектурой. Для этого нужно поменять местами книги с номерами 1 и 5. Такое изменение порядка называется перестановкой.

А сколько всего есть таких вариантов, или сколько существует перестановок для множества с 5-ю элементами?

Уберем с полки все книги и соберем их просто в кучу. Теперь у них нет порядка, никакая книга не является первой или последней. Нам нужно выбрать книгу на первое место. Для этого у нас есть 5 книг, т.е. на первом месте может быть любая. Как только мы выберем любую книгу - у нас останется 4 книги для 2-го места, значит на 2-е место на полке мы можем выбрать книгу 4-мя способами и, что важно, - 4-мя способами для каждого случая выбора первой книги, которых 5. Значит первые 2 книги мы можем выбрать 5 * 4 = 20 способами. Теперь у нас есть 3 книги, берем любую и для всех 20 способов мы можем выбрать любую из 3 - значит общее число 5 * 4 * 3 = 60. Для оставшихся 2 мы можем выбрать любую из 2 для каждого из 60 способов первых 3-х книг, общее число - 5*4*3*2 = 120. Последнюю книгу мы можем выбрать только 1 способом, т.е. тут у нас уже нет выбора, но можно сказать что для всех 120 способов расположить 4 книги у нас есть 1 способ расположить последнюю книгу, т.е. общее число способов - 5 * 4 * 3 * 2 * 1 = 120.

Для произвольного числа N количество перестановок равно N * (N-1) * (N-2) * ... * 2 * 1, и такое произведение называется факториалом числа. Обозначается факториал как N! (знак восклицания). Итак, число перестановок числа N равно факториалу этого числа.

На стоянке есть 10 свободных мест. К ней подъезжают 10 автомобилей. Сколькими способами автомобили могут занять свободные места? (Ответ: 10! или 3628800, т.к. первый автомобиль может занять любое из свободных 10 мест, второй автомобиль любое из оставшихся 9 не занятых и т.д.)

Перестановка с повторениями

Множество предполагает, что все его элементы различимы, но есть такое понятие как мультимножество. Чтобы не отдаляться в терминологию, предположим ситуацию - у нас вы пришли в магазин, в котором 5 книг, но книги по языку си и книги Петцольда нет, а по сетям 3 штуки (эти книги не различимы между собой).

Вопрос - сколько в таком случае вариантов переставить 5 книг?

Посмотрим на следующий пример. У нас есть 3 буквы(a, b, c). Мы можем переупорядочить их 6-ю (3!) способами.

Теперь заменим букву c на a и выделим ее красным цветом, чтобы мы все еще могли ее отличать. Можно заметить, что теперь некоторые комбинации дают одно и то же значение. Например, aba. Мы выделили красным цветом для наглядности, на самом деле и черная и красная a одинаковы. Из этого можно сделать вывод, что если 3 символа различны - то у нас есть 3! вариантов. А если 2 символа из 3-х одинаковы - то перестановка 2-х одинаковых букв местами не дает нового значения, значит нам нужно разделить общее число на число возможных перестановок одинаковых букв.

Чтобы лучше понять эту идею, возьмем те 3 одинаковые книги по сетям и пронумеруем их как A, B, C. Теперь они различимы. Предположим, что мы выбрали на 1 место книгу под номером 1, на 2- под номером 2, и осталось 3 книги по сетям. И вот как мы можем выбирать дальше. У нас есть 6 вариантов, но все эти варианты - одно и тоже, если все 3 книги А, В и С - неразличимы.

Поэтому мы делим общее число перестановок на количество перестановок каждого элемента среди таких же одинаковых элементов. В нашем случае мы получаем формулу

Сколько различных слов можно получить, переставляя буквы в слове МАТЕМАТИКА. Ответ: 151200, или 10!/2!3!2!1!1!1!, т.к. у нас 10 букв, 2 буквы М, 3 буквы А, 2 буквы Т и все остальные по 1 букве.

Размещения

Иногда нам нужно выбрать только несколько элементов k из множества, где k < N, т.е. размера множества.

Например, сколько есть способов выбрать 3 книги из 5?

На самом деле мы это уже делали. Первую книгу выбираем 5 способами, вторую - 4, третью - 3. На этом останавливаемся.

Размещения иногда называют m-перестановка из N. На самом деле, если N = k, такое размещение и есть перестановка.

Общая формула выглядит так (Обозначается сочетания обычно буквой А с индексом n внизу и k вверху).

Часто можно встретить такую формулу: мы сначала находим факториал n, а затем делим на факториал (n-k). На конкретном примере видно, что красные числа просто сокращаются и мы получаем верхнюю формулу.

В соревнованиях по бегу участвуют 10 спортсменов. Сколькими способами участники могут занять призовые (т.е. 1, 2 и 3) места? Ответ: 720. Первое место может занять любой участник из 10, второе - любой из 9, третье - любой из 8.

Размещения с повторениями

В прошлый раз при выборе элемента мы как бы "удаляли" его из множества. Для 5 элементов, как только мы выбрали элемент для 1-го места, на следующей позиции мы учитывали все элементы, кроме того, которого мы выбрали для 1-го места. Но что если мы не будем удалять выбранный элемент?

Тогда на 1 месте может находиться любой из N элементов, но на 2-ом месте мы также можем выбрать любой из N элементов, как и на 3-й позиции и т.д.

Это можно представить так: пусть у нас есть мешок с шариками 5-ти цветов. Нам нужно вытащить из мешка 3 шарика. Сначала у нас есть 5 возможных вариантов. После того как мы вытащили 1-й шар, в мешке останется 4 шара, и мы можем вытащить любой из 4-х. Но если мы вернем 1-й шар обратно в мешок, то шаров будет также 5.

В случае с книгами, представим ситуацию, что мы пришли в магазин в котором есть 5 различных книг, но количество экземпляров каждой книги больше 3. Нам нужно выбрать 3 книги в подарок 3-м своим друзьям. Это может быть 3 книги по алгоритмам, 2 по сетям и 1 по архитектуре, могут быть все книги разные. Главное, что для каждого из k друзей количество вариантов книг не уменьшается после приобретения 1 экземпляра.

Таким образом, выбрать k шаров/книг/элементов из множества размера N с повторениями мы можем N в степени k способами. Выбрать 3 книги из 5 с повторами можно 5 * 5 * 5 = 125 способами.

Автомобильный номерной знак состоит из буквы, з-х цифр и еще 2-х букв, например А123ВЕ. Цифра может быть любой от 0 до 9, но кроме номера 000, а буква любая из множества {А, В, Е, К, М, Н, О, Р, С, Т, У, Х}. Сколько существует всего номеров? Ответ: 1726272. Различных комбинаций чисел для номеров (10^3) - 1 = 999 (что логично, все кроме 000). Мощность множества допустимых букв = 12, нам нужно выбрать 3 буквы, повторы допускается, значит количество таких вариантов 12^3=1728. По правилу произведения находим ответ как 999*1728.

Сочетания

Сочетания очень похожи на размещения, но в них нам не важен порядок. В самом начале было объяснение про наличие порядка, и сейчас оно нам пригодится.

Пусть также выбираем 3 книги из 5. В прошлый раз мы выбирали их 3-м друзьям, а значит если мы выбрали книги 1, 3, 5 для 1-го, 2-го и 3-го друга, это не тоже самое, что выбрать книги 3, 5, 1. Каждый друг получит другую книгу, хоть вместе это тот же набор книг.

Когда мы говорим о сочетаниях, нас не интересует порядок. Если мы теперь захотим купить 3 книги из 5 для себя - то какая разница как мы их купим - 1, 3, 5 или 5, 3, 1 - они все равно окажутся у нас дома.

Когда нас интересует вопрос, а сколько есть вариантов выбрать подмножество из 3-х книг из 5, мы говорим о сочетаниях. Можно это запомнить так - когда нам важен порядок - это размещения (как будто мы начинаем считать: раз, два, три. Слово начинается на раз). Когда порядок неважен, а важны только сами элементы - это сочетания.

Вспомним как мы находили размещения. Возьмем тот же пример - 3 книги из 5. Пусть это будут книги 1, 3, 5. Тогда размещения {1, 3, 5}, {1, 5, 3}, {3, 5, 1}, {3, 1, 5}, {5, 1, 3}, {5, 3, 1} - все они соответствуют одному сочетания - множество из книг 1, 3 и 5.

Таким образом, если мы выбрали 3 книги, то мы можем задать на этом множестве порядок 3! (т.е. 6) способами. Но для сочетания порядок не важен. Значит нужно количество размещений поделить на количество перестановок для данного числа k, т.е. на k!.

Сочетания из n по k обозначаются буквой C с индексами n внизу и k вверху.

В итоге выбрать 3 книги из 5 без учета порядка можно 10 способами.

На остановке стоят 10 человек, всем им нужно добраться от остановки до пункта В. К остановке подъезжает автобус, который едет до этого пункта, но в автобусе только 3 свободных места. Трое случайных пассажиров садятся в автобус и добираются до нужного пункта. А сколько всего есть вариантов выбрать троих человек, которые поедут на данном автобусе? Ответ: 120, или 10!/(7!*3!), т.к. 10!/7! - число выбрать упорядоченное подмножество из 3-х человек, а неупорядоченное (они все едут в автобусе, порядок неважен) в 3! раза меньше.

Сочетания с повторениями

Сочетания с повторениями похожи на размещения с повторениями - элементы также могут повторяться. Эта формула имеет следующий вид: сочетания из n по k с повторениями равна сочетаниям из (n+k-1) по k (или n-1), но без повторений.

Сначала разберемся со следующей формулой

Здесь все логично. Мы выбираем из n k предметов. Пусть это будет 3 книги из 5. Но как только мы выбрали 3 книги, мы поделили множество из 5-ти книг на 2 - там где есть выбранные книги, и где их нет. Выбрать 3 книги из 5 для покупки это все равно что выбрать 2 книги, которые мы не будем покупать. Поэтому неважно, хотим мы выбрать k элементов, или n-k.

Чтобы понять, почему верна формула для сочетаний с повторениями, займемся решением следующей задачи. Вы приходите в магазин за своими 3-мя книгами из 5 (вас должно быть уже хорошо там знают), и хотите выбрать любые 3 книги из 5 себе в подарок. Но важное отличие от простого сочетания, которое мы выбирали в прошлый раз - вы можете выбрать и 3 одинаковые книги, и 2 одинаковые с 1 другой, и все разные книги. Т.е. книги могут повторяться, но порядок книг не важен: 1, 1, 2 и 2, 1, 1 - одно и тоже.

Чтобы понять принцип, решим сначала немного другую, но очень похожую задачу. Вы приходите в магазин и видите, что все книги, кроме 2, раскупили. Неважно какие 2 книги остались, пусть это будут просто А и В. Но экземпляров этих книг - очень много. Вам нужно взять 4 книги. Понятно, что вы не можете взять 4 разные книги - их всего 2. Вы можете выбрать любое количество книг А и любое количество книг В, но такое, чтобы в сумме они давали 4. Например, Это может быть АААА, ААВВ, АВВВ и т.д. Порядок в сочетаниях неважен, поэтому набор ААВВ и АВВА - один и тот же набор. Сколько у вас есть вариантов?

Т.к. порядок неважен, давайте сделаем следующее - сначала возьмем сколько-то книг А, а оставшиеся книги будут книги В. Как только мы выбрали количество книг А, разложим их в ряд и оставшиеся книги В разложим в ряд строго справа от А, и отделим их некоторым способом (в данном случае с помощью символа |). Мы получим следующие варианты: |BBBB, A|BBB, AA|BB, AAA|B, AAAA|B.

Заметим одну особенность. Каждый вариант состоит из 5 символов, в котором только 1 символ | (назовем этот символ перегородка), отделяющий книги типа А от типа В. Что в данном случае означает выбрать позицию перегородки - это выбор 1 символа из 5 возможных. Как только мы выбрали перегородку - слева книги типа А, справа - типа В и их число однозначно определяется позицией перегородки.

Усложним задачу. Пусть у нас есть 3 типа книг - А, В и С. Нам все также нужно выбрать 4 книги любого типа, порядок не важен. Значит результат можно записать как АААА, или ААВВ, АВСС и т.д. Причем результат АВСА и ААСВ - одно и тоже. Тогда мы всегда можем записать результат как число книг типа А, перегородка, число книг типа В, перегородка, число книг типа С. Для АВСА это будет выглядеть так - АА|B|C. Заметим, что мы можем даже не указывать тип - перегородки однозначно определяют количество книг. По записи, например **|*|* можно точно понять, что до первой черты - книги типа А, между 1-й и 2-й перегородкой - 1 книга типа В и в конце 1 книга типа С.

Запись вида ****|| означает, что все выбранные книги типа А. Вида **|**| - что выбраны по 2 книги типа А и В соответственно.

Итак, вспомним условия задачи - выбрать из 3 типов книг 4 экземпляра, при этом книги разных типов неотличимы между собой, и количество экземпляров может быть любым, а порядок выбранных книг не важен. Это можно сформулировать как найти сочетания из n(3) по k(4) с повторениями.

Для решения задачи мы ввели перегородки в количестве n-1(2) штуки, при этом получив 6 элементов, из которых нужно выбрать 2 в качестве перегородки, т.е. к задаче выбора сочетаний из n+k-1 (6) по n-1 (2), а это и есть формула выше.

Что же касается изначальной задачи? У нас 5 книг - это n, 3 нужно выбрать, это k, значит у нас будет всего будет 5 + 3 - 1 элементов, которые нужно разделить 4 перегородками. Задача сводится к сочетанию из 7 по 4 без повторов. В результате мы можем получить результат вида |*|*|*| (2, 3, 4), ***||||(1, 1, 1), ||*||**(3, 5, 5), и т.д. А всего их 7!/(4!3!) = 35.

Сколько существует натуральных чисел меньше 10.000, которые в сумме дают 9? Ответ: 220. Нам нужно найти такие числа abcd, при которых выполняется условие a+b+c+d=9. Представим число 9 в унарной системе, т.е. просто как 9 символов *. Тогда можно записать, что a+b+c+d=*********. Если мы добавим 3 символа |, то любая последовательность разобьется на 4 группы, например 1251=*|**|*****|*, 9000=*********|||. Всего таких вариантов число сочетаний из 12 по 3, или 12!/(3!9!)

Бином Ньютона

В какой-то момент всем нам знакомый магазин распродал все различные книги, кроме 2-х, но экземпляров этих книг осталось очень много. Чтобы побыстрее продать книги, магазин устраивает акцию и продает книги по особой схеме: есть 4 витрины, на каждой по 1 экземпляру каждого вида. Выглядит это следующим образом.

Магазин предлагает купить 4 книги на выбор по очень большой скидке, для этого из каждой витрины нужно взять по 1 типу. Может получиться набор АААА, АААВ, АВАВ, ВВВВ и т.д. Как всегда вопрос стоит следующий - сколько есть таких комбинаций?

Вспоминаем правило произведения, в первой витрине мы можем взять любую из 2-х книг, для любой книги одну из двух со второй и т.д. В итоге мы получим 2*2*2*2 = 16 вариантов. Но некоторые из них будут одинаковы, если не учитывать порядок. Например, АВВВ = ВАВВ = ВВАВ = ВВВА. Их четыре штуки.

Заметим, что как только мы выбрали книги типа А - книги типа В определяются однозначно. Сколько книг типа А мы можем выбрать? Очевидно, мы можем выбрать все книги типа В, тогда книг типа А будет ноль. С другой стороны мы можем выбрать все книги типа А, тогда их будет 4. Но и любое количество от 0 до 4 также можем выбрать.

А теперь посмотрим внимательно, что означает выбрать, например, 2 книги типа А? Это означает выбрать 2 витрины, с которых мы берем книги типа А. Или по другому выбрать 2 витрины из 4-х. Что означает выбрать 1 книгу типа А? Это все равно что выбрать 1 витрину из 4-х. Выбрать 3 книги типа А - выбрать 3 витрины из 4-х и т.д. Выбрать k витрин из 4-х - это чисто сочетаний из 4 по k. Раз мы можем выбрать книгу типа А только 0, 1, 2, 3 или 4 раза, давайте найдем количество всех способов сделать это.

• Выбрать 0 витрин из 4-х можно 1-м способом,т.е. просто не выбирая ни одну (4!/(0! * 4!))
• Выбрать 1 витрину из 4-х можно 4-мя способами (4!/(1! * 3!))
• Выбрать 2 витрины из 4-х можно 6-ю способами (4!/(2! *2!))
• Выбрать 3 витрины из 4-х можно 4-мя способами (4!/(3! * 1!))
• Выбрать 4 витрины из 4-х можно 1-м способом (4!/(4! * 0!))

Так как нам не интересен порядок, и мы считаем варианты АВВВ = ВАВВ и т.д. одинаковыми, будем всегда сначала писать тип А, а затем тип В. Например, все варианты ВАВА, АВВА и т.д. сведем к ААВВ. Что мы получим в итоге.

Итоговая сумма получается следующая: 1 - ВВВВ, 4 - АВВВ, 6 - ААВВ, 4 АААВ, 1 - ААА. В сумме они дают 16 (1+4+6+4+1). А что же мы сделали на самом деле - мы нашли коэффициенты выражения (a+b)^4. Посмотрите на формулу ниже и соотнесите это с нашей задачей.

Когда мы возводим в степень, мы умножаем скобку саму на себя. Когда мы раскрываем скобки, мы из каждой скобки выбираем или а, или b. Если мы выбираем все а - получаем а^4. Выбрать 4 а из 4-х скобок можно только 1-м способом. Дальше выбираем из 3-х а, и из 1-й b. Это можно сделать 4-мя способами и т.д.

Числа, которые мы нашли называются биномиальные коэффициенты.

Думаю понятно, что таким образом можно найти коэффициенты для любого выражения (a+b)^n. Бином - это многочлен, состоящий из 2-х одночленов (мономов).

Итоговая формула для бинома Ньютона выглядит следующим образом. Присмотритесь и вы поймете, что мы сделали все ровно по этой формуле, и при чем тут число сочетаний.

Треугольник Паскаля

Рассмотрим одно важное тождество

Доказывается оно очень просто. Предположим, мы хотим выбрать k(3) элементов из n(5). Зафиксируем последний элемент. Мы его можем взять при рассмотрении очередного сочетания, или нет. Мы не можем взять половину элемента. Если мы не берем, то нам нужно выбрать k элементов из всех элементов кроме последнего. Если мы его берем, то нам нужно выбирать элементы из всех кроме последнего, но 1 нужный мы уже нашли.

А теперь сделаем следующее. Будем увеличивать n, начиная от 0, сверху вниз, и запишем в ряд все сочетания из n по k, где k меняется от 0 и до n. Мы получим следующий треугольник слева.

По выражению выше, сумма зеленых элементов равна красному. Если мы найдем конкретные значения сочетаний, то получим треугольник справа. А теперь посмотрим на значения при n=4 - 1, 4, 6, 4, 1 - это и есть наши биномиальные коэффициенты при раскрытии скобок выражения (a+b)^4.

Заключение

Основная сложность комбинаторики - понять задача какого типа перед нами стоит и какую формулу использовать. В основном они сводятся к следующим

• число перестановок (с повторениями или без)
• число размещений (с повторениями или без)
• число сочетаний (с повторениями или без)
• найти сумму всех сочетаний для данного числа или каким-то иным способом использовать свойства треугольника Паскаля.