Дискретная математика. Ерош И.Л - 70 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

70
4.1.7. Сочетания без повторений
Если требуется выбрать k предметов из n и порядок выбора безраз
личен, то имеем
!
.
!( )!
k
n
n
С
kn k
1
2
(4.7)
Формула (4.7) может быть получена следующим образом. Выберем
по очереди k предметов из n. Число вариантов выбора будет определять
ся формулой (4.3). Однако порядок выбранных предметов нас не интере
сует, поэтому, разделив это выражение на k!, получим формулу (4.7).
Пример 1. Из группы в 25 человек нужно выбрать троих для рабо
ты в колхозе. Если выбирать их, присваивая номера, то получим
25·24·23 варианта. Но порядок выбора нам не важен, поэтому реше
ние нужно разделить на 3! = 6.
Пример 2. В середине 60х годов в Советском Союзе появились две
лотереи, которые по недоразумению были названы «Спортлото», а
именно, лотерея выбора 5 из 36 и лотерея выбора 6 из 49. Рассмотрим
одну из них, например 6/49. Играющий покупает билет, на котором
имеется 49 клеточек. Каждая клеточка соответствует какомулибо
виду спорта. Нужно выделить (зачеркнуть) 6 из этих клеточек и от
править организаторам лотереи. После розыгрыша лотереи объявля
ются 6 выигравших номеров. Награждаются угадавшие все 6 номеров,
5 номеров, 4 номера и даже угадавшие 3 номера. Соответственно, чем
меньше угадано номеров (видов спорта), тем меньше выигрыш.
Подсчитаем, сколько существует разных способов заполнения карто
чек «Спортлото». Казалось бы, заполняя последовательно номер за номе
ром, должны получить: 49 · 48 · 47 · 46 · 45 · 44. Но ведь порядок заполне
ния карточек не важен, поэтому используется формула числа сочетаний
6
49
49!
13 983 816.
6!43!
С 11
Эту же задачу можно решить и другим способом. Выпишем все но
мера подряд и под выбираемыми номерами поставим 1, а под осталь
ными – 0. Тогда различные варианты заполнения карточек будут от
личаться перестановками 1 и 0. При этом переставляется 6 единиц,
соответствующих выбираемым клеточкам, и 43 нуля, соответствую
щих невыбираемым клеточкам, т. е. получаем
12
49!
6, 43 13 983 816.
6!43!
P 33
Если все участники заполнят карточки поразному, то в среднем
один из 14 миллионов участников выиграет 6 номеров. А сколько че
ловек в среднем из 14 миллионов участников угадают 5 номеров?

Страницы