Раздел 1. Классическая вероятностная схема
1.1 Основные формулы комбинаторики
В данном разделе мы займемся подсчетом числа «шансов». О числе шансов говорят, когда возможно несколько различных результатов какого-либо действия (извлечение карты из колоды, подбрасывание кубика или монетки, двух кубиков и т.д.). Число шансов — это число таких возможных результатов, или, иначе говоря, число способов проделать это действие.
Теорема о перемножении шансов
Теорема 1 . Пусть имеется, k групп элементов, причем i -я группа содержит ni элементов, 1<= i <= k . Выберем из каждой группы по одному элементу. Тогда общее число N способов, которыми можно произвести такой выбор, равняется
Замечание 1 . В теореме 1 считается, что даже если все элементы в i -й группе неразличимы, выбрать один из них можно ni способами.
Замечание 2. Результат выбора, описанного в теореме 1 , представим в виде набора (а1 , а 2 ,…, а k ) в котором а i — выбранный из i -й группы элемент. Тогда общее число различных наборов (а1 , а 2 ,…, а k ) также равняется
Доказательство теоремы 1.
Занумеруем элементы i -ой группы числами от 1 до ni . Элемент из первой группы можно выбрать n 1 способами. Если мы выбрали элемент j , 1<= i <= n 1 , то выбрать элемент из второй группы мы можем n 2 способами. Получаем, что с первым элементом j возможно составить n 2 пар ( j , l ) , где 1<= l <= n 2 .
Но столько же пар можно составить и с любым другим элементом первой группы. Тогда всего пар, в которых первый элемент выбран из первой группы, а второй — из второй, существует ровно
Иначе говоря, есть способов выбрать по одному элементу из первых двух групп. Возьмем одну такую пару ( j , l ) . Заметим, что элемент из третьей группы можно выбрать n 3 способами, то есть возможно составить ровно n 3 троек ( j , l , m ) , добавляя к данной паре ( j , l ) любой из n 3 элементов третьей группы.
Но столько же троек можно составить и с любой другой парой ( j , l ). Тогда всего троек, в которых первый элемент выбран из первой группы, второй — из второй, а третий — из третьей, существует ровно .
Продолжая рассуждения, методом математической индукции заключаем справедливость утверждения теоремы.
Урны и шарики
Есть урна, (то есть ящик), содержащая n занумерованных объектов, которые мы без ограничения общности будем считать шариками. Мы выбираем из этой урны k шариков. Нас интересует, сколькими способами можно выбрать k шариков из n , или сколько различных результатов (то есть наборов, состоящих из k шариков) получится.
На этот вопрос нельзя дать однозначный ответ, пока мы не определимся
· с тем, как организован выбор (скажем, можно ли шарики возвращать в урну), и
· с тем, что понимается под различными результатами выбора.
Рассмотрим следующие возможные схемы выбора:
1. Выбор с возвращением: каждый выбранный шарик возвращается в урну, то есть каждый из k шариков выбирается из полной урны. В полученном наборе, состоящем из k номеров шариков, могут встречаться одни и те же номера (выборка с повторениями ).
2. Выбор без возвращения: выбранные шарики в урну не возвращаются, и в полученном наборе не могут встречаться одни и те же номера (выборка без повторений ).
И в том, и в другом случае результатом выбора является набор из k номеров шариков. Удобно считать, что шарики всегда выбираются последовательно, по одному (с возвращением или без).
Условимся, какие результаты мы будем считать различными .
Есть ровно две возможности.
1. Выбор с учетом порядка: два набора номеров шариков считаются различными, если они отличаются составом или порядком номеров. Так, при выборе трех шариков из урны, содержащей 5 шариков, наборы (1,2,5), (2,5,1) (4,4,5) различны, если производится выбор с учетом порядка.
2. Выбор без учета порядка: два набора номеров шариков считаются различными, если они отличаются составом. Наборы, отличающиеся лишь порядком следования номеров, считаются одинаковыми. Так, в примере выше первые два набора (1,2,5), (2,5,1) есть один и тот же результат выбора, а набор (4,4,5) — другой результат выбора.
Подсчитаем теперь, сколько же возможно различных результатов при каждой из четырех схем (выбор с возвращением и без, и в каждом из этих случаев учитываем ли мы порядок или нет).
Урновая схема: выбор без возвращения, с учетом порядка
Одними из наиболее популярных услуг на рынке IT-технологий являются создание и продвижение лендингов. Они способны положительно влиять на деятельность любого бизнес-проекта в интернете. Судя по многочисленным отзывам, заказавшие создание лендингов люди ни разу не пожалели о потраченных деньгах. Они вложили в будущее, которое неразрывно связано с интернетом. Всё больше и больше предпринимателей обращаются к услугам разных агентств, веб-студий, чтобы заказать создание лендинга у профессионалов.