_учебник_ Теория вероятности. Н.И. Чернова. 2007 (_учебник_ Теория вероятности. Н.И. Чернова. 2007.pdf), страница 2

. . Я употребил обыкновенную хитрость романистов: началповесть эффектными сценами, вырванными из средины иликонца её, прикрыл их туманом. Ты, публика, добра, оченьдобра, а потому ты неразборчива и недогадлива. На тебя нельзя положиться, что ты с первых страниц можешь различить,будет ли содержание повести стоить того, чтобы прочесть её,у тебя плохое чутьё, оно нуждается в пособии, а пособий этихдва: или имя автора, или эффектность манеры.Н. Г. Чернышевский. Что делать?§ 1.

Элементы комбинаторикиНаучимся подсчитывать число «шансов». О числе шансов говорят, когда возможно несколько результатов какого-либо действия (выбор картыиз колоды, подбрасывание кубика или монетки). Формулы комбинаторики позволяют посчитать число способов проделать действие или число еговозможных результатов.Теорема о перемножении шансов. Основной принцип комбинаторики заключается в следующем: если первый элемент можно выбратьk способами, а второй элемент — m способами, то упорядоченную паруэлементов можно составить km способами.Т е о р е м а 1.

Пусть множество A = {a1 , . . . , ak } состоит изk элементов, а множество B = {b1 , . . . , bm } — из m элементов. Тогда можно образовать ровно km пар (ai , bj ), взяв первый элемент измножества A, а второй — из множества B.Д о к а з а т е л ь с т в о. С элементом a1 мы можем образовать m пар:(a1 , b1 ), (a1 , b2 ), . . . , (a1 , bm ). Столько же пар можно составить с элементом a2 или с любым другим из k элементов множества A.

Таким образом,10ГЛАВА I. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ВЕРОЯТНОСТЕЙвсего возможно km пар, в которых первый элемент выбран из множестваA, а второй — из множества B.У п р а ж н е н и е . С помощью теоремы 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 местах.У п р а ж н е н и е .