Материал: Введение в статистические методы управления качеством. учебное пособие. Пентюхов В.И., Мищенко Е.В
1.4.2. Соединения и выборки
Процедура построения размещений называется еще выбор без возвращений, при этом каждое из размещений называют упорядоченной выборкой объема m. В другом случае, при выборе с возвращением любой элемент, извлеченный для формирования выборки из исходной совокупности (генеральная совокупность), заменяется эквивалентным и происходит восстановление исходного состава генеральной совокупности.
Таким образом, в конкретной выборке каждый элемент может встречаться несколько раз.
Все возможные выборки с возвращением, которые можно сформировать из элементов трех типов a, b и c по 2, будут такие (сравни с предыдущим случаем):
aa, ab, ac, ba, bb, bc, ca, cb, cc;
Для формирования всех таких соединений по 2 надо записать строку исходных элементов дважды
a, b, c…
a, b, c…
и каждый элемент первой строки последовательно объединять со всеми элементами второй строки.
Если полное число
элементов есть n, то число возможных
соединений по 2 равно
.
Итак, если объем
выборок равен m, то необходимо
записать m строк и, следовательно,
количество упорядоченных выборок с
возвращением будет равно
.
В комбинаторике
стремятся к формальной аналогии в записи
близких по своему смыслу величин. Поэтому
число выборок без возвращений (число
размещений) часто записывают, как
.
Последнюю величину полагают по определению
равной
и называют убывающий m-факториал.
Очевидно, что при
m=n справедливо следующее равенство:
Примеры.
1. Сколько двоичных кодов можно записать на 8-разрядной сетке?
Число таких кодов, например 01101001, совпадает с числом возможных выборок с возвращением объема 8 из двух элементов 0 и 1.
Следовательно,
m=8 и n=2, ответом будет число равное
.
2. Сколько целых трехзначных чисел можно записать, используя 10 десятичных цифр 0, 1, …,9
Из 10 элементов
(цифр) можно сформировать
выборок
с возвращением по 3. Однако, выборки,
имеющие 0 на первой позиции, соответствуют
либо двузначным, либо однозначным
числам, либо нулю и их надо исключить.
Таких комбинаций будет столько, сколько
возможно выборок с возвращением из 10
элементов по 2, то есть
.
Следовательно, трехзначных чисел будет
.
Выбор m элементов из генеральной совокупности объема n является экспериментом, возможными исходами которого являются различные выборки объема m. Общее число их равно или , в зависимости от того, как производится выбор: с возвращением или без возвращения. Предположим, что выбор производится случайно и так, что все выборки равновероятны.
Какова вероятность, что случайно извлеченная выборка с возвращением не имеет одинаковых элементов, то есть эта выборка является размещением и могла бы быть получена при выборе без возвращения?
Воспользуемся формулой благоприятных исходов.
При случайной
выборе с возвращением общее число
исходов равно
,
а благоприятными являются лишь те
исходы, которым соответствует выбор
без возвращений, их число равно
.
Таким образом, искомая вероятность равна
.
Если объем
генеральной совокупности n велик,
а m сравнительно мало, то отношение
близко
к единице. Это говорит о том, что при
большой генеральной совокупности и
относительно малой выборке различие
между двумя способами выбора незначительно,
и
.
В следующих примерах раскрывается неожиданное свойство приведенной выше вероятности.
Примеры.
1. Имеется группа из m случайно выбранных людей. Какова вероятность, что все люди из этой группы имеют различные дни рождения? Для простоты можно игнорировать существование високосных годов и принять, что в году 365 дней.
Дни рождения m произвольно выбранных людей образуют случайную выборку объема m с возвращением из всех дней в году. Нас интересуют те выборки, элементы которых различны. Вероятность выбора одной из них равна
Расчеты по этой формуле приведут нас к парадоксальным результатам. Для малой выборки кажется правдоподобным заключение, что p близко к единице. И действительно, для m = 10 человек p = 0.883. Однако, уже для m = 23, что тоже невелико, p < 0.5, то есть в более 50% групп с такой численностью найдутся, по крайней мере, двое, имеющие общий день рождения.
2. В городе на каждую неделю приходится в среднем семь автомобильных катастроф. Какова вероятность равномерного распределения катастроф по дням недели? Предполагается, что все возможные распределения равновероятны.
Решение сводится
к случайному выбору с возвращением семи
дней недели, для семи катастроф
.
Объем выборки m =7 равен числу
элементов n =7, из
которых производится выбор. Напомним,
что
,
и приведенная выше формула для вероятности
выборки с различающимися элементами
даст:
.
Таким образом, равномерное распределение числа катастроф встречается очень редко, в среднем лишь для одной недели из 163. Обычно, на какие то дни недели приходится две и более катастроф. Удивительно, что этот вывод следует из предположения о равной вероятности всех дней недели в отношении возможных катастроф.
3. Какова вероятность, что при шести бросаниях правильной кости появятся все возможные грани?
Ситуация аналогична
рассмотренной в предыдущем примере.
Через
обозначим
последовательность номеров граней,
появившихся в серии из 6 бросаний. Полное
число вариантов равно числу выборок с
возвращением из 6 по 6 элементов.
Благоприятными являются выборки без
возвращений из 6 по 6 элементов
(перестановки). Интересующая нас
вероятность есть
-
это всего 1.5%, что, на первый взгляд, также
противоречит представлению о равной
вероятности выпадения всех граней.
1.4.3. Сочетания
Если из всех размещений, которые можно составить из n элементов по m, отобрать только те, которые отличаются друг от друга, по крайней мере, одним элементом, то получим соединения, которые называются сочетаниями. Например, из трех элементов a, b, c сочетания по 2 будут:
ab, ac, bc
Если в каждом из этих сочетаний сделаем все возможные перестановки, то получим все возможные размещения из трех элементов по 2. Это справедливо и в общем случае произвольных n и m.
Таким образом,
число всех размещений из n
элементов по m равно числу всех
сочетаний из n по m,
умноженному на число перестановок
,
какие можно сделать в каждом сочетании
по m элементов, то есть
,
где
означает число всех сочетаний из n
элементов по m.
Отсюда выводим следующую формулу для числа сочетаний:
.
Умножая числитель
и знаменатель правой части этой формулы
на
,
который равен
,
получим
.
Следовательно, формулу для числа сочетаний можно записать и так:
,
откуда легко
увидеть следующее важное свойство
симметрии
.
Это равенство имеет четкий смысл для m < n .
В комбинаторике
удобно принимать, что указанное свойство
симметрии справедливо и для m
= n, то есть
.
Учитывая, что
,
для согласованности приведенных выше
формул полагают, по определению, что
и
.
Числа
часто
называют еще биномиальными
коэффициентами и обозначают так
.
Таким образом,
,
,
.
Такое название
этих чисел связано с тем, что они являются
коэффициентами разложения n-ой
степени бинома
по
степеням
:
,
это частный случай общей формулы, называемой кратко бином Ньютона.
1.4.4. Задачи о размещении элементов по ячейкам.
В абстрактной формулировке это – задача о числе вариантов размещения m шаров по n ящикам.
Многие схемы комбинаторики, внешне весьма различные, по существу эквивалентны абстрактной схеме распределения m шаров по n ящикам.
Так распределение дней рождения m человек соответствует размещению m шаров по n =365 ящикам (см. выше, пример 1.2.3). Классификация m несчастных случаев по дням недели, в которые они происходят (см. там же пример 1.2.4), эквивалентна размещению m шаров по n =7 ящикам. Заметим, что часто употребляемый в этой ситуации термин “размещение”, используется как синоним термина “распределение”. Последний более предпочтителен в нашем контексте, поскольку он не вносит путаницу с понятием размещения как вид соединений.
Обращаясь к задачам качества, рассмотрим партию из N изделий, в которой D изделий являются дефектными. Все изделия находятся в ячейках по одному в каждой ячейке. Сколько возможно вариантов размещения D дефектных изделий по N ячейкам? Ячейки предполагаются перенумерованными, а изделия различаются только по признаку годности. Очевидно, что интересующее нас число размещений совпадает с числом возможных выборов D мест из заданных N для размещений дефектных изделий. Порядок этих мест роли не играет, так как все дефектные изделия в известном смысле равноправны.
Следовательно, искомое число вариантов совпадает с числом сочетаний из N по D, то есть равно
.
Можно разрешить помещать в ячейку любое число (не больше D) дефектных изделий. Тогда число возможных размещений определяется формулой
.