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

Часть I. Случайные событияГлава 1. Элементы комбинаторного анализа.Одной из основных задач комбинаторики является подсчет числа элементовконечных множеств, заданных каким-либо дескриптивным условием. Рассмотримтиповые ситуации.§ 1. Основные правила комбинаторикиПусть имеется k групп А1,А2,...,Аk , причем i-ая группа содержит ni элементов.Тогда:А. Правило умножения (основная теорема комбинаторики).

Общее число Nспособов, которыми можно получить упорядоченную совокупность (a1,a2,...ak), гдеaiAi (т.е. выбрать по одному элементу из каждой группы и расставить их вопределенном порядке), равноN  n1 n2 ...n k .Б. Правило сложения. Если один элемент из группы Ai можно выбрать ni способами,и при этом любые две группы Ai и Aj не имеют обших элементов, то выбор одногоэлемента или из A1, или из A2, ..., или из Ak можно осуществитьN  n1  n2  ...  nk способами.Задача 1.

В группе 30 студентов. Необходимо выбрать старосту, заместителя старостыи профорга. Сколько существует способов это сделать?Решение. Старостой может быть выбран любой из 30 студентов, заместителем - любойиз оставшихся 29, а профоргом - любой из оставшихся 28 студентов, т.е. n1=30, n2=29,n3=28. По правилу умножения общее число N способов выбора старосты, егозаместителя и профорга равноN=n1n2n3=302928=24360.Задача 2. Два почтальона должны разнести 10 писем по 10 адресам. Сколькимиспособами они могут распределить работу?Решение.

Первое письмо имеет n1=2 альтернативы – либо его относит к адресатупервый почтальон, либо второй. Для второго письма также есть n2=2 альтернативы ит.д., т.е. n1=n2=…=n10=2. Следовательно, в силу правила умножения общее числоспособов распределений писем между двумя почтальонами равноN  n1 n2 ...n10  22  ... 2  210  1024 .10ðàçЗадача 3. В ящике 100 деталей, из них 30 – деталей 1-го сорта, 50 – 2-го, остальные –3-го. Сколько существует способов извлечения из ящика одной детали 1-го или 2-госорта?Решение. Деталь 1-го сорта может быть извлечена n1=30 способами, 2-го сорта – n2=50способами.

По правилу суммы существует N=n1+n2=30+50=80 способов извлеченияодной детали 1-го или 2-го сорта.1§ 2. Упорядоченные совокупности (последовательный выбор)Пусть имеется некоторая конечная совокупность элементов {a1,a2,...,an},называемая генеральной совокупностью и n – объем этой совокупности. Пустьэксперимент состоит в том, что из генеральной совокупности последовательновыбирают k элементов и располагают их в порядке выбора. Возможны две ситуации.А. Размещения без повторений. Отобранный элемент перед отборомследующего не возвращается в генеральную совокупность. Такой выбор называетсяразмещением k элементов из n, или последовательным выбором без возвращения. Итак,размещения – это упорядоченные совокупности k элементов из n,отличающиеся друг от друга либо составом, либо порядком элементов.Например.

Пусть имеется множество a, b, c из трех элементов. Тогда все размещениядвух элементов из трех таковы: ab, ba, ac, ca, bc, cb.Требуется найти число различных способов, которыми можно произвестипоследовательную выборку без возвращения k элементов из генеральной совокупностиобъема n.

Очевидно, что первый элемент можно выбрать n1=n способами, и так какотобранный элемент не возвращается в генеральную совокупность, то следующийэлемент выбирается из совокупности, объем которой на один элемент меньше, то естьn2=n-1, и т.д. так, что nk=n-(k-1). Тогда по правилу умножения общие число Nспособов равно N=n(n-1)...(n-(k-1)). Такое число обозначаетсяAnk , т.е.Ank  n(n  1)(n  2)...(n  k  1) , илиn!.( n  k )!В частном случае, когда выбираются все элементы генеральной совокупности, т.е.когда k=n, размещения называются перестановками.Ank Перестановки – это упорядоченные совокупности, отличающиеся друг отдруга только порядком элементов.Число всех перестановок множества из n элементов обозначается Pn и вычисляется поформулеPn  n! .Например.

Все перестановки множества a, b, c из трех элементов устроены так:abc, bac, cba, acb, cab, bca и P3  3! 6.Б. Размещения с повторениями. Если каждый отобранный элемент передотбором следующего возвращается в генеральную совокупность, то такой выборназывается размещением с повторениями (или последовательный выбор свозвращением).

Так как на каждом шаге выборка производится из генеральнойkсовокупности объема n, то общее число Àn различных способов, какими можнопроизвести выборку с возвращением k элементов из генеральной совокупности объемаkn равно À n  n k .Пример. Все размещения с повторениями двух элементов из множества с тремяэлементами a, b, c:aa, ab, ac, ba, bb, bc, ca, cb, cc.2Задача 4. Расписание одного дня состоит из 5 уроков. Определить число вариантоврасписания при выборе из 11 дисциплин.Решение.

Каждый вариант расписания представляет набор 5 дисциплин из 11,отличающихся от других вариантов как составом, так и их порядком следования,11!11! 7  8  9  10  11  55440.поэтому N  A115 (11  5)! 6!Задача 5. В конкурсе по 5 номинациям участвуют 10 кинофильмов. Сколькосуществует вариантов распределения призов, если по каждой номинации установленыразличные премии?Решение.

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

Поэтому числотаких комбинаций равно числу размещений с повторениями из 10 элементов по5:N  А105  105  100000.§ 3. Неупорядоченные совокупности (одновременный выбор)А. Сочетания без повторений. Если комбинации из n элементов по k отличаютсятолько составом элементов, то их рассматривают как одновременныйнеупорядоченный выбор k элементов из генеральной совокупности объема n иназывают сочетаниями из n элементов по k. То есть,сочетания – это неупорядоченные совокупности элементов, отличающиесядруг от друга только составом элементов.Например. Все сочетания без повторений двух элементов из множества a, b, c:a, b, a, c, b, c.Формула для вычисления числа сочетаний n элементов по k:n!С nk .( n  k )! k!Свойства числа сочетаний:Cnk  Cnn  k ;Cnk  Cnk 1  Cnk11;Cn0  Cnn  1;Cn0  Cn1  Cn2  ...  Cnn  2n.Б.

Сочетания с повторениями. Если в сочетаниях из n элементов по k некоторые изэлементов или все могут оказаться одинаковыми, то такие сочетания называютсясочетаниями с повторениями из n элементов по k, и число сочетаний с повторениямииз n элементов по k равноkС n  C nkk 1.Пример. Все сочетания с повторениями двух элементов из множества a, b, c:a, a, a, b, a, c, b, b, b, c, c, c.Задача 6. В шахматном турнире участвуют 16 человек.

Сколько партий должно бытьсыграно в турнире, если между любыми участниками должна быть сыграна однапартия?3Решение. Каждая партия играется двумя участниками из 16 и отличается от другихтолько составом пар участников, т.е. представляет собой сочетания из 16 элементов по16! 15  162. Их число равно C162  120.14!2!1 2Задача 7. В условиях задачи 5 определить, сколько существует вариантовраспределения призов, если по каждой номинации установлены одинаковые призы?Решение. Если по каждой номинации установлены одинаковые призы, то порядокфильмов в комбинации 5 призов значения не имеет, и число вариантов представляетсобой число сочетаний с повторениями из 10 элементов по 5, определяемое по510  11  12  13  14формуле C 10  C105 51  C145  2002.1 2  3 4  5Задача 8. Порядок выступления 7 участников конкурса определяется жребием.Сколько различных вариантов жеребьевки при этом возможно?Решение.

Каждый вариант жеребьевки отличается только порядком участниковконкурса, т.е. является перестановкой из 7 элементов. Их число равноP7  7!  1  2  3  4  5  6  7  5040.§ 4. Разбиение множества на группыЕсли множество из n различных элементов разбивается на k групп так, что в первуюгруппу попадают n1 элементов, во вторую – n2 элементов, в k-ую группу – nkэлементов, причем n1+n2+...+nk=n, то число таких разбиений равноn!N n (n1 , n2 ,...nk ) .n1!n2!...nk !Задача 9. Сколькими способами можно разбить группу из 25 студентов на триподгруппы по 6, 9 и 10 человек в каждой группе?Решение.

Здесь n=25, k=3, n1=6, n2=9, n3=10. Согласно формуле, число таких разбиение25!равно N 25 (6,9,10) .6!9!10!Задача 10. Сколько существует семизначных чисел, состоящих из цифр 4,5 и 6, вкоторых цифра 4 повторяется 3 раза, а цифры 5 и 6 - по 2 раза?Решение. Каждое семизначное число отличается от другого порядком следованияцифр, при этом фактически все семь мест в этом числе делятся на три группы: на одниместа ставится цифра «4», на другие места – цифра «5», а на третьи места – цифра «6».Таким образом, в нашем случае множество состоит из 7 элементов (n=7), причем n1=3,n2=2, n3=2), и, следовательно, в силу формулы число таких чисел равно7!N 7 (3;2;2)  210.3!2!2!Задачи для самостоятельного решения1.2.3.4.В ящике 5 красных и 4 зеленых яблока.