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

Ноя 16 2014

Лекция «Комбинаторика»

Комбинаторика — это математическая наука, грубо говоря, о подсчете числа способов сделать что-либо. Несмотря на узость предмета изучения, наука эта весьма глубока. Кроме того, в олимпиадных задачах комбинаторика используется настолько часто, что ее знание (хотя бы в объеме данной лекции!) совершенно необходимо каждому математику-олимпиаднику.

(!) Хотя многие комбинаторные задачи кажутся очевидными, но многие школьники, особенно начинающие, путаются в них, принимая задачу одного типа за принципиально другую. Избежать путаницы в голове можно именно систематическим изучением теории.

Основные комбинаторные формулы и соображения:

1. Аддитивность взаимоисключающих случаев. Если в комбинаторной задаче имеется (возможно, на каком-то внутреннем этапе) несколько взаимоисключающих случаев/вариантов выбора, то общее число способов равно сумме количеств способов в каждом из этих случаев.
Это действительно очевидно. Настолько, что в решении задач можно даже не формулировать 😉

2. Мультипликативность независимых случаев. Если способ (количество которых надо посчитать) полностью определяется несколькими независимыми друг от друга этапами выбора (на каждом этапе выбор вариантов — взаимоисключающий!), то общее число способов равно произведению количеств вариантов выбора на каждом этапе.
Доказательство: Пусть у нас всего есть k этапов. Обозначим количество вариантов выбора на первом этапе — n1, на втором этапе — n2… на последнем — nk. На первом этапе у нас есть n1 вариантов выбора, т.е. образуется n1 случаев. На втором этапе в каждом из этих случаев мы может выбрать любой (т.к. этапы независимы) из n2 вариантов, образовав n2 подслучаев. Таким образом, после двух этапов будет уже n1*n2 случаев. На третьем этапе в каждом из них мы можем выбрать любой из n3 вариантов… и после трех этапов будет n1*n2*n3 случаев. Продолжая этот процесс, мы получаем после всех этапов n1*n2*…*nk случаев — и это будут уже окончательные способы. Их количество как раз равно произведению количеств вариантов выбора, ч.т.д.
Опять же, в решении задач это свойство можно даже не формулировать… если вы уверены, что применили его в правильной ситуации 😉

(!) На самом деле, доказывая п.2, мы пользуемся утверждением п.1. Например, как подробнее объяснить, почему после двух этапов есть n1*n2 случаев? У нас есть взаимоисключающие случаи — варианты выбора на первом этапе, которых n1 штук. В каждом из них есть n2 способов сделать выбор на двух этапах (на первом этапе вариант уже известен, осталось выбрать n2 вариантов на втором этапе). А чтобы найти общее число способов сделать выбор на первых двух этапах, надо (в соответствии с п.1) сложить n1 чисел, равных n2, т.е. умножить n1 на n2, ч.т.д.

2′. Общее правило мультипликативности подслучаев. Если способ полностью определяется несколькими, возможно зависимыми друг от друга, этапами выбора, но количество вариантов выбора на каждом этапе не зависит от того, как был сделан выбор на предыдущих этапах, то общее число способов равно произведению количеств вариантов выбора на каждом этапе.
Доказательство: Ничем не отличается от доказательства п.2, т.к. там мы пользовались независимостью от предыдущих этапов выбора только количества вариантов на данном этапе.

(!) Очень распространенной ошибкой является перепутывание области применения п.1 и п.2, вплоть до полного непонимания, где и почему надо складывать варианты, а где — умножать. Поэтому мы тут же проиллюстрируем их различие на примерах.

Примеры:

Задача 1. Из города А в город Б ведет 6 дорог, из города Б в город В — 4 дороги, и больше никаких дорог из этих городов не выходит. Сколькими путями можно проехать из города А в город В?
Решение: На первом этапе нам надо выбрать дорогу, по которой мы поедем из А в Б, и здесь у нас есть 6 вариантов. На втором этапе надо выбрать дорогу, по которой мы поедем из Б в В, и там у нас 4 варианта. Эти два этапа полностью определяют путь проезда. Выбор независим, т.к. по какой бы дороге мы не поехали в Б, мы сможем потом поехать в В по любой из дорог. Таким образом, мы имеем дело с независимыми этапами выбора, и должны перемножать варианты. Всего получаем 6*4=24 различных пути.
(!) Если понимание не пришло, то рекомендуется нарисовать картинку, прочертить на ней все 24 пути и понять, что никак иначе проехать нельзя.

Задача 2. Из глухого захолустного города Г, где отродясь не было никаких дорог, проложили 2 новые дороги в город В из предыдущей задачи. Кроме того, из города А из предыдущей задачи в город Г проложили еще 2 новые дороги. Сколькими путями теперь можно проехать из города А в город В?
Решение: В этой задаче надо в самом начале выделить два взаимоисключающих случая: когда мы едем через город Б, и когда едем через город Г. Найти количество путей в первом случае — это в точности задача 1, и ответ будет 6*4=24 (по п.2). Найти количество путей во втором случае — это задача, аналогичная задаче 1, но с ответом 2*2=4. Теперь, по п.1, эти количества путей надо сложить, и в ответе получается 24+4=28 путей проезда.

(!) Этот кусок лекции следует перечитывать до полного осознания того, почему в задаче 2 числа 6 и 4 надо перемножить, 2 и 2 — тоже перемножить, а 24 и 4 — сложить.

Теперь займемся такими видами задач, где надо выбирать какие-то предметы или элементы множеств (для стандартизации, скажем, что нам надо из n элементов выбрать k):

3. Выбор с повторениями, с учетом порядка (заполнение позиций элементами множества).
Общая задача может формулироваться так: «Есть алфавит из n букв. Сколько в этом алфавите «слов» ровно из k букв?» Ответ будет ровно nk.
Доказательство: У нас есть n способов выбрать первую букву, n способов выбрать вторую букву… n способов выбрать k-ю букву. Всего имеет k этапов выбора, по n вариантов на каждом. При этом выбор независим (какие бы ни были первые несколько букв, мы можем выбрать любую следующую). Поэтому, можно применить п.2 и получить ответ nk ч.т.д.
Доказательство №2: (Здесь мы покажем, как можно не ссылатся на утверждение п.2, а воспроизвести его док-во прямо в решении.) У нас есть n способов написать первую букву (это дает n случаев). В каждом из них мы можем n способами приписать к первой букве вторую и получить n двухбуквенных слов (образуется n подслучаев). Всего будет n*n=n2 способов написать первые две буквы. В каждом из этих n2 случаев мы можем n способами приписать в первым двум буквам третью и получить n трехбуквенных слов (опять образуется n подслучаев). Всего будет n2*n=n3 способов написать первые 3 буквы. И так далее, пока мы не напишем все слово — здесь число способов будет n в степени, равной длине слова, т.е. nk ч.т.д.

(!) Для читателей, незнакомых с факториалами: далее в тексте будет встречаться обозначение n! (читается «n-факториал»). Оно обозначает произведение всех натуральных чисел от 1 до n, т.е. n!=1*2*…*(n-1)*n. 1!=1, 2!=2, 3!=6, 4!=24, 5!=120 и (обратите особое внимание!) считается, что 0!=1. Последнее равенство обеспечивает верность формул, содержащих факториалы, для крайних случаев, когда одно из чисел под факториалом равно 0. Заметим также, что n!=n*(n-1)!

4. Выбор без повторений, с учетом порядка (раскладка в ряд).
Общая задача может формулироваться так: «Есть куча из n разных предметов. Мы последовательно берем из них k предметов и ставим в ряд. Сколько есть разных способов заполнения ряда?» Число в ответе имеет свое специальное обозначение: Ank и вычисляется по формуле Ank=n*(n-1)*(n-2)*…*(n-k+1) или Ank=n!/(n-k)! (вторая формула получается при умножении и делении первой на (n-k)!)
Доказательство: У нас есть n способов выбрать (взять и поставить в ряд) первый предмет (назовем это первым этапом выбора). Далее у нас есть, независимо от того, как выбран первый предмет, n-1 способов взять второй предмет — в любом случае, это может быть какой угодно предмет, кроме первого выбранного. Затем есть n-2 способа взять третий предмет — он может быть какой угодно, кроме первых двух выбранных… и так далее. Обратите внимание, что число способов выбрать последний, k-й предмет — не n-k, а n-k+1=n-(k-1), т.к. им может быть любой, кроме первых k-1 выбранных. Итого, мы имеет k этапов выбора, на каждом из которых число вариантов равно (независимо от того, как сделан выбор на предыдущих этапах), соответственно, n, n-1… n-k+1. Поэтому, согласно п.2′, мы получаем общее число способов выбора k предметов n*(n-1)*…*(n-k+1), ч.т.д.
Упражнение: Придумать доказательство с полной подстановкой рассуждения из п.2, т.е. похожее на док-во №2 предыдущего пункта.

Для справки: An0=1 (обратите внимание!), An1=n, An2=n*(n-1)=n2-n, … Ann-1=n!/1!=n!, Ann=n!

4′. Перестановки n предметов.
Имеется n разных предметов. Сколько у нас способов выставить их все в ряд?
Обычно эту задачу рассматривают как отдельную и повторяют отдельно все комбинаторное рассуждение (как в док-ве №2 п.3). Но мы заметим, что эта задача — частный случай п.4 при k=n. Поэтому ответ будет Ann=n!
Упражнение: Придумать обычное доказательство, с повторением комбинаторного рассуждения.

5. Выбор без повторений, без учета порядка (число сочетаний).
Общая задача может формулироваться так: «Есть куча из n разных предметов. Мы берем из них k предметов и кидаем в мешок. Сколько есть разных способов заполнения мешка?» Число в ответе имеет свое специальное обозначение: Сnk и вычисляется по формуле Сnk=Ank/k! или Cnk=(n*(n-1)*(n-2)*…*(n-k+1))/k! или Cnk=n!/(k!*(n-k)!) (вторая и третья формулы получается при подстановке в первую формулу формул для Ank)
Доказательство: Достаточно доказать только первую формулу. Пусть мы сначала выбираем k предметов последовательно и ставим в ряд, а потом закидываем этот ряд в мешок. Число возможных рядов и есть, согласно п.4, Ank. Докажем, что заполнений мешка ровно в k! раз меньше, чем различных рядов — тогда формула будет доказана. (Заметим, что один и тот же ряд не может переходить в два разных заполнения мешка!) Теперь обернем процесс закидывания ряда в мешок: пусть в мешке лежат какие-то k предметов, а мы достаем их и ставим в ряд. Согласно п.4′, у нас для каждого заполнения мешка будет ровно k! различных рядов. Кроме того, по нашему замечанию, из двух разных заполнений мешка нельзя получить один и тот же ряд. Поэтому рядов ровно в k! раз больше, чем заполнения мешка, ч.т.д.

Для справки: Cn0=1 (обратите внимание!), Cn1=n, Cn2=n*(n-1)/2=(n2-n)/2, Cn3=n*(n-1)*(n-2)/6 … Cnn-1=n, Cnn=1.
Вообще говоря, Cnk=Cnn-k для любого n>=0 и 0<=k<=n. Свойствам чисел Cnk и способам их быстрого вычисления будет посвящена лекция «Комбинаторика-2″.

(!) Выбор k предметов из n с повторениями, но без учета порядка, относится к теории «шаров и перегородок» и будет также рассматриваться в лекции «Комбинаторика-2″. Для любопытных сообщаю ответ: Cn+k-1k.

Примеры применения пп.3-5:

Задача 3. Сколько существует 6-значных чисел, в записи которых есть хотя бы одна четная цифра?
Решение: Разбирать случаи, сколько четных цифр и на каких местах стоит в нашем числе — слишком долго и противно. Воспользуемся хитрым приемом: посчитать то, что нам не нужно. То есть, считать будем числа из одних нечетных цифр. Нечетные цифры — это «алфавит» из 5 «букв», а 6-значное число — «слово» из 6 «букв» этого «алфавита». Таких слов-чисел, согласно п.3, будет ровно 56 штук. А чисел, которые нас интересуют (это все остальные) — ровно 900000-56=900000-15625=984375 (всего 6-значных чисел 900000).

Задача 4. По Конституции, флаг страны состоит из трех одинаковых горизонтальных полос трех различных цветов, причем на флаге могут быть только белый, красный, желтый, зеленый, голубой и черный цвета. Сколько разных флагов разрешает такая Конституция?
Решение: Мы имеем дело с выбором 3-х из 6. Выбор происходит без повторений (цвета должны быть различны) и с учетом порядка (важно, какой цвет вверху, какой внизу и какой в середине). Согласно п.4, ответом будет число A63=6*5*4=120.

Задача 5. Сколькими способами можно выставить по кругу красный, коричневый, зеленый, голубой и звездно-полосатый флаги? (расстановки, отличающиеся поворотом круга, считаются одинаковыми)
Решение: Перестановки n различных предметов в ряду мы уже умеем считать, пользуясь п.4′. Теперь осталось немного подумать и свести перестановки по кругу к перестановкам в ряд. Возьмем еще 5 флагов тех же цветов и будем выставлять в ряд: первый в ряду всегда будет звездно-полосатый, а следующие 4 идут в том же порядке, в каком 4 флага в круге следуют по часовой стрелке после звездно-полосатого. Например, расстановке (Кр)-(Зел)-(Гол)-(Зв-Пол)-(Кор)-(Кр) [изображен порядок флагов по кругу по часовой стрелке] будет соответствовать ряд (Зв-Пол)-(Кор)-(Кр)-(Зел)-(Гол). Понятно, что любой расстановке по кругу соответствует какой-то ряд, и любому ряду, начинающемуся со звездно-полосатого флага, соответствует какая-то расстановка по кругу (просто надо поставить звездно-полосатый флаг и вслед за ним по кругу, по часовой стрелке, выставить остальные 4 флага в том же порядке, в каком они были в ряду). Значит, расстановок флагов по кругу ровно столько же, сколько расстановок в ряд, начинающихся со звездно-полосатого флага. Этих расстановок будет ровно 4!=24, так как реально мы расставляем только 4 флага (а звездно-полосатый всегда торчит на первом месте). Ответ: 24 способа.
Это рассуждение можно сильно упростить: всего есть 5! расстановок флагов(хоть вдоль ряда, хоть вдоль круга), но они объединяются вгруппы по 5 штук, переходящих друг в друга при повороте круга (проверьте, что поворотов, переводящих расстановку в расстановку, ровно пять!). Поэтому в ответе будет 5!/5=4!=24 способа.

(!) Нелишне запомнить: n предметов по кругу можно выставить ровно (n-1)! способами. Но это верно только если расстановки, отличающиеся поворотом круга, считаются одинаковыми.

Задача 6. Один профессор математики написал 6 книг, другой — 8. Каждый из хочет подарить другому 3 свои книги с автографом. Сколькими способами они могут обменяться подарками?
Решение: Первый профессор может выбрать для подарка 3 книги из своих 6, а это можно сделать C63=20 способами (см. п.5). Второй профессор может выбрать для подарка 3 книги из своих 8, уже C83=56 способами. Оба выбора происходят независимо и однозначно определяют способ обмена, поэтому варианты нужно перемножать. Ответ: C63*C83=56*20=1120 способов.

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

Примеры:

Задача 7. Сколько «слов» (здесь и далее словом считается любая последовательность букв русского алфавита) можно получить, переставляя буквы в слове ЛИНИЯ?
Решение: В этом слове есть 2 одинаковые буквы (И). Будем временно считать их разными: И1 и И2. По п.4′ получаем, что теперь можно составить 5!=120 слов. На самом деле, это в несколько раз больше, чем нужно. Во сколько же именно? Понятно, что слова, различающиеся только перестановкой букв И1 и И2 на тех же местах (например, ЛИ1ЯНИ2 и ЛИ2ЯНИ1), на самом деле одинаковы, хотя мы посчитали их как разные. Всего на одних и тех же местах можно расставить буквы И1 и И2 ровно 2!=2-мя способами, следовательно, каждый раз мы вместо одного слова сосчитываем 2 разных. Значит, мы получили 120:2=60 различных слов.

Задача 8. Тот же вопрос про слово АКАДЕМИЧЕСКИЕ?
Решение: В этом слове повторяются 4 разные буквы: по 2 раза А, И и К и 3 раза Е. Опять применяем тот же прием, считая все буквы разными: Е1, Е2 и Е3, А1 и А2, И1 и И2, а также К1 и К2. Теперь можно составить аж 13! слов (для любопытных: 13!=6 227 020 800). Здесь мы посчитали одинаковые слова как разные, если они различаются только какой-то перестановкой букв Е1, Е2 и Е3 и/или А1 и А2 и/или К1 и К2 и/или И1 и И2 на тех же местах. Буквы Е1, Е2 и Е3 можно расставить на тех же местах 3!=6-ю способами, а остальные пары повторяющихся букв можно расставить 2!=2-мя способами каждую (и тут эти варианты расстановок независимы, поэтому надо перемножать). Каждый раз мы вместо одного слова сосчитываем 2!*2!*2!*3! разных. В ответе получаем 13!/(3!*2!*2!*2!) различных слов. (Для любопытных: 13!/(2!*2!*2!*3!)=13!/(2*2*2*6)=13!/48=6227020800/48=129729600.)

(!) Здесь, как и при подсчете чисел Cnk, мы использовали очень важную идею кратного подсчета: подсчитать объекты, которых во сколько-то раз больше чем тех, которые нам нужны, а потом узнать, во сколько раз их больше. Для Cnk роль таких вспомогательных объектов играли способы взятия предметов с учетом порядка (которых Ank,), а в данном случае — перестановки слова, в котором все буквы разные.

Нет ответов пока

Вы должны ввойти чтобы оставить комментарий.