Основные правила комбинаторики.




Правило суммы: если некоторый объект а можно выбрать m способами, а объект b можно выбрать n способами, то выбор «а или b » можно осуществить

N 1 =(m + n) способами. (4)

Задача 9. От посёлка Горелки до областной больницы г. Тулы можно доехать через Октябрьский посёлок или центр города через Пролетарский мост. В первом случае можно воспользоваться автобусом № 23 или собственным автомобилем (количество вариантов равно 2), во втором – маршрутным такси № 23, маршрутным такси № 32 или воспользоваться собственным автомобилем (количество вариантов – 3). Сколькими способами можно добраться из посёлка Горелки до областной больницы?

Решение.

Очевидно, что число разных вариантов проезда от посёлка до больницы 2 + 3 = 5.·

 

Задача 10. Пусть а – число, делящееся без остатка на два, b – число, делящееся без остатка на три. Сколькими способами можно выбрать «а или b » на множестве М = {1, 2, 3, 4, 5}?

Решение.

1) Числа, делящиеся без остатка на 2, – это числа 2 и 4, т.е. m = 2.

2) Без остатка на 3 из заданного множества М делится только число 3, т.е. n = 1.

3) Число искомых способов (m + n) = 2 + 1 = 3.·

 

Если способы выбора объекта типа а совпадают со способами выбора объекта типа b, то из формулы (4) следует вычесть число таких совпадений

N 2 = (m + nk), где k – число совпадений.

Задача 11. Пусть а – число, делящееся без остатка на два, b – число, делящееся без остатка на три. Сколькими способами можно выбрать «а или b » на множестве М = {1, 2, 3, 4, 5, 6}?

Решение.

1) Числа, делящиеся без остатка на 2, – это числа 2, 4 и 6, т.е. m = 3.

2) Числа, делящиеся без остатка на 3, – это числа 3 и 6, т.е. n = 2.

3) Число совпадений k = 1, т.к. 6 попадает в первую и вторую выборку. Тогда число искомых способов (m + nk) = 3 + 2 – 1 = 4.·

 

Правило произведения. Пусть некоторый выбор требует выполнения од­ного за другим k действий. Если первое действие можно выполнить n 1 способами, второе (после него) — n 2 способами, третье — n 3 способами и так до k -гo действия, которое можно выполнить nk способами (после вы­полнения предыдущих (k – 1) действий), то все k действий в указанном по­рядке можно выполнить(n l× n 2´...´ nk) способами.

 

Решим задачу 1 настоящего раздела, используя правило произведения.

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

Решение.

Так как по условию задачи каждый учащийся может быть избран комсоргом, то, очевидно, существует 30 способов выбора комсорга. Старостой может стать каждый из оставшихся 29 чело­век. Любой из 30 способов выбора комсорга может осуществляться вместе с любым из 29 способов выбора старосты. Поэтому суще­ствует 30 × 29 = 870 способов выбора комсорга и старосты.·

Решим задачу 4 настоящего раздела, используя правило произведения.

Задача 4. Для дежурства в классе в течение недели (кроме воскресенья) выделены 6 учащихся. Сколькими способами можно установить очередность дежурств, если каждый учащийся дежурит один раз?

Решение.

В понедельник может дежурить любой из выделенных шести человек. Во вторник может дежурить каждый из еще не дежу­ривших пяти учащихся. Следовательно, расписание дежурств на первые два дня недели можно составить 6 × 5 способами. К среде остаются четыре человека, которые еще не дежурили, и поэтому на среду дежурного можно будет назначить 4 способами. Таким образом, существует 6 × 5 × 4 способов установления очередности дежурств на первую половину недели. В четверг сможет дежурить любой из трех еще не дежуривших учащихся, в пят­ницу — любой из двух еще не дежуривших. К субботе выбора не будет, так как останется один человек, который еще не дежурил. Он и будет дежурным в субботу. Ясно, что число способов, кото­рыми можно установить очередность дежурств учащихся, равно 6 × 5 × 4 × 3 × 2 × 1 = 720.·

Задача 12. Из Перми до Чайковского можно добраться теплоходом, поездом, автобусом или самолетом; из Чайковского до Ижевска — тепло­ходом или автобусом. Сколькими способами можно осуществить путеше­ствие по маршруту Пермь—Чайковский—Ижевск?

Решение.

Число разных путей из Перми до Ижевска равно 4 × 2 = 8, так как, выбрав любой из четырех возможных способов путешествия из Перми до Чайковского, имеем 2 возможных способа путешествия из Чай­ковского до Ижевска.·

Задача 13. Сколько существует целых четырёхзначных чисел, не делящихся на 5 без остатка? Целое число не делится на 5, если оно не за­канчивается на 5 или на 0.

Решение.

Первую значащую цифру можно выбирать девятью способами (все цифры, кроме нуля), вторую и третью – десятью способами, а четвертую лишь восе­мью (все цифры, кроме 0 и 5). Следовательно, целых четырёхзначных чисел, не делящихся на 5 без остатка, существует:

9 × 10 × 10 × 8 = 7200, где n 1 = 9, n 2 = n 3 = 10, n 4 = 8 (см. правило произведения).·

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-12 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: