Элементы комбинаторики. Модели случайного выбора

Вопросы, которые рассматриваются в этом параграфе, не имеют особого значения с точки зрения общей теории, так как здесь изучается некоторая частная модель, связанная с классическим определением вероятности. Но модели случайного выбора широко используются в экономике, социологии, демографии и других науках. В силу этого они очень важны с практической точки зрения.

Как мы видели выше, при классическом определении вероятности нам нужно решить две задачи: вычислить число всех элементарных исходов  и число  благоприятных исходов для события А. Обычно это сводится к подсчету того, сколькими способами может быть выполнено некоторое действие, т. е. сколько существует вариантов. Задачами такого типа занимается специальный раздел математики, называемыйкомбинаторикой. Мы начнем изучение основ комбинаторики с одной элементарной, но очень полезной леммы.

Лемма 1 (умножения). Пусть некоторое действие осуществляется в два этапа. На первом этапе мы имеем вариантов его осуществления, а на втором, независимо от того, что произошло на первом этапе,- вариантов. Тогда общее число вариантов осуществления такого действия равно 

Доказательство этой леммы сводится к установлению взаимно однозначного соответствия между двухэтапными вариантами и клетками таблицы размера

Нас в основном будут интересовать задачи комбинаторики, которые можно сформулировать в терминах выбора некоторого количества предметов из заданной совокупности  При этом необходимо учитывать два обстоятельства: как производился выбор и как фиксировался результат выбора. В первом случае мы имеем два варианта: выбор с повторением, когда на каждом этапе выбранный предмет возвращается назад и выбор производится из одной и той же совокупности; выбор без повторения, когда выбранный на некотором шаге предмет уже не используется в дальнейшем. При фиксации результата мы также имеем два варианта: с учетом порядка (в этом случае мы знаем, какие выбраны предметы и в каком порядке) и без учета порядка (здесь мы знаем только, какие были выбраны предметы, но не имеем информации о порядке их появления). Имея в виду вероятностные и статистические применения рассматриваемых задач, мы будем называть результат выбора элементарным исходом или выборкой. Число элементов в выборке называется ееобъемом. Рассмотрим несколько стандартных примеров.

Определение 1. Размещением с повторением изэлементов по называется произвольная упорядоченная выборка с возвращением, объемаиз совокупности

В этом случае , где. Используя лемму

умножения, легко подсчитать, что число различных элементарных исходов будет равно 

Определение 2. Размещением (без повторения) из  элементов по называется произвольная упорядоченная выборка без возвращения объема из совокупности

Здесь . Вновь по лемме

умножения получаем ,что число различных размещений равно 

Если , то такое размещение называется перестановкой. Число различных перестановок  элементов равно

Определение 3. Сочетанием (без повторений) из  элементов по называется произвольная неупорядоченная выборка без возвращения объема  из совокупности

В этом случае мы отмечаем только, какие именно элементы вошли в эту выборку, и не учитываем порядок их появления. Поэтому для каждого элемента достаточно указать, входит он в выборку или нет. Таким образом, , где , если  входит в выборку , и равно 0 в противном случае. Из каждого сочетания, переставляя его элементы, мы получаем  различных размещений. В силу этого число сочетаний в раз меньше числа размещений, т. е. 

Определение 4. Сочетанием с повторением из  элементов по называется произвольная неупорядоченная выборка с возвращением объема из совокупности 

Так как теперь один элемент может входить в выборку несколько раз, то элементарный исход имеет вид , где   означает, что элемент   входит в выборку  раз. Для подсчета числа таких выборок применим следующий вспомогательный прием. Выпишем сначала все элементы , затем  и так далее. Между элементами разных типов поставим перегородки. Таким образом, мы имеем  элементов и  перегородку. Если каких-то элементов нет, то перегородки стоят рядом. Для задания сочетания с повторением достаточно расставить   перегородку на  возможных мест без учета порядка. Это можно сделать  способами.

Рассмотрим два важных с практической точки зрения примера.

Пример 1. Пусть мы имеем некоторую совокупность, содержащую предметов, из которых - одного типа и - другого типа. С возвращением выбираем предметов из этой совокупности. Найти вероятность события того, что среди них будет  предметов первого типа.

Так как выбор осуществляется с возвращением, то мы имеем всего различных элементарных исходов в этой задаче. Благоприятные исходы легче пересчитать, используя следующее замечание. Сначала мы должны выбрать, на каких шагах мы будем отбирать предметы первого типа. Это можно сделать  способами. Затем на каждом из этих шагов мы имеем вариантов, а на остальных- вариантов. По лемме умножения число благоприятных исходов будет равно . Если обозначить через долю предметов первого типа во всей совокупности, то получим 

Пример 2. Пусть мы имеем ту же задачу, что и в примере 1, но выбор осуществляется без возвращения.

В этом примере удобнее фиксировать результат без учета порядка следования элементов. Тогда общее число элементарных исходов . Для получения благоприятного исхода нужно в два этапа набрать элементов первого типа (из ) и  элементов второго типа (из ), т. е. по лемме умножения . Тогда по классическому определению вероятности получаем 

Задача 1. Пусть в примере  так что  (0,1), а  и  - фиксированы. Тогда 

Таким образом, в этом случае выбор с возвращением и выбор без возвращения эквивалентны. Легко понять, почему так получилось. Дело в том, что для больших совокупностей удаление небольшого числа элементов не меняет практически пропорций, т. е. мы имеем на каждом шаге выбор из той же совокупности.

Пример 3. В некотором городе живет 100 ООО человек, среди которых 60 ООО женщин. Для проведения социологического обследования производят выборку объема 500. Найти вероятность того, что среди них будет 300женщин.

Так как отбор 500 человек не изменит существенно пропорций, то можно считать, что мы имеем выбор с возвращением. Здесь

. Тогда 

Примеры 1 и 2 можно обобщить на случай выбора из совокупностей, где есть предметы  типов