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

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

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

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

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

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

Определение 1. Размещением с повторением изСтатья 353 - Картинка 8элементов по Статья 353 - Картинка 9называется произвольная упорядоченная выборка с возвращением, объемаСтатья 353 - Картинка 10из совокупностиСтатья 353 - Картинка 11

В этом случае Статья 353 - Картинка 12, гдеСтатья 353 - Картинка 13. Используя лемму

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

Определение 2. Размещением (без повторения) из Статья 353 - Картинка 15 элементов по Статья 353 - Картинка 16называется произвольная упорядоченная выборка без возвращения объема Статья 353 - Картинка 17из совокупностиСтатья 353 - Картинка 18

Здесь Статья 353 - Картинка 19. Вновь по лемме

умножения получаем ,что число различных размещений равно Статья 353 - Картинка 20

Если Статья 353 - Картинка 21, то такое размещение называется перестановкой. Число различных перестановок Статья 353 - Картинка 22 элементов равно

Статья 353 - Картинка 23

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

В этом случае мы отмечаем только, какие именно элементы вошли в эту выборку, и не учитываем порядок их появления. Поэтому для каждого элемента достаточно указать, входит он в выборку или нет. Таким образом, Статья 353 - Картинка 28, где Статья 353 - Картинка 29, если Статья 353 - Картинка 30 входит в выборку Статья 353 - Картинка 31, и равно 0 в противном случае. Из каждого сочетания, переставляя его элементы, мы получаем Статья 353 - Картинка 32 различных размещений. В силу этого число сочетаний вСтатья 353 - Картинка 33 раз меньше числа размещений, т. е. Статья 353 - Картинка 34

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

Так как теперь один элемент может входить в выборку несколько раз, то элементарный исход имеет вид Статья 353 - Картинка 39, где Статья 353 - Картинка 40 означает, что элемент Статья 353 - Картинка 41 входит в выборку Статья 353 - Картинка 42 раз. Для подсчета числа таких выборок применим следующий вспомогательный прием. Выпишем сначала все элементы Статья 353 - Картинка 43, затем Статья 353 - Картинка 44 и так далее. Между элементами разных типов поставим перегородки. Таким образом, мы имеем Статья 353 - Картинка 45 элементов и Статья 353 - Картинка 46 перегородку. Если каких-то элементов нет, то перегородки стоят рядом. Для задания сочетания с повторением достаточно расставить Статья 353 - Картинка 47 перегородку на Статья 353 - Картинка 48 возможных мест без учета порядка. Это можно сделать Статья 353 - Картинка 49 способами.

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

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

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

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

В этом примере удобнее фиксировать результат без учета порядка следования элементов. Тогда общее число элементарных исходов Статья 353 - Картинка 62. Для получения благоприятного исхода нужно в два этапа набрать Статья 353 - Картинка 63элементов первого типа (из Статья 353 - Картинка 64) и Статья 353 - Картинка 65 элементов второго типа (из Статья 353 - Картинка 66), т. е. по лемме умножения Статья 353 - Картинка 67. Тогда по классическому определению вероятности получаем Статья 353 - Картинка 68

Задача 1. Пусть в примере Статья 353 - Картинка 69 так что Статья 353 - Картинка 70 (0,1), а Статья 353 - Картинка 71 и Статья 353 - Картинка 72 - фиксированы. Тогда Статья 353 - Картинка 73

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

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

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

Статья 353 - Картинка 74. Тогда Статья 353 - Картинка 75

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