Элементы дискретной математики - 22 стр.

UptoLike

ВУЗ: 

ЯГПУ им. Ушинского | Ярославль

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

Рубрика: 

22
Даны n различных предметов и k ящиков. Надо положить в первый ящик n
1
предметов, во второй – n
2
, ..., в k-ый – n
k
, где n
1
+...+n
k
=n. Сколькими способами можно
сделать такое распределение, если не интересует порядок предметов в ящике?
Выложим все предметы в один ряд. Это можно сделать n! способами. Первые n
1
предметов положим в первый ящик, вторые n
2
предмета – во второй ящик, …,
k-ые n
k
предметов – в к-ый ящик. Так как нас не интересует порядок предметов в ящике, то любая
перестановка первых n
1
предметов не меняет результат раздела. Точно так же его не меняет
любая перестановка вторых n
2
предметов, ..., k-ых n
k
предметов. По правилу произведения
получаем n
1
! ⋅n
2
!⋅...⋅n
k
! перестановок, не меняющих результата раздела. Таким образом, n!
перестановок делятся на группы по n
1
! ⋅n
2
!⋅...⋅n
k
! перестановок в каждой группе, причем
перестановки из одной группы приводят к одинаковому распределению предметов.
Следовательно, число раздела предметов равно
!...!!
!
21 k
nnn
n
⋅⋅⋅
=P(n
1
,...,n
k
).
Задача.
При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут
это сделать?
Решение.
Переформулируем задачу: необходимо разложить 28 предметов в 4 ящика по 7
предметов в каждый, причем порядок предметов в ящике не важен. Получаем
4
)!7(
!28
способов распределения костей домино.
Можно было рассуждать другим способом. Первый игрок выбирает себе 7 костей из 28,
это можно сделать
7
28
C способами. Второму необходимо выбрать 7 костей из
оставшихся 21, это можно сделать
7
21
C способами. Третьему 7 из 14 –
7
14
C способов. А
четвертый заберет оставшиеся. По правилу произведения получаем
7
14
7
21
7
28
CCC ⋅⋅ .
Даны n различных предметов и k одинаковых ящика. Надо положить в каждый
ящик n
1
предметов, где n
1
=
k
n
. Сколькими способами можно сделать такое распределение,
если не интересует порядок предметов в ящике, и все ящики одинаковы?
Задача отличается от предыдущей только тем, что ящики не пронумерованы. Так
как k ящиков можно переставить k! способами, то полученный в предыдущей задаче
результат необходимо разделить на k!. Всего
k
nk
n
)!(!
!
1
⋅
способов распределения.

Страницы