Правила суммы и произведения

Правило суммы. Если объект А может быть выбран т способами, а объект В - п способами, причем выборы объектов А и В несовместны, то выбор «либо А либо В» может быть осуществлен т + п способами.

Пример 1. В киоске имеется 11 видов открыток «Поздравляю! », 7 видов - «С Новым годом! » и 3 вида – «С Рождеством! ». Сколькими способами можно выбрать одну поздравительную открытку?

Решение.

Найдем число способов, которыми можно выбрать открытку каждого вида. Открытку «Поздравляю! » можно выбрать 11 способами, «С Новым годом! » - 7 способами и «С Рождеством! » - 3 способами. Эти выборы несовместны. Поэтому по правилу суммы находим, что поздравительную открытку можно выбрать N = 11 + 7 + 3 = 21 способом.

Ответ: N = 21.

Правило произведения. Если объект А может быть выбран т способами, а объект В может быть выбран п способами, то выбор упорядоченной пары (А, В) может быть осуществлен т∙ п способами.

Пример 2. В классе 12 девочек и 13 мальчиков. Сколькими способами можно выбрать двух человек для уборки класса, если в паре должны быть мальчик и девочка?

Решение.

Для дежурства в классе девочку можно выбрать 12 способами, мальчика – 13 способами. Применяя правило произведения найдем число возможных пар, равное N =12 ∙ 13 = 156.

Ответ: N = 156.

Основное правило комбинаторики. Если объект А₁ может быть выбран k₁ способами, объект А₂ - k₂ способами, объект А₃ - k₃ способами, ..., а объект А_п - k_п способами, то выбор кортежа (А₁, А₂, А₃, ..., А_п) может быть осуществлен k₁∙ k₂∙ k₃∙ ...∙ k_п способами.

Основное правило комбинаторики является обобщением правила произведения.

Пример 3. Сколько четырехзначных чисел можно составить из цифр 1, 2, 3, 4, если цифры в числе не повторяются?

Решение.

На месте тысяч поставим любую из четырех цифр. После каждого такого выбора на месте сотен можно поставить любую из трех оставшихся цифр, а на месте десятков можно поставить любую из двух оставшихся цифр, так как цифры и числе не повторяются. На месте единиц можно поставить оставшуюся одну цифру. Применяя основное правило комбинаторики найдем число четырехзначных чисел, равное N = 4∙ 3∙ 2∙ 1 = 24.

Ответ: N = 24.

Правило включений и исключений. Если объект А можно выбрать т способами, объект В - п способами, а выбор пары (А, В) может быть осуществлен р способами. То выбор объектов «либо А либо В» может быть осуществлен т + п – р способами.

Правило включений и исключений является обобщением правила суммы, оно может быть распространено на сколь угодно большое число объектов.

Если объект А₁ может быть выбран k₁ способами, объект А₂ - k₂ способами, объект А₃ - k₃ способами, ..., а объект А_п - k_п способами, причем выбор каждого кортежа (А_i, А_j, ..., А_l) может быть осуществлен р_i способами, то для любых объектов А₁, А₂, А₃, ..., А_п справедлива следующая формула

N = k₁ + k₂ + k₃ +...+ k_п – р₁– р₂–... р_i +... + (-1)^п^-1∙ р_m,

где п – число мест в кортеже.

Пример 4. В форме и по материалам ЕГЭ вступительные испытания в вуз по биологии сдавали 137 абитуриентов, по информатике – 51, по химии – 28, по биологии и информатике – 17, по биологии и химии – 13, по информатике и химии – 11, по всем трем предметам – 2. Сколько абитуриентов сдавали хотя бы один из перечисленных экзаменов?

Решение.

Обозначим через А₁ – множество абитуриентов, сдававших ЕГЭ по биологии, через А₂ – по информатике, через А₃ – по химии. Тогда k₁ = 137, k₂ = 51, k₃ = 28, р₁ = 17, р₂ = 13, р₃ = 11, р₄ = 2.

Следовательно, N = 137 + 51 + 28 + (-1)^2-1∙ 17 + (-1)^2-1∙ 13 + (-1)^2-1∙ 11 + + (-1)^3-1∙ 2 = 216 – 41 + 2 = 177.

Ответ: N = 177.

Виды комбинаторных задач

Размещениями с повторениями из п элементов по k называют кортежи длины k, составленные из элементов множества X, содержащего п элементов, причем элементы в кортеже могут повторяться. Число таких размещений выражается формулой

= .

Пример 1. Сколько четырехзначных чисел можно составить из цифр 1, 2, 3?

Решение.

Рассматриваемое множество состоит из трех различных элементов: 1, 2, 3. При этом порядок расположения цифр в записи числа имеет существенное значение, цифры могут повторяться, а количество цифр в числе равно четырем. Следовательно, необходимо составить размещения с повторениями из трех элементов по четыре. А это число равно

= 3⁴ = 81.

Ответ: = 81.

Размещениями без повторений из п элементов по k называют кортежи длины k, составленные из элементов множества X, содержащего п элементов, причем элементы в кортеже не повторяются. Число таких размещений выражается формулой

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

Решение.

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

Ответ: = 600.

Если k = п, то говорят о перестановках без повторений. Их число выражается формулой

Пример 3. Сколько пятизначных чисел можно составить из цифр 1, 2, 3, 5, 7, если цифры в записи числа не повторяются.

Решение.

Так как число элементов в множестве равно числу мест в кортеже k = п = 6, то имеют место перестановки без повторения. Значит количество пятизначных чисел равно .

Ответ:

Пусть в кортеже длины п, составленном из элементов множества X = {х₁, х₂, ..., х_l}, гдеэлемент х₁– повторяется k₁ раз, элемент х₂– повторяется k₂ раза, ..., элемент х_l – повторяется k_l раз (k₁ + k₂ +... + k_l = п).

Такие кортежи называют перестановками с повторениями из k₁ элементов х₁, k₂ элементов х₂,..., k_l элементов х_l. Их число выражается формулой

, где k₁ + k₂ +... + k_l = п.

Пример 4. Сколькими способами можно переставить буквы слова «математика»?

Решение.

Рассматриваемые кортежи состоят из 10 элементов. При этом буква «м» повторяется 2 раза, «а» - 3 раза, «т» - 2 раза, «е» - 1 раз, «и» - 1 раз, «к» - 1 раз. Следовательно кортежи имеют вид (2, 3, 2, 1, 1, 1). Следовательно, число способов, которыми можно переставить буквы слова «математика» равно .

Ответ: .

Если множество А содержит п элементов, то его подмножества, содержащие k элементов, называются сочетаниями из п элементов по k элементов без повторений. Их число выражается формулой

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

Решение.

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

Ответ:

Разобьем множество всех кортежей длины п, составленных из элементов множества X = {х₁, х₂, ..., х_k}на классы эквивалентности, отнеся к одному классу кортежи одинакового состава. Эти классы эквивалентности называют сочетаниями с повторениями из п элементов поk.Их число выражается формулой

Пример 6. В питомнике продаются саженцы 5 сортов фруктовых деревьев. Сколькими способами можно выбрать 7 саженцев для пришкольного сада?

Решение.

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

Ответ:

* *

265. В городе 3 института и 5 средних профессиональных учебных заведений. Сколькими способами выпускник школы может выбрать учебное заведение для продолжение обучения?

266. В городе 7 музыкальных школ и 3 художественные школы. Сколькими способами можно выбрать музыкальную и художественную школу для получения дополнительного образования?

267. В классе 5 человек играют на фортепиано, 3 человека, занимаются вокалом, 7 в кружке художественного слова. Сколькими способами можно выбрать одного человека так, чтобы он хорошо пел или декламировал стихи? Сколькими способами можно составить группу из трех человек для участия в школьном концерте так, чтобы в нее вошли аккомпаниатор, чтец и певец?

268. В студенческой столовой имеется 3 вида первых блюд, 4 вторых, 3 третьих и два вида салата. Сколькими способами студент может выбрать комплексный обед?

269. У одного студента имеется 7 книг Л.Н. Толстого, а у другого 9 книг А.П.Чехова. Сколькими способами они могут обменять книгу на книгу?

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

271. Сколько различных трехзначных чисел, меньших 300 можно составить из нечетных цифр при условии, что цифры в записи числа не повторяются? Решите ту же задачу при условии, что цифры в записи числа могут повторяться.

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

273. В магазине имеется 7 сортов шоколадных конфет и 3 сорта карамели. Сколько различных покупок конфет одного сорта можно сделать в этом магазине? Сколько можно сделать различных покупок, содержащих один сорт шоколадных конфет и один сорт карамели.

274. Из 100 человек 1 курса английский язык изучают 50 человек, немецкий - 38, французский - 11, английский и немецкий – 15, английский и французский - 7, немецкий и французский – 5. Все три языка изучают три студента. Сколько студентов изучает только один язык? Сколько студентов не изучает ни одного языка?

275. Сколько чисел содержится в множестве М, если известно, что среди них 50 чисел кратно двум; 57 – трем; 60 – пяти; 22 – шести; 19 – десяти; 25 – пятнадцати; 10 чисел – тридцати? Сколько из данных чисел делятся только на одно из чисел два, три или пять?

276. По результатам промежуточной аттестации, были получены следующие данные об успеваемости студентов первого курса: из 25 человек 1 группы сдали сессию на «хорошо» и «отлично» по математике 16 человек, по отечественной истории – 15, по возрастной анатомии – 17, по математике и истории – 11 человек, по математике и анатомии – 8 человек, по истории и анатомии – 7 человек, 6 человек успешно сдали сессию по всем предметам. Докажите, что данные сведения не могут быть верными.

277. В течение 30 дней сентября было 12 дождливых дней, 8 ветреных, 4 холодных, 5 дождливых и ветреных, 3 дождливых и холодных, 2 ветреных и холодных, а один день был дождливым, ветреным и холодным. В течении скольких дней в сентябре стояла хорошая погода?

278. Трое студентов сдают экзамен. Сколькими способами могут быть поставлены им оценки, если известно, что никому из них не будет поставлена неудовлетворительная оценка?

279. В некотором государстве не было двух жителей с одинаковым набором числа зубов. Какая может быть наибольшая численность населения государства, если полное число зубов у человека равно 32?

280. Сколько четырехзначных чисел можно образовать из цифр 1, 2, 3. Сколько из них будет четными?

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

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

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

284. Сколько четырехзначных чисел имеется в пятеричной системе счисления?

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

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

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

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

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

290. Из 25 студентов группы, среди которых только один юноша, выбираются для дежурства 3 человека. Сколькими различными способами это можно сделать? В скольких случаях в число дежурных попадет юноша?

291. В магазине «Детский мир» продаются мягкие игрушки 5 видов (собачки, зайцы, медведи, кошки и обезьянки). Сколько можно составить различных наборов игрушек для детского сада из 11 игрушек в каждом?

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

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

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

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

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

297. В состав сборной включены 2 вратаря, 5 защитников, 6 полузащитников и 6 нападающих. Сколькими способами можно составить команду в которую входит вратарь, 3 защитника, 4 полузащитника и 3 нападающих?

298. Из полного набора шахмат вынули 4 фигуры или пешки. Во скольких случаях среди них окажется: а) два коня, б) не менее двух коней?

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

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

События и их вероятности

Предыдущая 1 2 3 4 567 8 9 10 Следующая