Лекция 12: Графы - 2 (стр. 13 )

Примеры:

Задача 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)! способами. Но это верно только если расстановки, отличающиеся поворотом круга, считаются одинаковыми.