Элементы комбинаторики

Элементы комбинаторики

Элементы комбинаторики

1. Комбинаторика. Основные комбинаторные правила. 2. Клас­сификация соединений элементов некоторого множества. 3. Формулы для подсчета числа размещений, перестановок, сочетаний

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

событий W и подсчитать число элементарных событий, благоприятствующих случайному событию А.

Сформулируем на языке событий два правила, которые применяются при комбинаторных подсчетах.

Правило суммы. Если событие А может осуществиться m способами, а независимое от него событие В – n способами, то событие «или А, или В», т. е. событие А + В может осуществиться k = m + n способами.

Пример 2.1. Шарики распределены по двум ящикам: в первом m шариков, во втором – k. Произвольно из какого-либо ящика вынимаем шарик. Сколькими способами это можно сделать?

Из первого ящика шарик можно вынуть m разными способами, из второго – k разными способами. Всего способов: n = m + k.

Ответ: n = m + k.

Правило произведения (основное правило комбинаторики). Если событие А может осуществиться m способами, а независимое от него событие В – n способами, то событие «А и В», т. е. событие А × В, может осуществиться k = m × n способами.

Пример 2.2. а) Сколько двузначных чисел можно записать в десятичной системе счисления?

Число десятков

Поскольку число двузначное, число десятков может принимать одно из девяти значений 1, 2,…,9. Число единиц может принимать те же значения и может быть, кроме того, равным нулю. Всего получаем двузначных чисел 9 × 10 = 90 (рис. 2.1).

Ответ: 90.

б) Из города А до города В можно добраться автобусом, самолетом, теплоходом, поездом, из города В в город С – теплоходом и автобусом. Сколькими способами можно осуществить путешествие по маршруту А ® В ® С?

Рис.2.2

Очевидно, что число разных путей равно 4 × 2 = 8 (рис. 2.2).

Ответ: 8.

Замечание. Если требуется выполнить одно за другим k действий, причем первое действие можно выполнить n1 способами, второе – n2 способами, …, k-е – nk способами, то все k действий вместе можно выполнить n1 × n2 × …× nk способами.

Пример 2.3. В группе изучается 10 дисциплин. Сколькими способами можно составить расписание на понедельник, если в понедельник 6 уроков, причем все уроки разные.

Ответ: 10 × 9 × 8 × 7 × 6 × 5 = 151 200.

Рассмотрим множество n элементов {a1, a2, …, an}, которое в комбинаторике принято называть генеральной совокупностью объема n.

Соединениями называют комбинации (наборы), составленные из элементов генеральной совокупности, которые отличаются друг от друга или элементами, или порядком элементов в комбинации. Соединение можно получать, выбирая, например, элементы. Выборкой длины r называют соединение из r элементов генеральной совокупности объемом n. Различают выборки:

·  упорядоченные (характеризуются и составом элементов, и последовательностью извлечения);

·  неупорядоченные (характеризуются только составом элементов).

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

Способы получения выборок из генеральной совокупности могут быть двух видов:

·  выбор без возвращения элементов, в этом случае говорят о выборках без повторения (т. е. о выборках, которые не имеют одинаковых элементов);

·  выбор с возвращением элементов, тогда говорят о выборках с повторениями (т. е. о выборках, имеющих одинаковые элементы).

В таблице приведены формулы, по которым вычисляют число способов получения различных выборок.

Принятые обозначения:

Соединения, не содержащие одинаковых элементов: размещения – , перестановки – Рn, сочетания – .

Соединения, содержащие одинаковые элементы: размещения –, перестановки – Рn (n1, n2, …, nr), где n1, n2, …, nr – число одинаковых элементов первого, второго,…, r-го типа, сочетания – .

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

Ситуация 1. Предположим, что r неразличимых частиц распределяются по n ячейкам (r £ n) при условии, что в каждой ячейке может находиться не более одной частицы.

Число различных размещений (элементарных исходов) совпадает с числом выбора r занятых ячеек из общего числа ячеек n, т. е. равно . Рассмотрим событие А – заняты k фиксированных ячеек (k £ r). Тогда оставшиеся n – k ячеек должны быть заполнены r – k частицами, а это можно сделать способами.

Ситуация 2. Предположим, что генеральная совокупность имеет
n = n1 + n2 +…+ nk различных элементов, причем из них n1 элементов первого типа, n2 – второго типа, …, nk – k-го типа. Случайным образом из этих n элементов выбирается m = m1 + m2 +…+ mk элементов, причем среди выбранных оказывается ровно m1 £ n1 элементов первого типа, m2 £ n2 – второго типа, … , mk £ nk – k-го типа (событие А). Поскольку порядок выбора несуществен, то при подсчете общего числа соединений из n элементов по m мы должны воспользоваться числом сочетаний . Далее, m1 частиц первого рода мы можем выбрать способами, m2 частиц второго рода – способами, …, mk частиц
k-го типа – способами. Число благоприятных событию А исходов равно× × … × (использовали основное правило комбинаторики – правило умножения).

Пример 2.4. а) Из колоды, содержащей 52 карты, наугад выбирают четыре. Число способов выбрать из 52 четыре карты –, а ×– число способов составить соединение, содержащее 1 туз.

б) У сборщика 12 деталей, мало отличающихся друг от друга. Из них пять – первого вида, 4 – второго и 3 – третьего (12 = 5 + 4 + 3). Берут одновременно 6 деталей. Число способов составить соединение, содержащее 3 детали первого вида, 2 – второго и 1 – третьего, – ××.

Замечание. При подсчете числа сочетаний можно пользоваться свойствами сочетаний:

·  правило симметрии = ;

·  правило Паскаля = + .

Рассмотрим примеры, в которых используются все виды соединений, изученных нами.

Пример 2.5. (размещение без повторения – число способов составить упорядоченную выборку, не содержащую одинаковых элементов ).

1) Число телефонных номеров из 6 цифр, если все цифры различны, – = 10 × 9 × 8 × 7 × 6 × 5 = 151 200.

2) Число четырехбуквенных «слов», которые можно образовать из букв слова «around», – = 6 × 5 × 4 × 3 = 360.

3) Число «слов», которые можно записать, если карточки с буквами К, Ю, А, И, Г перетасовать, затем вынимать наугад и записывать в том порядке, в каком они были вынуты, – = Р5 = 5! = 120.

4) Число способов распределить первую, вторую и третью премии на конкурсе, в котором участвуют 20 человек, – = 20 × 19 × 18 = = 6840.

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

1) Число телефонных номеров из 6 цифр, при условии, что любая цифра может повторяться, – = 106 = 1 000 000.

2) Число «слов», которые можно записать, если карточки с буквами К, Н, А, И, Г перетасовывают и вынимают по одной с последующим возвращением – = 55 = 3125.

3) Число способов 5 пассажирам лифта выйти на любом этаже девятиэтажного дома начиная со второго – = 85 = 32 768.

Пример 2.7. (перестановки без повторения – частный случай размещений без повторения Рn).

1) Для лечения заболевания применяют 5 лекарств. Полагают, что последовательность, в которой применяют лекарства, оказывает существенное влияние на результаты лечения. Число различных порядков назначения этих лекарств – Р5 = 5! = 1× 2× 3× 4 ×5 = 120;

2) Менеджер ежедневно просматривает 6 печатных изданий экономического содержания. Если порядок просмотра случаен, то осуществить это можно Р6 = 1× 2× 3× 4 ×5 ×6 = 720 способами.

Пример 2.8 (перестановки с повторением – Pn (n1, n2, …, nr)).

1) Число «слов», которые можно составить из букв слов: «error» – Р5 (3) = = 20, «letters» – Р7 (2, 2) = = 1260;

2) Три типа бактерий культивируются в 9 пробирках. В трех пробирках содержатся бактерии первого типа, в четырех – второго типа и в двух – бактерии третьего типа. Сколькими различными способами можно расположить пробирки в ряд на штативе, если нам важно расположение лишь типов бактерий? Число различных перестановок –
Р9 (3, 4, 2) = = 1260;

Пример 2.9 (сочетание без повторения – число способов составить неупорядоченную выборку, которая не имеет одинаковых элементов).

1) Правление коммерческого банка из 10 кандидатов выбирает 3 сотрудников на одинаковые должности (все 10 кандидатов имеют равные шансы). Число возможных групп по 3 человека, которые можно составить из 10 кандидатов, – = 120.

2) Комитет состоит из 12 членов. Минимальный кворум на заседаниях этого комитета – 8 человек.

·  минимальный кворум достигается = 495 способами.

·  какой-либо кворум достигается, если присутствуют 8, 9, 10, 11 или 12 человек. Число способов достижения кворума (используем правило сложения):

= 495 + 220 + 66 + 12 + 1 = 794.

3) У 6 мальчиков и 11 девочек в детском саду выявлены признаки инфекционного заболевания. Чтобы подтвердить диагноз, требуется провести выборочный анализ крови у 2 мальчиков и 2 девочек. Сколькими способами можно это сделать?

Существует = 15 способов выбора 2 мальчиков и = 55 способов выбора 2 девочек. Согласно правилу произведения существует 15×15 = = 825 способов выбора 2 мальчиков и 2 девочек.

Пример 2.10 (сочетание с повторениями – неупорядоченные выборки, содержащие одинаковые элементы , причем r может быть и больше n ).

1) В продажу поступили открытки 10 разных видов. Число способов организовать набор:

·  из 8 открыток = 12 310;

·  из 12 открыток = 293 930.

2) Число способов выбрать 6 пирожных в кондитерской, где есть 4 разных сорта пирожных – = 84.

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

Пример 2.11 [12]. Необходимо составить варианты контрольной работы, каждый из которых должен содержать три задачи. Первая задача выбирается из любого параграфа I главы сборника задач, вторая – из любого параграфа II главы, а последняя из любого параграфа III главы. При этом следует учесть, что I и III главы содержат два параграфа, а II глава – три параграфа. Сколько видов контрольной работы можно составить исходя из этих условий, если вид работы определяется только номерами параграфов, из которых выбраны задачи?

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

Для подсчета количества видов контрольной работы воспользуемся граф-деревом. Начальную точку (корень) обозначим буквой О. Двигаясь всеми возможными путями по ребрам графа слева направо начиная с точки О, получим 12 вариантов контрольной работы (рис. 2.3).

Рис. 2.3

2.8. 1) Имеется 10 белых и 6 красных роз. Сколькими способами из них можно выбрать для букета 3 белые и 2 красные розы?

2) Из 12 разных книг 4 имеют переплет. Сколькими способами можно выбрать 5 книг так, чтобы среди них 2 было в переплете?

3) Из 10 теннисисток и 6 теннисистов нужно составить 4 смешанные пары. Сколькими способами это можно сделать?

2.9. 1) Сколько существует возможных результатов опыта с 5 подбрасываниями монеты?

2) Сколько существует возможных результатов опыта с 2 подбрасываниями игральной кости?

1)  Набирая номер телефона, абонент забыл 2 последние цифры и решил набрать наугад. Сколько существует способов набора этих цифр?

2.10. 1) Автомобильные номера состоят из 3 букв (всего используется 30 букв) и 4 цифр (используется всего 10). Сколько можно составить разных номеров?

2) Сколькими способами шофер может доставить 5 коробок товара в 4 магазина?

Вероятности случайного события

1. Статистический подход к вычислению вероятности события. 2. Классическое определение вероятности.

Понятие вероятности (меры возможности наступления случайного события) можно ввести разными способами, что отражает особенности пространства элементарных событий W, которое может быть конечным, счетным или несчетным множеством, а также характер самих элементарных событий.

Рассмотрим три подхода к понятию вероятности случайного события: статистический (частотный), классический и геометрический.

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

(3.1)

называется относительной частотой наступления события А в данной серии.

Отметим важные свойства величины :

1.  Если событие А достоверно, т. е. nA= n, то = 1.

2.  Если событие А невозможное, т. е. nA= 0, то = 0.

3.  0 £ £ 1.

Пример 3.1. Какова относительная частота:

а) рождения мальчиков, если среди 1000 новорожденных оказалось 550 мальчиков;

б) всхода семян, если для выявления качества семян было высеяно 100 штук, из которых 93 взошли;

в) простых чисел на отрезке от 1 до 20?

Ответ: а) 550/1000; б) 93/100; в) 9/20.

Пример 3.2. При стрельбе по мишени относительная частота попадания = 0,75. Найти число попаданий при 40 выстрелах.

Þ nA = n , nA = 40 × 0,75 = 30.

При многократных бросаниях монеты подсчитывалось число появления герба и находилась относительная частота этого события. Результаты эксперимента приводятся в табл. 3.1

Таблица 3.1 

Серия	n	nA
1	4040	2048	0,5069
2	12 000	6019	0,5016
3	24 000	12 012	0,5005

Приведенные данные свидетельствуют о том, что относительные частоты появления герба при достаточно больших n мало отличаются.

Рис. 3.1

Отметим, что число может меняться от одной серии экспериментов к другой. Однако, как показывает опыт, при достаточно большом числе экспериментов n (n ® ¥) величина стабилизируется и приближается к некоторому числу Р(А), поэтому говорят, что событие А стохастически устойчиво, а число Р(А) называют статистической вероятностью события А:

. (3.2)

Свойство устойчивости частот – одна из фундаментальных закономерностей теории вероятностей. На рис. 3.1 показаны результаты трех экспериментов с монетой (по 1000 бросаний в каждой серии).

Покажем на примере, как можно использовать свойство устойчивости частот.

Пример 3.3. Как приближенно установить число рыб в озере?

Пусть в озере х рыб. Забрасываем сеть и, допустим, находим в ней n рыб. Каждую из них метим и выпускаем обратно в царство Нептуна. Через несколько дней в такую же погоду и в том же месте забрасываем ту же самую сеть. Допустим, находим в ней m рыб, среди которых k меченых. Пусть событие А – «пойманная рыба мечена». Тогда по формуле (3.1) . Но если в озере х рыб и мы выпустили в него n меченых, то согласно (3.3) . Так как .

Классическая вероятность (модель Лапласа). Рассмотрим эксперимент, пространство событий которого конечно W = {w1 , w2 ,…wn} и образует полную группу попарно несовместных, равновозможных событий (под равновозможными понимают события, имеющие одинаковые условия для появления, поэтому нет основания утверждать, что у какого либо из них появиться в результате опыта больше шансов, чем у другого). Классической вероятностью случайного события А называется число

, (3.3)

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

Из определения вероятности следуют ее простейшие свойства:

1.  Вероятность достоверного события равна единице: Р(W) = 1;

2.  Вероятность невозможного события равна нулю: Р(Æ) = 0;

3.  Вероятность случайного события 0 < P(A) < 1.

Замечание. При статистическом подходе мы определяем вероятность по результатам опыта, это апостериорная (послеопытная ) вероятность, тогда классическая вероятность – априорная, поскольку определяется теоретически (по формуле).

Для вычисления классической вероятности можно использовать алгоритм 1.

Алгоритм 1

Вычисление классической вероятности

Шаг 1. Ввести обозначения:

·  события, вероятностью наступления, которого мы интересуемся
А (В, С, …);

·  заданных величин.

Шаг 2. Выяснить, что представляет собой элементарный исход эксперимента.

Шаг 3. Убедиться в том, что

·  число элементарных исходов конечно;

·  все исходы равновозможны и попарно несовместны.

Шаг 4. Вычислить:

n – число всех элементарных исходов эксперимента;

m – число элементарных исходов, благоприятствующих появлению события А (В, С, …).

Шаг 5. Вычислить искомую вероятность по формуле .

Замечание. При подсчете чисел n и m используются формулы комбинаторика или графы.

Пример 3.4. При составлении команды космического корабля возникает вопрос о психологической совместимости отдельных членов экипажа. Допустим, надо составить команду, состоящую из командира, инженера и врача. На место командира есть три кандидата к1, к2, к3; на место инженера – четыре и1, и2, и3, и4, на место врача – два кандидата – в1, в2. Проведенная проверка показала психологическую несовместимость командира к2 с инженерами и3, и4, и с врачом в2, а инженера и2 с врачом в2. Какова вероятность события «составлен экипаж, все члены психологически совместимы друг с другом? »

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

Представим в виде дерева (рис. 3.2) все варианты состава.

Рис. 3.2

Число всех ветвей этого графа, т. е. число всех исходов, равно n =24. Выделенные ветви графа (члены экипажа совместимы друг с другом) соответствуют числу исходов, благоприятствующих событию А, поэтому m =16, следовательно, Р(А) = 16/24 = 2/3.

Ответ: Р(А) = 2/3.

Пример 3.5. В партии готовой продукции среди 20 ламп 5 – повышенного качества. Наудачу отбирается 7 ламп. Какова вероятность того, что среди них окажется 3 лампы повышенного качества (рис. 3.3).

Выбрать 7 ламп из 20 можно n = способами. Для подсчета благоприятных исходов воспользуемся рассмотренной в занятии 2 схемой, описанной в ситуации 2. Мы выбираем семь ламп, из них три лампы должны быть повышенного качества, их можно выбрать способами, а остальные четыре лампы выбираются из 15 (т. к 20 –5 =15). Это можно сделать способами.

По правилу умножения m =.

Тогда по формуле (3.3) имеем

.

Ответ: Р(А) = 0,176.

Пример 3.6. Участник лотереи «Спортлото» из 49 наименований спорта называет шесть. Выигрыш определяется тем, сколько он угадал наименований из шести, которые определяются в момент розыгрыша лотереи. С какой вероятностью участник угадает: 1) три цифры из шести; 2) не менее четырех цифр; 3) шесть из шести?

1)  n = , m = , .

2)  Р(А) = Р(4) + Р(5) + Р(6),

Число; ;

;

Тогда Р(А) = 0,00097 + 0,00002 + 0,00000007 » 0,001.

Пример 3.7. В цехе работают 6 мужчин и 4 женщины. Наудачу отбирают 7 человек. Какова вероятность того, что среди отобранных окажутся 3 женщины?

Ответ: Р(А) = 0,5.

Пример 3.8. Четырехтомное собрание сочинений расположено в случайном порядке. Чему равна вероятность того, что тома стоят в должном порядке слева направо или справа налево?

Всего возможных исходов n = 4!. Благоприятных m =2 (1, 2, 3, 4 или 4, 3, 2, 1).

Тогда по формуле (3.3) имеем .

Ответ: Р(А) = 0,0833.

Пример 3.9. На восьми карточках написаны цифры 2, 4, 6, 7, 8, 11, 12, 13. Берутся две карточки. Определить вероятность того, что образованная из двух полученных чисел дробь сократима.

Число возможных исходов n = . Благоприятных m =
(отбрасываем карточки с цифрами 7, 11, 13, останется 5, из них 2 можно выбрать способами). Тогда по формуле (3.3) имеем .

Ответ: Р(А) = 0,3572.

Пример 3.10. Среди 12 приборов 5 – повышенной точности. Найти вероятность того, что взятые наудачу 2 прибора – повышенной точности.

Ответ: Р(А) = 0,152.

Пример 3.11. В лифт девятиэтажного дома на первом этаже вошли 5 человек. Каждый из них с одинаковой вероятностью выходит на любом из этажей начиная со второго. Найти вероятность того, что:

1) все пассажиры выйдут на одном и том же этаже (событие А);

2) все пассажиры выйдут на шестом этаже (событие В);

3) все пассажиры выйдут на разных этажах (событие L);

4) на одном выйдут 3 пассажира, а на другом – 2 (событие D).

Всего возможных исходов n = 85 .

1)  Благоприятствующим событию А исходам соответствует число способов, которыми можно выбрать один этаж m = = 8, по формуле (3.3) Р(А) =.

2)  Благоприятствующим событию В исходам соответствует
m = 1, Р(В) = = 0,00003.

3)  Исходам, благоприятствующим событию L, соответствует число способов, которыми можно выбрать из восьми этажей пять (все пассажиры выходят на разных этажах) m =, P(L) == 0,205.

4)  Найдем число исходов, благоприятствующих событию D. Число способов, которыми можно выбрать один этаж, где будут выходить 3 пассажира, . Так как осталось семь этажей, то число способов, которыми можно выбрать, где будут выходить 2 пассажира, . Число способов, которыми можно выбрать трех пассажиров из пяти, выходящих на одном этаже, . Следовательно, благоприятствующих исходов m = . Пользуясь формулой (3.3), получаем: .

При изучении малых социальных групп иногда приходится проверять, не описываются ли взаимоотношения в группе случайной сетью. Случайной сетью называют следующую структуру: имеется N узлов, от каждого из которых отходят r связей, наугад прикрепляющихся к другим узлам, причем узел не может быть связан сам с собой и не имеет ни с каким другим узлом более одной связи.

Пример 3.12. В эксперименте каждому из 10 школьников, обучающихся в одном классе, предложили назвать имена 3 одноклассников, с которыми испытуемый больше всего хотел бы дружить. В результате один из мальчиков был назван в 9 анкетах. Разумно ли в такой ситуации считать, что отношения предпочтения в изучаемой группе образуют случайную сеть?

Событие А = {мальчик в 9 анкетах назван случайно}, тогда по формуле (3.3) , где n – число всевозможных способов составления анкет десятью школьниками. В любой из анкет можно назвать 3 человек, выбранных из 9. Число вариантов составления одной из анкет равно (число способов назвать одному школьнику 3 человек из 9), а десять школьников составят ()10 анкет. Посчитаем число возможных вариантов, благоприятствующих событию А. В одной анкете можно назвать данного мальчика способами (себя нельзя назвать, данный мальчик выбран, остается выбрать еще 2 из 8); в 9 анкетах число таких вариантов составляет ()9. Для десятой анкеты, составленной выбранным мальчиком, есть способов заполнения анкеты. Тогда вероятность события А:

.

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