1.3.3 Сочетания при выборе с возвращением и без возвращения

Любое подмножество из k элементов некоторого множества из n эле-

ментов называют сочетанием из n по k . Одно сочетание отличается от

15

другого хотя бы одним элементом. Число сочетаний находят по формулам:

C_nk₌

Ak

n

k!

=

n(n − 1)(n − 2) · · · (n − k + 1)

k!

=

n!

k!(n − k)!

.

Действительно, любое множество, содержащее k элементов, возможно

упорядочить k! способами. Следовательно, число размещений A^kn больше

числа соответствующих сочетаний C_nk в k! раз, т. е. A^kn⁼k! · C_nk . Разделив

формулы для подсчета числа размещений на k! , получим формулы вычис-

ления количества сочетаний.

Для чисел C_nk_,называемых также биномиальными коэффициен-

тами, справедливы следующие тождества:

C_nk₌C_nn−k (свойство симметрии),

C_nk₊₁= C_nk₊C_nk−1 (рекуррентное соотношение),

C_n0₊C_n1₊C_n2₊· · · + C_nn_{= 2}n (следствие биномиальной формулы Ньютона).

Два первых тождества выводятся непосредственно из формулы расчета

числа сочетаний. Для вывода третьего соотношения воспользуемся формулой

бинома Ньютона, которая справедлива для любых чисел a , b и любого на-

турального числа n :

n

(a + b)ⁿ= ∑_Cn^kaⁿ−k_bk_.

k=0

Положив в данной формуле a = 1 и b = 1 , получим необходимое равен-

ство. Отметим также, что в левой части третьего тождества подсчитывается

количество одноэлементных, двухэлементных и т. д. подмножеств, включая

пустое множество и само конечное множество из n элементов. Как следует

из данного тождества число всех таких подмножеств равно 2ⁿ.

Пример. Из 10 различных изделий, среди которых 3 бракованных,

наудачу выбирают 3 изделия для контроля. Найти вероятность того, что в

полученной выборке ровно одно изделие бракованное.

Решение. Пронумеруем изделия числами от 1 до 10 , и пусть мно-

жество номеров C = {1, 2, . . . , 7} соответствует годным изделиям, а множе-

ство номеров D = {8, 9, 10} бракованным изделиям. Согласно описанию

эксперимента производится выбор трех изделий (причем порядок их появле-

ния не существенен) из множества E = C ∪ D , содержащего 10 изделий.

Поэтому пространство элементарных исходов представляет собой множество

сочетаний из 10 по 3 , содержащее N (Ω) = C₁₀3₌10₁·^·2⁹·^·3⁸= 120 элементов.

Искомому событию A благоприятствуют только такие исходы (тройки изде-

лий), в которых два изделия годные (принадлежат множеству C ), а ровно

16

одно бракованное (принадлежит множеству D ). Применяя принцип умно-

жения, получим, что число всех таких исходов равно N (A) = C₇2_·C₃1 = 63 .

Используя формулу классической вероятности, получим окончательно

P (A) =

N (A)

N (Ω)

=

63

120

=

21

40

.

Cхема выбора с возвращением и без упорядочивания.

В данной схеме случайный выбор k элементов из множества, содер-

жащего n элементов, организован таким образом, что каждый выбранный

элемент возвращается обратно, так что при каждом следующем выборе мо-

жет быть взят как новый элемент, так и любой ранее выбранный. Полученное

таким образом соединение называют сочетанием с повторениями . Одно

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

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

n элементов по k обозначается Ї_nk и находится по следующей формуле:

CЇ_nk₌C_nk₊k−1^.

Действительно, в соответствии со схемой с возвращением и упорядочи-

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

соединений длиной k равно n(n + 1)(n + 2) · · · · · (n + k − 1) . Разделив дан-

ное число на k! и домножив числитель и знаменатель полученной дроби на

(n − 1)! , найдем число сочетаний с повторениями в указанном выше виде

Їk

n⁼

(n − 1)! · n(n + 1)(n + 2) · · · · · (n + k − 1)

k! · (n − 1)!

=

(n + k − 1)!

k! · (n − 1)!

= C_nk₊k−1^.

Пример. В кондитерской продается десять видов пирожных. Какова

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

три пирожных разного вида?

Решение. Число всевозможных наборов из трех пирожных по смыслу

решаемой задачи находится по формуле расчета сочетаний с повторениями

из 10 элементов по 3 ЇC₁₀3₌C₁₂3 = 220 . Число наборов из трех пирожных

разного вида равно числу сочетаний из десяти элементов по три C₁₀3 = 120 .

По формуле вычисления вероятности события в классической схеме получим

P (A) =

N (A)

N (Ω)

=

120

220

=

6

11

.