Конечного множества и соответствующие им формулы

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

Пусть дано множество , состоящее из n различных элементов.

Определение1.Размещениями без повторений из n элементов по mназываются упорядоченные m-элементные подмножества множества Е, отличающиеся либо набором элементов, либо порядком их следования.

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

Задача 1. Сколькими способами можно выбрать из группы, насчитывающей 40 студентов, старосту, профорга и физорга?

Решение. Любой выбор является размещением без повторений из 40 элементов по три (он задается упорядоченным множеством из трех элементов без повторений, составленным из множества студентов); поэтому число способов выбора равно = 40×39×38 = 59280.

Задача 2. Сколькими способами можно опустить 5 писем в 11 почтовых ящиков, если в каждый ящик опускается не более одного письма?

Решение. В этой задаче речь также идет о выборе пяти ящиков из 11, при этом порядок выбора ящиков важен. Отсюда искомое число равно = 11×10×9×8×7 = 55440.

Определение2.Размещения без повторений из n элементов поn (n m ) называются перестановками без повторений из n элементов.

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

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

!

Используя эту формулу, число размещений из из n элементов по mможно найтииначе: .

Задача 3. Три студента победили в олимпиаде по математике. Сколько существует способов вручения им дипломов первой, второй и третьей степени?

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

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

Решение. Каждому стулу соответствует какой-нибудь один цвет. Поэтому способов обивки стульев будет столько, сколькими способами можно распределить 6 предметов на шести местах, то есть числу перестановок из шести элементов без повторений:

Определение 3. Перестановкой с повторениями из элементов ( , ,…, )состава ( ,…, ) называется упорядоченное множество, содержащее элементов, в которое элемент входит раз, элемент входит раз,…, элемент входит раз.

Число таких перестановок обозначают символом Р( …, ).

Р( …, ) =

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

Решение. Слово «математика» является упорядоченным множеством из 10 элементов, т.е. перестановкой из 10 элементов с повторениями состава (2, 3, 2, 1, 1, 1) (буква «м» входит в перестановку 2 раза, буква «а» – 3 раза, буква «т» – 2 раза, буквы «е», «и», «к» – по одному разу). Значит, при перестановках букв получится

Р(2, 3, 2, 1, 1, 1) «слов».

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

Решение. Поскольку нам надо разложить все 28 предметов, то речь идет о перестановках из 28 элементов, а так как порядок расположения предметов в одном ящике несущественен, то имеем дело с перестановками с повторениями типа (7,7,7,7). Таким образом, искомое число способов равно

Р(7,7,7,7) = .

Определение 4.Сочетаниями без повторений из n элементов по mназываются m-элементные подмножества множества Е, содержащие разные наборы элементов.

Из определения следует, что различные сочетания отличаются друг от друга составом элементов. Формула для вычисления числа сочетаний без повторений из n элементов по mимеет вид .

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

Решение. По условию задачи необходимо выбрать четырех человек из 10, при этом порядок выбора значения не имеет. Это значит, что речь идет о сочетаниях из 10 по 4. Число таких сочетаний равно .

Задача 8. У одного человека есть 11 книг по математике, а у другого – 15 книг. Сколькими способами они могут выбрать по 3 книги каждый для обмена?

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

Задачи

73. В цехе работают 8 токарей. Сколькими способами можно поручить трем из них изготовление трех различных видов деталей (по одному виду на каждого)?

74. Сколькими способами можно опустить 5 писем в 11 почтовых ящиков, если в каждый ящик опускают не более одного письма?

75. Сколькими способами можно посадить за круглый стол 5 мужчин и 5 женщин так, чтобы никакие два лица одного пола не сидели рядом?

76. Сколькими способами могут разместиться 20 человек в пяти вагонах метро, если каждый человек занимает место независимо от другого? (Важно не только то, сколько человек село в каждый вагон, но и то, кто из 20 человек в какой вагон сел ).

77. Сколько различных «слов» можно получить, переставляя буквы в слове 1) «математика», 2) «парабола», 3) «следователь»?

78. Сколькими способами можно переставлять буквы: 1) слова «перешеек» так, чтобы четыре буквы «е» не шли подряд? 2) слова «огород» так, чтобы три буквы «о» не шли подряд? 3) слова «обороноспособность» так, чтобы две буквы «о» не шли подряд?

79. Сколькими способами можно выбрать 12 человек из 17, если данные два человека из этих 17 не могут быть выбраны одновременно?

80. . Сколькими способами можно разбить 30 рабочих на 3 бригады по 10 человек в каждой бригаде? На 10 групп по 3 человека в каждой?

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

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

83. Из урны, содержащей 10 шаров, из которых 4 белых и 6 красных, извлекают 3 шара и откладывают в сторону. Сколькими способами это можно сделать так, чтобы а) все отложенные шары оказались белыми? б) среди отложенных шаров белых оказалось ровно 2?

84. 7 яблок, 3 апельсина и 5 лимонов раскладываются в три пакета, но так, чтобы в каждом было одинаковое количество фруктов. Сколькими способами это можно сделать так, чтобы в каждом пакете находилось по одному апельсину?

85. На собрании должны выступить 5 человек: А, Б, В, Г, Д. Сколькими способами можно расположить их в списке ораторов, если 1) Б не должен выступать до того, как выступил А; 2) если Б должен выступить сразу после А?

86. Сколькими способами можно поставить 8 шашек на черные поля доски?

87. Сколькими способами можно поставить на черные поля доски 12 белых и 12 черных шашек?

88. Сколькими способами можно заполнить карточки «Спортлото» (зачеркнуть 6 номеров из 49)? Во скольких случаях из выбранных шести номеров после тиража три окажутся угаданными правильно? Во скольких случаях правильно будут угаданы 4 номера? 5 номеров? 6 номеров?

89. 20 различных деталей раскладывают в три ящика, причем в первый ящик кладут три детали, во второй – 5 деталей, а в третий – все остальные детали. Сколькими способами это можно сделать?

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

91. Сколько шестизначных чисел можно составить из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9, если каждое число должно состоять из трех четных и трех нечетных цифр, причем никакие две цифры в нем не повторяются?

92. В лаборатории работают 8 физиков и 10 химиков. Надо создать рабочие группы по трем темам. В первую группу должны войти 4 физика, во вторую – 5 химиков, а третья должна состоять из трех человек, которые могут быть как физиками, так и химиками. Сколькими способами можно создать такие группы?

93. В течение 10 недель студенты должны написать 10 контрольных работ, в том числе 2 по математике. Сколькими способами можно составить расписание этих работ так, чтобы контрольные работы по математике не шли друг за другом?

94. В первой группе класса «А» первенства по футболу участвуют 17 команд. Разыгрываются медали: золотые, серебряные и бронзовые. Сколькими способами они могут быть распределены?

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

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

97. 13 человек обменялись рукопожатиями. Сколько было рукопожатий?

98. Сколько хорд определяют 5 точек окружности?

99. Каждый телефонный номер состоит из 7 цифр. Сколько телефонных номеров не содержит других цифр, кроме цифр 2, 3, 5, 7?

100. Сколькими способами из 12 различных конфет можно составить набор, если в наборе должно содержаться четное количество конфет?

101. В мешке содержатся 8 шаров: 3 красных и 5 зеленых. Сколькими способами из мешка можно вынуть два шара разного цвета? два шара одного цвета?

102. Сколько пятибуквенных «слов» можно составить из 7 гласных и 25 согласных букв, если гласные и согласные буквы в «слове» должны чередоваться? Решите эту задачу при условии, что ни одна буква в слове не должна повторяться.

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

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

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

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

107. В комнате студенческого общежития живут трое студентов. У них есть 4 чашки, 5 блюдец, 6 чайных ложек (все чашки, ложки и блюдца отличаются друг от друга). Сколькими способами они могут накрыть стол для чаепития?

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

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

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

111. Шифр камеры хранения состоит из одной буквы и трех цифр. Сколько можно набрать разных шифров, если имеется 11 букв и 10 цифр?

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

113. Сколько чисел, меньших, чем миллион, можно записать с помощью цифр 8 и 9?

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

115. Даны 6 цифр: 1, 2, 3, 4, 5, 6. Сколько четырехзначных чисел можно составить, используя эти цифры, если: а) никакие цифры в числе не встречается не более одного раза? б) повторения допустимы? в) числа должны быть четными? г) числа должны делиться на 4?

116. Сколькими способами из 15 человек можно выбрать группу людей для работы, если в группу могут входить от трех до 14 человек?

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

118. Сколько различных браслетов можно сделать из пяти одинаковых изумрудов, шести одинаковых рубинов и семи одинаковых сапфиров (в браслет входят все 18 камней)?

119.Сколькими способами можно из тех же камней выбрать 3 камня для кольца?

120.Стороны каждой из двух игральных костей помечены числами 0,1,3, 7,15, 31. Сколько различных сумм может получиться при метании этих костей?

121.Сколькими способами можно разложить 10 книг на 5 бандеролей по 2 книги в каждой (порядок бандеролей во внимание не принимается)?