Л.Н. Фадеева, А.В. Лебедев - Теория вероятностей и математическая статистика (1115296), страница 2
Текст из файла (страница 2)
Цель данного учебника — помочь изучающим теорию вероятностей и математическую статистику в усвоении необходимых теоретических знаний и приобретении практических навыков для квалифицированного использования статистической информации в целях принятия правильных решений в вопросах управления и прогнозирования. Авторы ГЛАВА 1 ЭЛЕМЕНТЫ КОМБИНАТОРНОГО АНАЛИЗА о дной из основных задач комбинаторного анализа (комбинаторики) является подсчет числа элементов конечных множеств, заданных каким-либо описательным условием.
Для этого разработаны различные формулы и правила. $ а.з. Основные понятия и теоремы комбинаторики Пусть имеется /с групп А„А„..., А,, причем!-я группа содержит п,. элементов. Тогда справедливы следуюшие правила. ф Теорема умюження (осювная формула комбинаторики). Общее число Ж способов, которыми можно получить упорядоченную совокупность (а„а„... а„), где а,.
е А,, т.е. выбрать по одному элементу из каждой группы и расставить их в определенном порядке, равно Это правило распространяется и на ситуации, когда новые группы образуются в процессе выбора элементов, если численности этих групп не зависят от того, какие именно элементы были выбраны. и йя ЧАСТЫ. Теория вероятнопей )» Теорема сложения. Если один элемент из группы А можно выбрать п, способами и при этом любые две группы А, и А не имеют общих элементов, то выбор одного элемента или из А„ или из А„..., или из А, можно осуществить способами. Как правило, рассматриваются следующие три типовые ситуации, которые являются частными случаями общей схемы выбора элементов из некоторой конечной совокупности (ао а„...а„), называемой генеральной совокупностью.
Будем называть йх схемами последовательного выбора с возвращением, последовательного выбора без возвращения и одновременным выбором. Последовательный выбор с возвращением. Эксперимент состоит в том, что из генеральной совокупности объема и последовательно выбирают /с элементов, и каждый отобранный элемент перед отбором следующего возвращается в генеральную совокупность. Тогда общее число способов, которыми зто можно сделать, обозначается А, и равно А, = и". Последовательный выбор без возвращения.
Эксперимент состоит в том, что из генеральной совокупности последовательно выбирают /с элементов, и каждый отобранный элемент в генеральную совокупность уже не возвращается. Число способов, которыми можно выбрать последовательно й элементов из генеральной совокупности объема и без возвращения, равно п! числу размещений из п по /с: А„' = (и — и)! Одновременный (неупорядоченный) выбор. Эксперимент состоит в том, что выбирают элементы без учета порядка и без возвращения. И все возможные наборы из й элементов отличаются друг от друга хотя бы одним элементом.
Число различных по составу наборов по й элементов из и равно числу сочетаний и! изппоlс: С„= й!(и — й)! В следующих параграфах изучим эти модели подробнее. Задача 1. В группе 30 студентов. Необходимо выбрать старосту, заместителя старосты и профорга. Сколько существует способов это сделать? гг Глава 1 яв Решение. Старостой может быль выбран любой из 30 студентов, заместителем — любой из оставшихся 29, а профоргом— любой из оставшихся 28 студентов, т.е. и, = 30, и, = 29, и, = 28.
По правилу умножения общее число Ф способов выбора старосты, его заместителя и профорга равно Ф = и, х и, х и, = 30 х х 29 х 28 = 24 360. Задача 2. Два почтальона должны разнести 10 писем по 10 адресам. Сколькими способами они могут распределить работу? Решение. Первое письмо имеет и, = 2 альтернативы — либо его относит к адресату первый почтальон, либо второй. Для второго письма также есть и, = 2 альтернативы и т.д., т.е.
п, = п, = ... = = и„= 2. Следовательно, в силу теоремы умножения общее число способов распределений писем между двумя почтальонами л=л, л,=2 2 ... 2-2" 1024. Задача 3. В ящике 100 деталей, из них 30 деталей 1-го сорта, 50 — 2-го, остальные — 3-го. Сколько существует способов извлечения из ящика одной детали 1-го или 2-го сорта? Решение. Деталь 1-го сорта может быть извлечена и, = 30 способами, 2-го сорта — и, = 50 способами. По теореме суммирования сушествует йг = и, + и, = 30 + 50 = 80 способов извлечения одной детали 1-го или 2-го сорта. 5 ал. Упорядоченные совокупности ((последовательный выбор) Пусть имеется некоторая конечная совокупность элементов (ао а,,..., а„ь называемая генеральной совокупностью, н и— объем этой совокупности. Пусть эксперимент состоит в том, что из генеральной совокупности последовательно выбирают Ф элементов и располагают их в порядке выбора.
Возможны две ситуации. Размещения без повторений. Отобранный элемент перед отбором следуюшего не возвращается в генеральную совокупность. Такой выбор называется размещением lс элементов из и (или последовательным выбором без возвращения). гЗ ( ( ф ЧАСТЬ Створня вероятностей Размещения — это упорядоченные совокупности /с элементов из и, отличающиеся друг от друга либо составом, либо порядком элементов. Пример 1. Пусть имеется множество (а, Ь, с» из трех элементов. Тогда все размещения двух элементов из трех таковы: аЬ, Ьа, ас, са, Ьс, сЬ. ~ Теорема 1.
Число различных способов, которыми можно произвести последовательный выбор без возвращения lс элементов из генеральной совокупности обьема п, равно и! А" = (и — тс) ! Доказательство. Очевидно, что первый элемент можно выбрать и, = и способами, и поскольку отобранный элемент не возвращается в генеральную совокупность, то следующий элемент выбирается из совокупности, объем которой на один элемент меньше, т.е. и, = и — 1, и т.д., так что и„= и — (к — 1). Тогда по теореме умножения общее число способов равно тт' = и(и — 1) ...
(и — (к — 1)) = и!/(и — к)! В частном случае, когда выбирают все элементы генеральной совокупности, т.е. когда к = и, размещения называются перестановками. Их число обозначается Р„. Перестановки — это упорядоченные совокупности, отличающиеся друг от друга только порядком элементов. Следствие. Число всех перестановок множества из и элемен- тов равно Р„= и! Пример 2. Все перестановки множества (а, Ь, с» из трех элементов устроены так: аЬс, Ьас„сЬа, асЬ, саЬ, Ьса и Р, = 3! = 6. Размещения с повторениями.
Если каждый отобранный элемент перед отбором следующего возвращается в генеральную совокупность, то такой выбор называется размещением с повторениями (или последовательным выбором с возвращением). ~ тй Глава 1 Е Теорема 2. Общее число различных способов, которыми моакно произвести выбор с возвращением к элементов из генеральной совокупности обьема и, равно А„" = и". Доказательство.
Так как каждый раз отобранный элемент перед отбором следующего возвращается в генеральную совокупность, то выбор на каждом шаге производится из совокупности объема и, и можно считать, что выбор производится из к групп и все группы состоят из одинакового числа элементов п, = и, = ... = и„= и. Тогда, в силу основной теоремы комбинаторики, число таких способов выбора равно ЛГ = и". Пример 3. Все размещения с повторениями двух элементов из множества с тремя элементами (а, Ь, с1: аа, аЬ, ас, Ьа, ЬЬ, Ьс, са, сЬ, сс. Задача 4.
Расписание одного дня состоит из 5 различных уроков. Определить число вариантов расписания при выборе из 11 дисциплин. Решение. Каждый вариант расписания представляет набор 5 дисциплин из 11, отличающихся от других вариантов как составом, так и порядком их следования, поэтому 5 ЬГ=А,', = ' = — '=?х8х9х10х11=55440. (11 — 5)! 6! Задача 5. В конкурсе по 5 номинациям участвуют 10 кинофильмов. Сколько существует вариантов распределения призов, если по каждой номинации установлены различные премии? Решение. Каждый из вариантов распределения призов представляет собой комбинацию 5 фильмов из 10, отличающуюся от других комбинаций как составом, так и их порядком. Поскольку каждый фильм может получить призы как по одной, так и по нескольким номинациям, одни и те же фильмы могут повторяться. Поэтому число таких комбинаций равно числу размещений с повторениями из 1О элементов по 5: ЬГ = А 1в =10' =100 000.
гв ЧАСТЫ. Теория вероятностей $ з.Э. Неупорядоченные совокупности (одновременный выбор) Сочетания без повторений. В результате одновременного неупорядоченного выбора (с элементов из генеральной совокупности объема и получаются комбинации, которые и называют сочетаниями иэ и элементов ио lс. Сочетания — это неупорядоченные совокупности элементов, различающиеся только составом элементов. Пример 4. Все сочетания без повторений двух элементов из множества (а, Ь, с»: (а, Ь», (а, с», (Ь, с». ~ Теорема 3.
Число сочетаний иэ п элементов по 1с равно Се и! (и — 1с)Ус! Доказательство. Среди А„' размещений без повторений имеется по к» наборов каждого состава (представляющих собой всевозможные перестановки из Ь элементов этого состава). Поэтому С„" = А„"/И Свойства числа сочетаний: СО=С =1; С„" =С„" "; С" +С"«' =С'+' « « «+1~ Сс+Сс+Сс+ +С 2«. ~А — Р С" Числа С„" называют также биномиальными коэффициентами, поскольку они участвуют в разложении бинома Ньютона: « (а+Ь) ~~са Ь я-е гб Глава в Сочетания с повторениями.
Если в сочетаниях из и элементов по Й некоторые из элементов или все могут оказаться одинаковыми, то такие сочетания называются сочетаниями с повторениями иэ и элементов по ?Г. ~ Теорема 4. Число сочетаний с повторениями иэ и элементов по /Г равно С. =С„",„,. Пример 5. Все сочетания с повторениями двух элементов из множества (а, Ь, с): (а, а), (а, Ь), (а, с), (Ь, Ь), (Ь, с), (с, с). Задача б.
В шахматном турнире участвуют 16 человек. Сколько партий должно быть сыграно в турнире, если между любыми участниками должна быть сыграна одна партия? Решение. Каждая партия играется двумя участниками из 16 и отличается от других только составом пар участников, т.е. представляет собой сочетания из 16 элементов по 2.
Их число 16! 15х16 равно С,', = — '= — =120. 14!2! 1х2 Задача 7. В условиях задачи 5 определить, сколько сушествует вариантов распределения призов, если по каждой номинации установлены одинаковые призы? Решение. Если по каждой номинации установлены одинаковые призы, то порядок фильмов в комбинации 5 призов значения не имеет, и число вариантов представляет собой число сочетаний с повторениями из 10 элементов по 5, определяемое 1Ох! 1х12х13х14 по формуле С~в =С,'„,, =С~ = = 2002. 1х2хЗх4х5 Задача 8. Порядок выступления 7 участников конкурса определяется жребием. Сколько различных вариантов жеребьевки при этом возможно? Решение.
Каждый вариант жеребьевки отличается только порядком участников конкурса, т.е. является перестановкой из 7 элементов. Их число равно Р, =7!=1х2хЗх4х5хбх7=5040. т7 ~[Ь ЧАСТЫ. Теарня вероятностей 9 з.т). Разбиение множества на группы Пусть множество из и различных элементов разбивается на /с групп так, что в первую группу попадают и, элементов, во вторую — п, элементов, в /с-ю группу — п„элементов, причем и, + и, + ... + и„= и. Такую ситуацию называют разбиением множества на группы.
Заметим, что порядок элементов при разбиении на группы не важен, а вот порядок групп (какую из них мы считаем первой, какую — второй и т.д.) существенен. Теорема 5. Число разбиений равно и! Ь!„(п„п„..., п„) = и,! ттт ! ... п„! Доказаительситво. Пусть в первую группу могут попасть любые и, элементов из имеющихся п элементов первоначально. Это можно сделать С„' способами. Вторую группу надо заполнить и, элементами из оставшихся и — и, элементов. Это можно сделать С„'е „различными способами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
