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

2.4. Сочетания

Определение. Произвольное неупорядоченное k-элементное подмножество множества из n элементов (k n) в комбинаторике называется сочетанием из n элементов по k элементов. Порядок элементов в подмножестве не имеет значения, поэтому часто вместо слова "сочетание" употребляется термин – комбинация или соединение из n элементов по k элементов, которые отличаются, по крайней мере, одним элементом, но не порядком элементов. Их число обозначается Cnm . Символ Cnm читается:

«число сочетаний из n элементов по k элементов». С – первая буква французского слова Combinaison – «сочетание».

Такое формирование выборок иначе можно назвать “укладывание элементов множества А в “мешок”, то есть формируются неупорядоченные выборки мощности k.

Доказательство. Очевидно, Ank Cnk k !. Действительно, объект A – неупорядоченная выборка из n элементов по k, их число Cnk . После того,

как эти k элементов отобраны, их можно упорядочить k! способами (в роли объекта B выступает “порядок“ в выборке). Совместный выбор “A и B“

–упорядоченная выборка.

Сточки зрения теории множеств Cnk – это число всех подмножеств из k элементов, которые можно выбрать из множества, состоящего из n элементов. Поэтому равенство Cn0 1 означает, что всякое пустое под-

множество только одно; Cn1 n – что число одноэлементных подмножеств

равно n и т.д.

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

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

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

Задача 100. В турнире принимали участие n шахматистов, и каждые 2 шахматиста встретились 1 раз. Сколько партий было в турнире?

Решение. Партий было сыграно столько, сколько можно выделить двухэлементных подмножеств в множестве из n элементов, то есть

51

Задача 101. В скольких точках пересекаются диагонали выпуклого n-угольника, если никакие 3 из них не пересекаются в одной точке?

Решение. Каждой точке пересечения диагоналей соответствует 4 вершины n-угольника, а каждым 4 вершинам n-угольника соответствует одна точка пересечения (точка пересечения диагоналей четырехугольника с вершинами в данных 4 точках) поэтому число всех точек пересечения равно числу способов, которыми среди n вершин можно выбрать 4 вер-

Задача 102. Хоккейная команда состоит из 2 вратарей, 7 защитников и 10 нападающих. Сколькими способами тренер может образовать стартовую шестерку, состоящую из вратаря, двух защитников и трех нападающих?

го, по правилу произведения, существует 2 21 120 = 5040 способов выбора стартовой шестерки.

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

Решение. Число точек пересечения прямых равно числу способов выбора неупорядоченной пары прямых, то есть Cn2 . Аналогично, каждый треугольник определяется тройкой прямых, поэтому общее число треугольников равно Cn3 .

Ответ. Cn2 и Cn3 .

Задача 104. Для проведения письменного экзамена по комбинаторике надо составить 4 варианта по 7 задач в каждом. Сколькими способами можно разбить 28 задач на 4 варианта?

Решение. Задачи для первого варианта можно выбрать C287 способа-

52

Отметим, что полученное число имеет порядок 1013; число n! с ро-

допустимых выбора.

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

Решение. Если все выбранные камни одного вида, то 3 способа, если выбраны 2 вида камней, то 2C31 6 способов, и если все три камня раз-

личны, то 1 способ. Всего 10 способов.

Задача 107. Хор состоит из 10 участников. Сколькими способами можно в течение трех дней выбирать по 6 участников, так, чтобы каждый день были различные составы хора?

Решение. В первый день участников можно выбрать C106 210 способами, во второй – C106 1 209 и в третий C106 2 208 способами. Всего

210 209 208 = 9 129 120 способов.

Задача 108. Сколькими способами можно выбрать из натуральных чисел от 1 до 30 три числа так, чтобы их сумма была четной?

Решение. Либо все три выбранных числ четны, либо одно четно и два нечетны. Поэтому по правилам суммы и произведения получаем

C153 C151 C152 2030 способов выбора.

Задача 109. Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется хотя бы один туз? Во скольких случаях ровно один туз? Во скольких случаях не менее двух тузов? Ровно два туза?

бами).

Задача 110. Из группы, состоящей из 7 мужчин и 4 женщин, надо выбрать 6 человек так, чтобы среди них было не менее 2 женщин. Сколькими способами это можно сделать?

53

Решение. Можно выбрать двух, трех или четырех женщин. Двух женщин можно выбрать C42 способами. После этого надо выбрать 4 мужчин, что можно сделать C74 способами. По правилу произведения получаем C42 C74 способов. Если выбирают трех женщин, то получают C43 C73

способов, а если четырех – C44 C72 . Всего C42 C74 C43 C73 C44 C72 371 способ.

Задача 111. Из спортивного клуба, насчитывающего 30 членов, надо составить команду из 4 человек для участия в беге на 1000 м. Сколькими способами можно это сделать? А сколькими способами можно составиь команду из 4 человек для участия в эстафете 100+200+400+800?

Ответ. C304 27 405; А304 657 720.

Задача 112. На школьном вечере присутствуют 12 девушек и 15 юношей. Сколькими способами можно выбрать из 4 пары для танца?

Решение. Четырех девушек можно выбрать C124 способами. После этого выбираем А154 способами юношей (здесь уже существен порядок!). Всего C124 А124 17 417 400 способов.

Задача 113. Сколькими способами можно раздать 27 книг лицам А, В и С так, чтобы А и В вместе получили вдвое больше книг, чем С?

Решение. Сначала выберем 9 книг для лица С. Это можно сделать C279 способами. Оставшиеся 18 книг можно разделить между А и В 218 способами. Всего имеем 218 C279 способов раздела.

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

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

Определение. Пусть имеется n элементов, среди которых k1 элементов первого типа, k2 элементов второго типа и т.д., km элементов m-го типа, причем k1 + k2 + ... + km = n. Упорядоченные выборки из таких n элементов по n называются перестановками с повторениями, их число обозначается Cn(k1, k2, ..., km). Числа Cn(k1, k2, ..., km) называются полиномиальными коэффициентами.

Другими словами, если задано множество A = {a1, a2,…, am}, |A| = m, то упорядоченные n-ки, содержащие ki раз элемент ai A (i = 1,2,…, m),

m

причем ki n , называются перестановками с повторением.

i 1

Теорема 7. Если обозначить через Сn(k1, k2, …, km) число всех перестановок с повторением, то

54

Доказательство проведем по индукции, по числу типов элементов m. При m = 1 утверждение становится тривиальным: k1 = n, все элементы одного типа и Cn(n) = 1. В качестве базы индукции возьмем m = 2, n = k1 + k2. В этом случаем перестановки с повторениями превращаются в сочетания из n элементов по k1 (или: выбираем k1 место, куда помещаем элементы первого типа, оставшиеся k2 позиции будут заполнены элементами второго типа). Число таких способов заполнения, очевидно, равно

Пусть формула верна для s = m , то есть n = k1 + ... + km и

n!

Cn(k1, ..., km)= k1 !k2 !...km !.

Докажем, что она верна для s = m + 1 (n = k1 +... + km + km+1). В этом случае перестановку с повторениями можно рассматривать как совмест-

ный выбор двух объектов: объект A – выбор km + 1 места для элементов (m + 1)-го типа; объект B – перестановка с повторениями из (n – km+1) элемен-

тов. Объект A можно выбрать Cnkm 1 способом, B – Cn km 1 (k1, ..., km) способами. По принципу произведения

что и требовалось доказать.

Задача 114. Для множества A = {a, b} составить все перестановки с повторением, если n = 3, k1 = 2, k2 = 1.

Решение. Пользуясь определением перестановок с повторением, получаем (a, a, b), (a, b, a), (b, a, a). Всего три перестановки с повторением.

Задача 115. Найти количество перестановок букв слова «комбинаторика».

Решение. В этом слове 2 буквы «к», 2 буквы «о», 1 буква «м», 1 буква «б», 2 буквы «и», 1 буква «н», 2 буквы «а», 1 буква «т» и 1 буква «р». Таким образом, число перестановок букв этого слова равно:

Задача 116. На узком участке трассы в линию движутся гонщики. Из них 5 на российских автомобилях, 6 – на американских и 3 – на итальянских. Сколько существует разных комбинаций размещения машин на

55

трассе, если интересует только принадлежность автомобиля конкретной стране?

Задача 117. Выходной алфавит абстрактного автомата содержит четыре буквы: y0, y1, y2, y3. Сколько разных выходных слов может выработать автомат при условии, что в выходном слове 2 раза встречаются буквы y0, 4 раза буква y1, 3 раза буква y2 и 1 раз буква y3?

2! 4! 3! 1!

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

Решение. Перестановки, где буквы «е» идут подряд, можно объединить и считать одной буквой. Поэтому число таких перестановок равно 5! Остается C8 4,1,1,1,1 5! 1560 перестановок.

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

Решение. Если «п» идет непосредственно после «о», то эти буквы можно объединить. Поэтому число искомых перестановок равно

C6 2,1,1,1,1 360.

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

Решение. Сначала расставим все буквы слова «обороноспособность», отличные от буквы «о» C11 2,1,1,1,1 способами. После этого вы-

бираем 7 из 12 мест, на которые можно вставить буквы «о». Всего получаем C11 2,1,1,1,1 C127 способов.

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

Решение. Как гласные, так и согласные можно переставлять друг с другом С4(2, 1, 1) = 12 способами. Если согласные уже расставлены, то для гласных остается 5 мест. Поэтому места для них можно выбрать C54 5 способами. Всего имеем 5 122 = 720 способов.

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

Решение. Для слова «кофеварка» первая и последняя буква должны быть согласными. Согласные можно переставлять С5(2, 1, 1, 1) способами, а гласные – С4(2, 1, 1) способами. Всего имеем С5(2, 1, 1, 1) С4(2, 1, 1) = 720 способов. Для слова «самовар» имеем Р4 С3(2, 1) = 72 перестановки.

56

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

Решение. Есть 3 комбинации, содержащие все 3 буквы «т», «а», «р» и 3 комбинации, содержащие по 2 различные буквы. Всего 6 комбинаций. Различных четырехзначных чисел из цифр числа 123 123 можно составить

3 С4(2, 1, 1) +3 С4(2, 2) = 54.

Задача 124. Сколько четырехзначных чисел можно составить из цифр числа 123 153?

Решение. Четырехзначное число может состоять либо из четырех различных цифр (1, 2, 3, 5), либо из двух одинаковых и двух различных цифр ((1, 1, 2, 3); (1, 1, 2, 5); (1, 1, 3, 5); (1, 2, 3, 3); (1, 3, 3, 5); (2, 3, 3, 5)),

либо, наконец, из двух пар одинаковых цифр (1, 1, 3, 3). Поэтому общее количество таких чисел по правилу сумы равно

Р4 + 6 С4(2, 1, 1) + С4(2, 2) = 24 + 6 12 + 6 = 102.

Задача 125. Сколькими способами можно переставить цифры числа 12 341 234 так, чтобы никакие две одинаковые цифры не шли друг за другом?

Решение. Общее число перестановок данных цифр равно С8(2, 2, 2, 2). Из них в С7(2, 2, 2, 1) перестановках данная цифра стоит два раза подряд, в С6(2, 2, 1, 1) повторяются подряд данные 2 цифры, в С5(2, 1, 1, 1) – данные 3 цифры и в С4(1, 1, 1, 1) – данные 4 цифры. По формуле включений и исключений получаем, что никакие 2 цифры не повторяются в

С8(2, 2, 2, 2)–4 С7(2, 2, 2, 1) + 6 С6(2, 2, 1, 1) – 4 С5(2, 1, 1, 1) + + С4(1, 1, 1, 1)= 864 перестановках.

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

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

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

Cnm (n).

Теорема 8. Если обозначить через Cnm (n) число всех сочетаний с по-

вторением, то

Cnm n Cmm n 1 Cmn 1n 1 .

57

Доказательство. Пусть в выборку вошло m1 элементов первого типа, m2 элементов второго типа, ...mn – n-го типа. Причем каждое 0 m i m и m1+m2+ ...+ mn= m. Сопоставим этой выборке вектор следующего вида:

ных выборок с повторениями и множеством векторов {bn} существует би-

екция (докажите это!). Следовательно, Cnm (n) равно числу векторов bn. “Длина вектора” bn равна числу 0 и 1, или m+n–1. Число векторов равно числу способов, которыми m единиц можно поставить на m + n 1 мест, а

это будет Cnm m 1 .

Отличительной особенностью данного способа сочетания является многократное, но не более m раз, использование при выборке одного и того же элемента множества Х.

Задача 126. Дано множество M = {1, 2, 3}. Укажите всевозможные

Пример 127. Для множества A = {a, b} составить все сочетания с повторениями, содержащие три элемента (m = 2, n = 3).

Решение. Следуя определению, получаем aaa, aab, abb, bbb.

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

Решение. Поскольку при составлении шоколадного набора порядок расположения шоколадок не важен, то используем для подсчета формулу сочетаний с повторениями:

Задача 129. Требуется купить 7 пирожных. В магазине имеются пирожные следующих видов: эклеры, песочные, слоеные и наполеоны. Сколько существует вариантов выбора, если в магазине имеется не менее 7 штук каждого вида пирожного?

Решение. Выбранные пирожные заменяем единицами, и добавляем три нуля (разделителя). Каждой перестановке однозначно соответствует некоторый выбор. Например, одному из вариантов покупки будет соответствовать такой код: 1101110101. Пирожные покупаются следующим образом. Количество единиц слева до первого нуля соответствует покупке эклеров, между первым и вторым нулем – покупке песочных, между вто-

58

рым и третьим – покупке слоеных, единицы после третьего нуля соответствуют числу покупаемых наполеонов. В случае приведенного кода покупается 2 эклера, 3 песочных, 1 слоеное и 1 наполеон. Количество вариантов покупки пирожных равно числу перестановок из 7 объектов одного типа (единиц) и 3 объектов второго типа (нулей). Если имеются предметы n разных типов (без ограничения числа предметов каждого типа) и требуется определить, сколько комбинаций можно сделать из них, чтобы в каждую комбинацию входило m предметов? Каждую комбинацию шифруем с помощью 0 и 1, причем 1 соответствуют предметам, а 0 выполняют функцию разделителей. Тогда записав m единиц и добавив n – 1 нуль, мы получим комбинацию, при которой выбираются m предметов первого типа и ни одного предмета остальных типов. Переставляя всеми способами эти m единиц и n – 1 нуль, будем каждый раз получать некоторую расстановку, состоящую из m предметов. Тогда

Задача 130. Входной алфавит абстрактного конечного автомата содержит 5 символов, например, a, b, c, d, f. Входные слова имеют длину в 11 символов. Сколько разных слов может быть подано на вход конечного автомата, если слова, имеющие одинаковый состав букв и различающиеся только порядком, считать одинаковыми? Например, слова baabcf и fabcba считаются одинаковыми.

Задача 131. Граф-схема алгоритма микропрограммного автомата содержит операторные и условные вершины. Операторные вершины “начало” и “конец” обязательны. Сколько существует разных граф-схем алгоритмов, содержащих 6 вершин, если нас интересует только количественный состав, а не связи между вершинами?

Задача 132. В почтовом отделении продаются открытки 10 сортов. Сколькими способами можно купить в нем 12 открыток? Сколькими способами можно купить 8 открыток? Сколькими способами можно купить 8 различных открыток?

Задача 133. Сколько существует треугольников, длины сторон которых принимают одно из значений 4, 5, 6, 7?

Решение. Имеем сочетания с повторениями из 4 элементов сортов по три элемента в сочетании. Их число равно C43 4 C63 20 .

59

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

Ответ. C103 10 C123 220.

Задача 135. Найдите натуральное число n, удовлетворяющее урав-

n! 2 n 1 ! n 5 ;

n n 1 ! 2 n 1 ! n 5 ; n 2 n 5 ;

n 10.

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

Определение. Упорядоченные выборки объемом m из n элементов, где элементы могут повторяться, называются размещениями с повторениями. Их число обозначается Anm n .

Теорема 9 (Теорема о числе размещений с повторениями).

Anm n = nm.

Доказательство. Первый элемент может быть выбран n способами, второй элемент также может быть выбран n способами и так далее, m-й элемент также может быть выбран n способами. По принципу произведения получаем nm .

Отличительной особенностью размещения из n по m с повторением является произвольное повторение, но не более m раз, каждого элемента множества Х в каждой выборке.

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

Ответ. Множество комбинаторных объектов равно:

(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2).

Комбинаторное число размещения из 2-х элементов по 3 с повторением равно: A23 2 .=23=8.

60