UML_4822 дм практикум

Путь дано множество Х, состоящее из подмножеств А, В, С. Элементы множества Х могут принадлежать одному, двум и трем подмножествам. Согласно принципу включения-исключения можно составить тождество:

= |A B C| – |A| – |B| – |C| + |A B| + |A C| + |B C| – |A B C|.

Данное выражение позволяет найти число элементов для любой операции, если известны их значения для всех других операций.

Рассмотренный принцип доказывается следующей парой теорем. Теорема 3. Если A и B конечные подмножества некоторого универ-

сального множества U, то

Доказательство. Применим метод полной индукции. Рассмотрим последовательно все пять различных случаев "взаимного расположения"

дут перечислены дважды. Отсюда и следует равенство (2.7). Теорема 3 доказана.

Задача 56. Сколькими способами можно выбрать гласную и согласную буквы из слова ``Камзол''?

Ответ. 2 4 = 8.

Задача 57. В магазине ``Все для чая'' есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем?

Решение. Выберем чашку. В комплект к ней можно выбрать любое из трех блюдец. Поэтому есть 3 разных комплекта, содержащих выбранную чашку. Поскольку чашек всего 5, то число различных комплектов равно 15 (3 5 = 15).

Задача 58. Из города А в город В ведут пять дорог, а из города В в город С – три дороги. Сколько путей, проходящих через В, ведут из А в С?

Ответ. По правилу произведения получаем 5 3 = 15.

Задача 59. Из двух спортивных обществ, насчитывающих по 100 фехтовальщиков каждое, надо выделить по одному фехтовальщику для

41

участия в состязании. Сколькими способами может быть сделан этот выбор?

Ответ. 1002 = 10 000 способов.

Задача 60. Бросают игральную кость с шестью гранями и запускают волчок, имеющий восемь граней. Сколькими различными способами могут они упасть?

Ответ. 48.

Задача 61. На вершину горы ведут пять дорог. Сколькими способами турист может подняться на гору и спуститься с нее? То же самое при условии, что спуск и подъем происходят по разным путям?

Ответ. 25; 20.

Задача 62. На ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его еще раз?

Ответ. 480; 437.

Задача 63. Сколькими способами можно указать на шахматной доске два квадрат – белый и черный? А если нет ограничений на цвет выбранных квадратов?

Ответ. 1024; 4032.

Задача 64. Сколькими способами можно выбрать на шахматной доске белый и черный квадраты, не лежащие на одной и той же горизонтали и вертикали?

Решение. Белый квадрат можно выбрать 32 способами, вычеркнем соответствующие горизонталь и вертикаль. На оставшейся части доски есть 24 квадрата. Всего 32 24 = 768 способов выбора.

Задача 65. Из 3 экземпляров учебника алгебры, 7 экземпляров учебника геометрии и 7 экземпляров учебника тригонометрии надо выбрать по одному экземпляру каждого учебника. Сколькими способами это можно сделать?

Ответ. 3 7 7 = 147.

Задача 66. Сколькими способами можно выбрать четырехзначное число, все цифры которого различны?

Решение. Каждому четырехзначному числу можно поставить во взаимно однозначное соответствие строку (х1, х2, х3, х4) , где х1, х2, х3, х4 – соответственно 1, 2, 3 и 4-я цифры. Элемент х1 этой строки можно выбрать 9 способами (любую из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9); элемент х2 можно выбрать также 9 способами (теперь можно использовать и цифру 0, но первую выбранную цифру повторить нельзя); элемент х3 можно выбрать 8 способами (уже выбранные первые две цифры повторить нельзя); наконец, элемент х4 можно выбрать 7 способами.

Согласно правилу произведения искомое число способов выбора четырехзначного числа с различными цифрами равно: 9 9 8 7 = 4536.

42

Задача 67. Сколько четырехзначных чисел можно составить, пользуясь только цифрами 0, 1, 2, 3, 4, 5, если ни одна из цифр не повторяется более одного раза?

Решение. Первой цифрой числа может быть только одна из 5 цифр 1, 2, 3, 4, 5 (0 не может быть первой цифрой, так как в этом случае число не будет четырехзначным); если первая цифра выбрана, то вторая может быть выбрана 5 способами, третья – 4 способами, четвертая – 3 способами. Согласно основному правилу комбинаторики общее число способов равно 5 5 4 3 = 300.

Задача 68. Сколько четырѐхбуквенных «слов» можно составить из карточек «в», «е», «ч», «н», «о», «с», «т», «ь»?

Решение. Пусть ak – k-я буква слова (k =1,2,3,4). Тогда n1 = 8, n2 = 7, n3 = 6, n4 = 5 и по правилу произведения сразу получаем ответ: 8 7 6 5 = 1680.

Ответ: 1680.

Задача 69. Сколькими способами можно поставить на шахматную доску белую и черную ладью так, чтобы они не били друг друга?

Решение. Выбор объекта а1 – поля для белой ладьи – может быть сделан n1=64 способами. Независимо от выбора этого поля белая ладья бьѐт 15 полей, поэтому для чѐрной ладьи остается 64 – 15 = 49 полей: n2=49.

Ответ. Число расстановок ладей равно 64 49 = 3136.

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

Задача 70. Сколькими способами можно поставить на доску восемь ладей так, чтобы они не били друг друга?

Решение. В этой задаче подразумевается (хотя прямо и не говорится), что ладьи одинаковые, неразличимые. Очевидно, что на каждой горизонтали и на каждой вертикали должна стоять только одна ладья. Будем расставлять ладьи последовательно, начиная с первой горизонтали. На первой горизонтали 8 клеток, и первую ладью можно поставить на любую из них. Когда мы будем ставить вторую ладью, то на второй горизонтали ей будут доступны 7 клеток и т.д. По правилу произведения получаем, что всего таких позиций 8!

Если же считать ладьи различными (как в предыдущем примере), то число перестановок ладей равно

64 49 36 25 16 4 1 = (8!)2.

Действительно, для первой ладьи можно выбрать любое поле доски размером 8 8, вторая ладья фактически ставится на квадратную доску 7 7

43

(мы удалили одну горизонталь и одну вертикаль и «сдвинули» оставшиеся части доски) и т.д.

Зафиксируем одну из таких расстановок различных ладей. Число перестановок ладей на выделенных полях равно 8! Если мы считаем ладьи одинаковыми, то (8!)2 позиций разбиваются на классы по 8! позиций в каждом, и все позиции данного класса будут одинаковыми. Поэтому чис-

ло перестановок одинаковых ладей равно 8! 2 8!, что совпадает с ранее

8!

полученным ответом.

Задача 71. Сколько существует четырѐхзначных чисел, у которых все цифры нечѐтные? Сколько существует четырѐхзначных чисел, в записи которых есть хотя бы одна чѐтная цифра?

Решение. Всего нечѐтных цифр – пять, поэтому выбор k-й цифры числа может быть сделан nk = 5 способами (k =1, 2, 3, 4). Количество четырѐхзначных чисел, у которых все цифры нечѐтные, равно 5 5 5 55 = 625.

Чтобы ответить на второй вопрос, проще не определять последовательно, сколько существует чисел, в записи которых ровно одна чѐтная цифра, две, три, четыре, а воспользоваться полученным ответом на первый вопрос. Все четырѐхзначные числа, а их 9999 – 999 = 9000, делятся на две группы: те, в записи которых все цифры нечѐтные, и те, в записи которых есть хотя бы одна чѐтная цифра. Следовательно, количество чисел второго типа равно 9000 – 625 = 8375.

Ответ. 8375.

Обратите внимание на идею, которую мы использовали – переход к дополнению изучаемого множества. Это пример применения второго общего правила комбинаторики – правила суммы.

Задача 72. В Стране Чудес есть четыре города A, B, С, D. Из города А в город В ведет 6 дорог, а из города В в город D – 4 дороги. Из города А в город С ведет 2 дороги, а из города С в город D – 3 дороги (рис. 13). Сколькими способами можно проехать от А к D?

Рис. 13. Карта дорог Страны Чудес

Решение. Выделим два случая: путь проходит через город В или путь проходит через город С. В каждом из этих случаев легко подсчитать коли-

44

чество возможных маршрутов: в первом – 24, во втором – 6. По принципу сложения получим общее количество маршрутов – 30.

Задача 73. В букинистическом магазине лежат 6 экземпляров романа И.С. Тургенева «Рудин», 3 экземпляра его же романа «Дворянское гнездо» и 4 экземпляра романа «Отцы и дети». Кроме того, есть 5 томов, содержащих романы «Рудин» и «Дворянское гнездо», и 7 томов, содержащих романы «Дворянское гнездо» и «Отцы и дети». Сколькими способами можно сделать покупку, содержащую по одному экземпляру каждого из этих романов?

Решение. Можно купить либо по экземпляру каждого романа, либо том, содержащий два романа. По правилам суммы и произведения получаем 6 3 4 + 5 4 + 7 6 = 134 способа.

Задача 74. Та же задача, если кроме того, в магазине есть 3 тома, в которые входят «Рудин» и «Отцы и дети».

Решение. Можно купить еще том, содержащий романы «Рудин» и «Отцы и дети» и один экземпляр «Дворянского гнезда». Добавляется 3 3 = 9 способов, а всего имеем 143 способа.

Задача 75. Имеются три волчка с 6, 8 и 10 гранями соответственно. Сколькими различными способами могут они упасть? Та же задача, если известно, что по крайней мере два волчка упали на сторону, помеченную цифрой 1.

Решение. 6 8 10 = 480; если первые два волчка упали на сторону «1», то третий волчок может упасть 10 способами; аналогично рассматриваются случаи, когда на такую сторону падают другие два волчка; всего получаем 6 + 8 + 10 способов, но при этом один способ (когда на сторону «1» падают все три волчка) считается трижды, поэтому остается 22 способа.

Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Общим термином «соединения» будем называть три вида комбинаций, составляемых из некоторого числа различных элементов, принадлежащих одному и тому же множеству – перестановки, сочетания и размещения.

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

Определение. Упорядоченные n-ки (кортежи длины n), содержащие все элементы множества A называются перестановками этого множества. Иногда добавляют «из n элементов». Другими словами, перестановки – это комбинации или соединения из n элементов, содержащие все элементы, и которые считаются различными, если отличаются порядком элементов.

Упорядоченные выборки, объемом n из n элементов, где все элементы различны, называются перестановками из n элементов. Число перестановок из n элементов обозначается Pn.

45

Процедура перестановки имеет большое значение при выборе алгоритмов сортировки данных на компьютере для быстрого и экономного использования оперативной памяти. Все алгоритмы опираются на отношение порядка и формируют линейно упорядоченные множества.

Обычно выделяется одно, основное или естественное, упорядочение, которое называется тривиальной перестановкой. Сами элементы множества A нас не интересуют. Часто в качестве рассматриваемых элементов берут целые числа от 1 до n или от 0 до n – 1. Выясним, чему равно число всевозможных перестановок Pn, как перебрать элементы {Pn}, как их перенумеровать.

Пусть задано конечное множество A мощности n.

Теорема 4. (Теорема о числе перестановок). Если через Pn обозна-

Доказательство. Будем последовательно выбирать элементы множества A и размещать их в определенном порядке на n местах. На первое место можно поставить любой из n элементов. После того как заполнено первое место, на второе место можно поставить любой из n – 1 оставшихся элементов. По правилу произведения упорядоченный выбор двух элементов можно осуществить n (n 1) способами. Затем выбираем третий элемент, для его выбора останется n 2 возможности и т.д., последний элемент можно выбрать единственным способом. По принципу умножения все n мест можно заполнить и получить в результате перестановку n n 1 n 2 ... 2 1 n! способами. Мы вновь приходим к формуле

(2.8). Теорема доказана.

Задача 76. Дано трехэлементное множество M = {1, 2, 3}. Укажите всевозможные перестановки этого множества.

Ответ. (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).

Задача 77. Сколькими способами можно расставить на книжной полке десятитомник Пушкина так, чтобы том 2 стоял рядом с томом 1 и справа от него?

Решение. Чтобы решить задачу, будем рассматривать пару томов 1 и 2-й как один объект. Расстановка полученного набора из 9 томов (восьми обычных и одного сдвоенного) может быть произведена 9! способами.

Задача 78. К кассе кинотеатра подходит 6 человек. Сколько существует различных вариантов установки их в очередь друг за другом?

Решение. Расставим 6 человек произвольным образом и начнем их переставлять всеми возможными способами. Число полученных перестановок в соответствии с формулой перестановок будет равно 6! = 720.

Задача 79. Сколько различных слов (пусть и не имеющих смысла) можно получить путем перестановки букв в слове “дубленка”?

46

Ответ. 8! = 40320.

Задача 80. В заезде на ипподроме участвуют 12 рысаков. Играющие в тотализатор заполняют карточки, в которых указывают порядок, в котором, по их мнению, рысаки придут к финишу. Будем считать, что к финишу одновременно не могут придти два и более рысаков. Сколько вариантов заполнения карточек существует?

Ответ. 12!

Задача 81. На заседании Думы 14 депутатов записались на выступления. Сколько вариантов списков выступающих может быть составлено, если списки отличаются только порядком? Подсчитайте количество расстановок депутатов в списке выступающих, если известно, что некоторые депутаты “Ж” и “З” уже добились, чтобы их включили в список выступающих под номерами соответственно 3 и 7.

Ответ. 14!; 12!

Задача 82. Сколько существует способов, чтобы расположить на полке 5 различных книг?

Решение. Число способов расстановки книг равно числу способов упорядочения множества, состоящего из 5 элементов, то есть Р5 = 1 2 3 4 5 = 120.

Задача 83. Сколькими способами можно упорядочить множество {1, 2,…, 2n}, так чтобы каждое четное число имело четный номер?

Решение. Четные числа можно расставить на местах с четными номерами (таких мест n) n! способами. Каждому способу размещения четных чисел на местах с четными номерами соответствует n! способов размещения нечетных чисел на местах с нечетными номерами. Поэтому общее число перестановок указанного типа по правилу умножения равно n! n! = (n!)2.

Задача 84. Сколько можно составить перестановок из n элементов, в которых данные два элемента не стоят рядом?

Решение. Определим число перестановок, в которых данные два элемента a и b стоят рядом. Могут быть следующие случаи: a стоит на первом месте, a стоит на втором месте, …, a стоит на (n – 1)-м месте, а b стоит правее a; число таких случаев равно n – 1. Кроме того, a и b можно поменять местами, и, следовательно, существует 2(n – 1) способов размещения a и b рядом. Каждому из этих способов соответствует (n – 2)! перестановок других элементов. Следовательно, число перестановок, в которых a и b стоят рядом, равно 2 (n – 1) (n – 2)! = 2 (n – 1)!. Поэтому искомое число перестановок равно n! – 2 (n – 1)! = (n – 1)! (n – 2).

Задача 85. Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг?

47

Решение. Если бы они стояли на месте, то получилось бы 7! = 5040 перестановок. Но так как танцующие кружатся, то их положение относительно окружающих предметов не существенно, а важно лишь взаимное расположение. Поэтому перестановки, переходящие друг в друга при кружении танцовщиц надо считать одинаковыми. Но из каждой перестановки можно получить еще шесть новых путем вращения. Значит, число 5040 надо разделить на 7. Получаем 5040:7 = 720 различных перестановок девушек в хороводе.

Вообще, если рассматривать перестановки n предметов, расположенных не в ряд, а по кругу, и считать одинаковыми расположения, переходящие друг в друга при вращении, то число различных перестановок равно (n – 1)!.

Задача 86. Сколько ожерелий можно составить из 7 различных бу-

син?

Решение. По аналогии с предыдущей задачей, можно подумать, что число различных ожерелий равно 720. Но ожерелье можно не только повернуть по кругу, но и перевернуть (рис. 14). Поэтому ответом на эту задачу является 720:2 = 360.

Рис.14. К решению задачи 86

2.3. Размещения

Напомним, что выборка называется упорядоченной, если в ней задан порядок следования элементов. Если порядок следования элементов несущественен, то выборка называется неупорядоченной.

Из определения следует, что две упорядоченные выборки, состоящие из одних и тех же элементов, но расположенных в разном порядке, являются различными.

Определение. Перестановки k-элементных подмножеств множества A называются размещениями из n элементов по k элементов. Другими словами, размещения из n элементов по k – это комбинации или соединения, содержащие k различных элементов, и которые считаются различными, если отличаются либо своими элементами, либо порядком элементов.

48

Другими словами, упорядоченные выборки объемом k из n элементов (k n), где все элементы различны, называются размещениями. Число размещений из n элементов по k обозначается Ank .

Теорема 5 (Теорема о числе размещений). Если через Ank обозначить число всех размещений из n по k элементов множества A, то

Доказательство. Рассмотрим схему: первый элемент выбираем n способами, второй – (n – 1) способами и т.д., k-й элемент выбираем (n – k + 1) способом. Число различных способов выбрать k элементов по принципу произведения равно: n(n – 1)...(n – k +1), что совпадает с Ank .

Задача 87. Дано множество M = {1, 2, 3, 4}. Укажите всевозможные размещения этого множества по 2 элемента.

Ответ. (1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3).

Задача 88. Научное сообщество состоит из 25 человек. Надо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами может быть сделан этот выбор, если каждый член общества может занимать лишь один пост?

Решение. В задаче имеет значении и то, кто будет выбран в руководство общества, и то, какие посты займут выбранные. Поэтому ответ

Задача 89. Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из пяти языков: русского, английского, французского, немецкого, итальянского на любой другой из этих пяти языков?

Ответ. A52 20 словарей.

Задача 90. На сколько больше словарей придется издать, если число различных языков равно 10?

Ответ. A102 A52 70 .

Задача 91. Компания из семи юношей и десяти девушек танцует. Если в каком-то танце участвуют все юноши, то сколько имеется вариантов участия девушек в этом танце?

Ответ. A107 604800 .

Задача 92. В парламент нового независимого государства нужно представить для рассмотрения варианты флагов (для определенности – три горизонтальных полосы). Сколько вариантов флагов можно предста-

49

вить, если каждый флаг должен содержать три разных цвета, а количество цветов имеющегося материала, из которого делаются флаги, равно 12?

Ответ. A123 1320.

Задача 93. Сколькими способами можно переставить буквы в слове «параллелизм» так, чтобы не менялся порядок гласных букв.

Решение. Зафиксируем порядок гласных букв. 7 гласных букв можно разместить на 11 мест A117 способами, однако следует учесть, что буква

«л» входит в слово трижды, поэтому окончательно имеем A7 / P 277200 .

11 3

Задача 94. Учащемуся необходимо сдать 4 экзамена на протяжении 8 дней. Сколькими способами это можно сделать?

Решение. Искомое число способов равно числу 4-элементных последовательностей (дни сдачи экзаменов) множества из 8 элементов, то есть A84 8 7 6 5 1680 способов. Если известно, что последний экзамен будет сдаваться на восьмой день, то число способов равно

4 A73 7 6 5 4 840.

Задача 95. Сколькими способами можно переставить буквы слова «логарифм» так, чтобы второе, четвертое и шестое места были заняты согласными буквами?

Решение. Выберем 3 буквы из 5 согласных и поставим их на указанные места ( A53 способов). Оставшиеся 5 букв произвольным образом расставим на остальные 5 мест (5! способов). Всего 5! A53 7200 способов.

Задача 96. Сколькими способами можно выбрать из фразы «око за око, зуб за зуб» три буквы, если учитывать порядок выбранных букв?

Ответ. A63 3A62 2 212 способов.

Задача 97. Сколько шестизначных чисел, кратных 5, можно составить из цифр 0, 1, 2, …, 9 при условии, что цифры в числе не повторяются?

Решение. Последней цифрой искомого числа может быть 0 или 5. В первом случае остальные пять цифр можно выбрать из множества {1, 2,

…, 9} и число вариантов равно A95 9!4! 15120 . Если число оканчивается

цифрой 5, то в качестве первой цифры можно взять любую из восьми цифр 1, 2, 3, 4, 6, 7, 8, 9 – нельзя использовать 0, так как число должно быть шестизначным. Цифры со второй по четвертую можно выбрать A84 1680 различными способами. Следовательно, по правилу произведе-

ния имеется 8 A84 чисел, оканчивающихся цифрой 5. По правилу суммы находим, сколько существует чисел, удовлетворяющих условию задачи

A95 8 A84 28560 .

50