chapter1 (Л.Н. Фадеева - Задачи по теории вероятностей с решениями (DOC))

Часть I. Случайные события.

Глава 1. Элементы комбинаторного анализа.

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

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

Пусть имеется k групп А₁,А₂,...,А_k , причем i-ая группа содержит n_i элементов. Тогда:

А. Правило умножения (основная теорема комбинаторики). Общее число N способов, которыми можно получить упорядоченную совокупность (a₁,a₂,...a_k), где a_iA_i (т.е. выбрать по одному элементу из каждой группы и расставить их в определенном порядке), равно

.

Б. Правило сложения. Если один элемент из группы A_i можно выбрать n_i способами, и при этом любые две группы A_i и A_j не имеют обших элементов, то выбор одного элемента или из A₁, или из A₂, ..., или из A_k можно осуществить

способами.

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

Решение. Старостой может быть выбран любой из 30 студентов, заместителем - любой из оставшихся 29, а профоргом - любой из оставшихся 28 студентов, т.е. n₁=30, n₂=29, n₃=28. По правилу умножения общее число N способов выбора старосты, его заместителя и профорга равно

N=n₁n₂n₃=302928=24360.

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

Решение. Первое письмо имеет n₁=2 альтернативы – либо его относит к адресату первый почтальон, либо второй. Для второго письма также есть n₂=2 альтернативы и т.д., т.е. n₁=n₂=…=n₁₀=2. Следовательно, в силу правила умножения общее число способов распределений писем между двумя почтальонами равно

.

Задача 3. В ящике 100 деталей, из них 30 – деталей 1-го сорта, 50 – 2-го, остальные – 3-го. Сколько существует способов извлечения из ящика одной детали 1-го или 2-го сорта?

Решение. Деталь 1-го сорта может быть извлечена n₁=30 способами, 2-го сорта – n₂=50 способами. По правилу суммы существует N=n₁+n₂=30+50=80 способов извлечения одной детали 1-го или 2-го сорта.

§ 2. Упорядоченные совокупности (последовательный выбор)

Пусть имеется некоторая конечная совокупность элементов {a₁,a₂,...,a_n}, называемая генеральной совокупностью и n – объем этой совокупности. Пусть эксперимент состоит в том, что из генеральной совокупности последовательно выбирают k элементов и располагают их в порядке выбора. Возможны две ситуации.

А. Размещения без повторений. Отобранный элемент перед отбором следующего не возвращается в генеральную совокупность. Такой выбор называется размещением k элементов из n, или последовательным выбором без возвращения. Итак,

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

Например. Пусть имеется множество из трех элементов. Тогда все размещения двух элементов из трех таковы:

Требуется найти число различных способов, которыми можно произвести последовательную выборку без возвращения k элементов из генеральной совокупности объема n. Очевидно, что первый элемент можно выбрать n₁=n способами, и так как отобранный элемент не возвращается в генеральную совокупность, то следующий элемент выбирается из совокупности, объем которой на один элемент меньше, то есть n₂=n-1, и т.д. так, что n_k=n-(k-1). Тогда по правилу умножения общие число N способов равно N=n(n-1)...(n-(k-1)). Такое число обозначается , т.е. , или

.

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

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

Число всех перестановок множества из n элементов обозначается и вычисляется по формуле

.

Например. Все перестановки множества из трех элементов устроены так: и

Б. Размещения с повторениями. Если каждый отобранный элемент перед отбором следующего возвращается в генеральную совокупность, то такой выбор называется размещением с повторениями (или последовательный выбор с возвращением). Так как на каждом шаге выборка производится из генеральной совокупности объема n, то общее число различных способов, какими можно произвести выборку с возвращением k элементов из генеральной совокупности объема n равно .

Пример. Все размещения с повторениями двух элементов из множества с тремя элементами :

Задача 4. Расписание одного дня состоит из 5 уроков. Определить число вариантов расписания при выборе из 11 дисциплин.

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

Задача 5. В конкурсе по 5 номинациям участвуют 10 кинофильмов. Сколько существует вариантов распределения призов, если по каждой номинации установлены различные премии?

Решение. Каждый из вариантов распределения призов представляет собой комбинацию 5 фильмов из 10, отличающуюся от других комбинаций как составом, так и их порядком. Так как каждый фильм может получить призы как по одной, так и по нескольким номинациям, то одни и те же фильмы могут повторяться. Поэтому число таких комбинаций равно числу размещений с повторениями из 10 элементов по5:

§ 3. Неупорядоченные совокупности (одновременный выбор)

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

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

Например. Все сочетания без повторений двух элементов из множества :

Формула для вычисления числа сочетаний n элементов по k:

Свойства числа сочетаний:

Б. Сочетания с повторениями. Если в сочетаниях из n элементов по k некоторые из элементов или все могут оказаться одинаковыми, то такие сочетания называются сочетаниями с повторениями из n элементов по k, и число сочетаний с повторениями из n элементов по k равно

Пример. Все сочетания с повторениями двух элементов из множества :

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

Решение. Каждая партия играется двумя участниками из 16 и отличается от других только составом пар участников, т.е. представляет собой сочетания из 16 элементов по 2. Их число равно

Задача 7. В условиях задачи 5 определить, сколько существует вариантов распределения призов, если по каждой номинации установлены одинаковые призы?

Решение. Если по каждой номинации установлены одинаковые призы, то порядок фильмов в комбинации 5 призов значения не имеет, и число вариантов представляет собой число сочетаний с повторениями из 10 элементов по 5, определяемое по формуле

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

Решение. Каждый вариант жеребьевки отличается только порядком участников конкурса, т.е. является перестановкой из 7 элементов. Их число равно

§ 4. Разбиение множества на группы

Если множество из n различных элементов разбивается на k групп так, что в первую группу попадают n₁ элементов, во вторую – n₂ элементов, в k-ую группу – n_k элементов, причем n₁+n₂+...+n_k=n, то число таких разбиений равно

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

Решение. Здесь n=25, k=3, n₁=6, n₂=9, n₃=10. Согласно формуле, число таких разбиение равно

Задача 10. Сколько существует семизначных чисел, состоящих из цифр 4,5 и 6, в которых цифра 4 повторяется 3 раза, а цифры 5 и 6 - по 2 раза?

Решение. Каждое семизначное число отличается от другого порядком следования цифр, при этом фактически все семь мест в этом числе делятся на три группы: на одни места ставится цифра «4», на другие места – цифра «5», а на третьи места – цифра «6». Таким образом, в нашем случае множество состоит из 7 элементов (n=7), причем n₁=3, n₂=2, n₃=2), и, следовательно, в силу формулы число таких чисел равно

Задачи для самостоятельного решения

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

2. Монету подбросили 3 раза. Сколько различных результатов бросаний можно ожидать?

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

4. Десять человек при встрече обмениваются рукопожатиями. Сколько всего рукопожатий будет сделано?

5. Доступ к файлу открывается только если введен правильный пароль – определенный трехзначный номер из пяти цифр. Каково максимальное число возможных попыток угадать пароль?

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

7. Сколькими способами можно расположить на полке 10 томов энциклопедии?

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

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

10. Группу из 10 человек требуется разбить на две подгруппы так, чтобы в первой группе было 6 человек, а во второй – 4 человека. Сколькими способами это можно сделать?

11. Группу из 16 человек требуется разбить на 3 подгруппы, в первой из которых должно быть 5 человек, во второй — 7 человек, в третьей — 4 человека. Сколькими способами это можно сделать?

12. Сколько существует двухзначных чисел, кратных либо 2, либо 5, либо тому и другому числу одновременно?

13. Из бригады в 14 врачей человек ежедневно в течении 7 дней назначают двух дежурных врачей. Определить количество различных расписаний дежурства, если каждый человек дежурит один раз?

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

15. Шесть групп занимаются в 6 расположенных подряд аудиториях. Сколько существует вариантов расписания, при которых группы 1 и 2 находились бы в соседних аудиториях?

16. Восемь мешков постельного белья доставляются на пять этажей гостиницы. Сколькими способами можно распределить мешки по этажам? В скольких вариантах на пятый этаж доставлен один мешок?

17. Два наборщика должны набрать 16 текстов. Сколькими способами они могут распределить эту работу между собой?

18. Поезд метро делает 16 остановок, на которых выходят пассажиры. Сколькими способами могут распределиться между этими остановками 100 пассажиров, вошедших в поезд на конечной остановке?

19. Акционерное собрание компании выбирает из 50 человек президента компании, председателя совета директоров и 10 членов совета директоров. Сколькими способами можно это сделать?

20. Из фирмы, в которой работают 10 человек, 5 сотрудников должны уехать в командировку. Сколько может быть составов этой группы, если директор фирмы, его заместитель и главный бухгалтер одновременно уезжать не должны?

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

22. Из группы в 25 человек должны быть выделены староста и 3 члена студкома. Сколькими способами это можно сделать?

23. Шесть студентов-переводников следует распределить по трем группам второго курса. Сколькими способами это можно сделать?

24. Лифт останавливается на 7 этажах. Сколькими способами могут распределиться между этими этажами 6 пассажиров, находящихся в кабине лифта?

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

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

27. Сколько существует пятизначных телефонных номеров, в которых есть цифры 1 и 2?

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

29. Байт – это слово, состоящее из восьми бит, каждый бит равен либо 0, либо 1. Сколько символов можно закодировать с помощью байтов?

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

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

32. Из ящика, в котором лежат 10 красных и 5 зеленых яблока, выбирают одно красное и два зеленых яблока. Сколькими способами это можно сделать?

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

34. Студенческую группу в 24 человек (12 девушек и 12 юношей), разбивают на две равные подгруппы так, чтобы в каждой подгруппе юношей и девушек было поровну. Сколькими способами это можно сделать?

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

36. Лифт, в котором находится 9 пассажиров, может останавливаться на 10 этажах. Пассажиры выходят группами по два, по три и четыре человека. Сколькими способами это может произойти?

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

38. Есть 3 билета в различные театры. Сколькими способами они могут быть распределены среди 25 студентов группы, если каждый студент может получить только один билет?

39. На группу из 25 человек выделены 3 пригласительных билета на вечер. Сколькими способами они могут быть распределены (не более одного билета в руки)?

40. Имеются 7 билетов: 3 в один театр и 4 — в другой. Сколькими способами они могут быть распределены между студентами группы из 25 человек?

6