1625915146-70d402fe54d0af3e87017c6c516bbe93 (843877), страница 2
Текст из файла (страница 2)
С помощью теоремы 1 доказать, что:а) при подбрасывании трёх монет возможно 2 · 2 · 2 = 8 результатов;б) бросая дважды игральную кость, получим 6 · 6 = 36 результатов;в) трёхзначных чисел бывает 9 · 10 · 10 = 900 ;г) трёхзначных чисел, все цифры которых различны, существует 9·9·8.Урновые схемы. Есть урна (ящик), содержащая n пронумерованныхшаров. Мы выбираем из урны k шаров; результат этого выбора — набор изk шаров.
Нас интересует, сколькими способами можно выбрать k шаровиз n, т. е. сколько различных результатов возможно.На этот вопрос нельзя дать однозначный ответ, пока мы не знаем:а) как организован выбор;б) что понимать под различными результатами выбора.Рассмотрим следующие возможные способы выбора.1. Выбор с возвращением : каждый вынутый шар возвращается в урну, каждый следующий шар выбирается из полной урны. В полученномнаборе из k номеров шаров могут встречаться одни и те же номера.2. Выбор без возвращения : вынутые шары в урну не возвращаются,и в полученном наборе не могут встречаться одни и те же номера.Условимся, какие результаты выбора (какие наборы номеров шаров)мы будем считать различными .
Есть ровно две возможности.1. Выбор с учётом порядка : два набора номеров шаров считаются различными, если они отличаются составом или порядком номеров. Так, наборы (1, 5, 2), (2, 5, 1) и (4, 4, 5) считаются различными наборами.2. Выбор без учёта порядка : два набора номеров шаров считаются различными, если они отличаются составом. Так, наборы (1, 5, 2) и (2, 5, 3)различны, а наборы (1, 5, 2) и (2, 5, 1) не различаются.Подсчитаем, сколько возможно различных результатов для каждой изчетырёх схем выбора: с возвращением или без возвращения, и в каждомиз этих случаев — с учётом порядка или без учёта.Т е о р е м а 2.
Общее количество различных наборов при выборе k элементов из n без возвращения и с учётом порядка равняетсяkA n = n(n − 1) · . . . · (n − k + 1) =kn!.(n − k)!Число A n называется числом размещений из n элементов по k элементов, а сами результаты выбора — размещениями.§ 1. Элементы комбинаторики11Д о к а з а т е л ь с т в о. Первый шар можно выбрать n способами. Прилюбом выборе первого шара есть n − 1 способ выбрать второй шар, прилюбом выборе первых двух шаров есть n − 2 способа выбрать третий шари т. д. Применяя последовательно теорему 1, получаем, что общее числовозможных наборов из k шаров равно произведению k сомножителейn(n − 1) · .
. . · (n − k + 1). Здесь последний сомножитель n − k + 1 естьчисло способов выбрать k -й шар из оставшихся в урне шаров.С л е д с т в и е 1. В множестве из n элементов возможно ровно n!перестановок этих элементов.Д о к а з а т е л ь с т в о. Перестановка — результат выбора без возвращеnния и с учётом порядка n элементов из n. Их число равно A n = n!У п р а ж н е н и е . Найти количество различных результатов в следующих экспериментах:а) из колоды в 36 карт выдают по карте троим игрокам;б) Вася, Петя, Оля и Лена выбирают четыре из восьми разных книг;в) из алфавита выбирают три разные буквы и составляют слово;г) из различных ненулевых цифр составляют трёхзначное число;д) 36 карт в колоде перемешивают и выкладывают на стол в ряд.Т е о р е м а 3.
Общее количество различных наборов при выборе k элементов из n без возвращения и без учёта порядка равняетсяkCn =Aknn!=.k!k! (n − k)!kЧисло Cn называется числом сочетаний из n элементов по k элементов, а сами результаты выбора — сочетаниями.Д о к а з а т е л ь с т в о. Упорядочить k различных номеров шаров можно k! способами. Поэтому из каждого сочетания можно перестановкамиобразовать k! размещений . Следовательно, число наборов, порядок в которых не учитывается (сочетаний), в k! раз меньше числа наборов, отличающихся ещё и порядком (размещений).У п р а ж н е н и е . Найти количество различных результатов в следующих экспериментах:а) из колоды в 36 карт выдают три карты одному игроку;б) из двадцати учеников класса выбирают троих дежурных.Т е о р е м а 4.
Общее количество различных наборов при выборе k элементов из n с возвращением и с учётом порядка равняется nk .12ГЛАВА I. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ВЕРОЯТНОСТЕЙД о к а з а т е л ь с т в о. Первый шар можно выбрать n способами. Прикаждом из этих способов второй шар можно выбрать также n способами,и так k раз.
Общее число наборов равно n · n · . . . · n = nk .У п р а ж н е н и е . Найти количество различных результатов в следующих экспериментах:а) монету подбрасывают пять раз;б) пятизначное число составляют из одних нечётных цифр.в) обезьяна напечатала на машинке слово из десяти букв;г) составляют слово длиной в 10 символов из нулей и единиц;д) игральную кость подбрасывают четырежды.Выбор с возвращением и без учёта порядка.
Рассмотрим урну с двумя пронумерованными шарами и перечислим результаты выборадвух шариков из этой урны при выборе с возвращением. Если учитыватьпорядок, то исходов получится четыре:(1, 1), (2, 2), (1, 2), (2, 1).Если порядок не учитывать, то следует объявить два последних исходаодним и тем же результатом эксперимента. Исходов окажется три:дважды вынут 1-й шар, дважды вынут 2-й шар, вынуты разные шары.Видим, что в схеме выбора без учёта порядка получилось три различныхрезультата, тогда как при выборе с учётом порядка различных результатов было четыре. Никаким делением на «число каких-нибудь перестановок», которое помогло избавиться от учёта порядка при выборе без возвращения, число 3 из числа 4 получить не удастся.Т е о р е м а 5. Общее количество различных наборов при выборе k элементов из n с возвращением и без учёта порядка равняетсяkn−1Cn+k−1 = Cn+k−1 .У п р а ж н е н и е . Проверить, что при n = 2 и k = 2 получается ровнотри исхода.Д о к а з а т е л ь с т в о.
Рассмотрим, чем отличаются друг от друга дваразных результата такой схемы выбора. Нам не важен порядок следованияномеров, т. е. мы учитываем только, сколько раз в нашем наборе из k номеров шаров появился каждый номер. Поэтому результат выбора можнопредставить набором чисел k1 , . . . , kn , в котором ki > 0 — число появлений шара номер i в наборе, k1 + . . . + kn = k. Два результата выбора13§ 2. События и операции над нимис возвращением и без учёта порядка различаются, если соответствующиеим упорядоченные наборы k1 , . . .
, kn не совпадают.Представим себе другой эксперимент, имеющий точно такие же результаты, и посчитаем их количество. Есть n ящиков, в которых размещаютсяk шаров. Нас интересует только число шаров в каждом ящике. Результатом эксперимента снова является набор чисел k1 , . . . , kn , где ki > 0равно числу шаров в ящике с номером i, k1 + . .
. + kn = k.А теперь изобразим результат такого размещения в виде схемы, в которой вертикальные линии обозначают перегородки между ящиками, а точки — находящиеся в ящиках шары:|• • • ||• |• • |• • ||• |Мы видим результат размещения девяти шаров по семи ящикам. Первыйящик содержит три шара, второй и шестой ящики пусты, третий ящиксодержит один шар, в четвёртом и пятом ящиках лежит по два шара.Переложим один шар из первого ящика во второй и изобразим таким жеобразом ещё два результата размещения:|• • |• |• ||||||||• • |• • ||• |• • • • • • • • • |Видим, что все размещения можно получить, меняя между собой шарыи перегородки или расставляя k шаров на n−1+k местах.
Число n−1+kполучается так: у n ящиков есть ровно n+1 перегородка, считая крайние,но из них перемещать можно лишь n −1 внутреннюю перегородку. Такимобразом, имеется n−1+k мест, которые можно занять шарами либо внутренними перегородками. Перебрав все возможные способы расставить kшаров на этих n−1+k местах, переберём и все нужные размещения. Остаkn−1лось заметить, что по теореме 3 существует Cn−1+k = Cn+k−1 способоввыбрать места для k шаров на n − 1 + k местах.У п р а ж н е н и е . Найти:а) количество способов разложить число k ∈ N в сумму n целых неотрицательных слагаемых, если важен порядок следования слагаемых;б) число различных производных порядка k функции n переменных;в) число возможных результатов подбрасывания двух игральных костей, если кости считаются неразличимыми.
То же самое для трёх игральных костей.§ 2. События и операции над ними14ГЛАВА I. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ВЕРОЯТНОСТЕЙПространство элементарных исходов. Основным понятием теории вероятностей является множество всех возможных результатов данного случайного эксперимента.О п р е д е л е н и е 1. Пространством элементарных исходов называется множество Ω, содержащее все возможные взимоисключающие результаты данного случайного эксперимента. Элементы множества Ω называются элементарными исходами и обозначаются буквой ω.Отметим сразу, что любое непустое множество Ω можно считать пространством элементарных исходов какого-то случайного эксперимента.О п р е д е л е н и е 2. Событиями называются подмножества множества Ω.
Говорят, что произошло событие A, если эксперимент завершился одним из элементарных исходов, входящих в множество A.З а м е ч а н и е . Вообще говоря, можно называть событиями не любыеподмножества множества Ω, а лишь элементы некоторого набора подмножеств. О смысле такого ограничения мы поговорим позднее.Итак, элементарный исход — это мельчайший неделимый результат эксперимента, а событие может состоять из одного или нескольких исходов.Напомним, что конечные и счётные множества удобно задавать перечислением их элементов.