Дискретная математика. Комбинаторика. Соколова С.В. - 13 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

13
соответствуют
одному
сочетанию
{
}
,
a b
.
Таким
образом
,
число
сочетаний
m
n
C
в
!
раз
меньше
числа
размещений
m
n
A
:
( )
!
! ! !
m
m
n
n
A n
C
m m n m
= =
−
.
Пример
.
Количество
способов
,
которыми
мы
можем
выбрать
из
восьми
дворников
троих
равно
( )
3
8
8! 8!
56.
3! 8 3 ! 3! 5!
C
= = =
− ⋅
9.
СОЧЕТАНИЯ
С
ПОВТОРЕНИЯМИ
Задача
.
Найти
количество
m
n
C
сочетаний
с
повторениями
из
n
предметов
по
m
.
Рассмотрим
вывод
формулы
на
примере
с
фотографиями
(
см
.
2.1.2).
Имеется
n
типов
предметов
3
n
=
негатива
).
Нужно
составить
набор
из
m
предметов
(
m
=5
фотографий
).
Наборы
различаются
своим
составом
,
а
не
порядком
элементов
.
Например
,
разными
будут
наборы
состава
(3,1,1)
и
(1,0,4) –
один
содержит
три
фотографии
с
первого
негатива
и
по
одной
со
второго
и
третьего
,
а
другой
–
одну
с
первого
и
четыре
с
третьего
.
Разложим
эти
наборы
на
столе
,
разделяя
фотографии
разного
типа
карандашами
.
Карандашей
нам
понадобится
1 3 1 2
n
− = − =
,
а
фотографий
5
m
=
.
Мы
будем
получать
различные
сочетания
с
повторениями
,
переставляя
между
собой
эти
(
)
1
n m
− +
предметов
,
т
.
е
.
( )
1
1,
m
n
n m
C P n m
− +
= − −
число
сочетаний
с
повторениями
из
n
предметов
по
m
равно
числу
перестановок
с
повторениями
длины
1
n m
− +
состава
(
)
1,
n m
−
.
В
нашем
примере
( ) ( )
5
3
3 1 5 7
7!
3 1,5 2,5 21
2! 5!
C P P
− +
= − = = =
⋅
.
Иначе
формулу
сочетаний
с
повторениями
можно
записать
(
)
( )
1
1 !
1 ! !
m
m
n
n m
n m
C C
n m
− +
− +
= =
− ⋅
.

Страницы