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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

11
выбранного
элемента
не
допускается
).
По
правилу
произведения
получаем
(
)
(
)
1 ... 1
m
n
A n n n m
= ⋅ − ⋅ ⋅ − +
.
Эта
формула
записывается
иначе
с
использованием
обозначения
! 1 2 ...
n n
= ⋅ ⋅ ⋅
.
Так
как
(
)
(
)
(
)
(
)
! 1 ... 1 ... 2 1 !,
m
n
⋅ − = ⋅ − ⋅ ⋅ − + ⋅ − ⋅ ⋅ ⋅ =
то
( )
!
!
m
n
n
A
n m
=
−
.
Пример
.
Сколько
может
быть
различных
списков
победителей
олимпиады
(
первое
,
второе
,
третье
место
),
если
участвовало
20
человек
?
Здесь
20, 3
n m
= =
,
искомым
является
число
( )
3
20
20! 20!
20 19 18 6840.
20 3 ! 17!
A
= = = ⋅ ⋅ =
−
6.
ПЕРЕСТАНОВКИ
БЕЗ
ПОВТОРЕНИЙ
Рассмотрим
частный
случай
размещения
без
повторений
:
если
n r
=
,
то
в
размещении
участвуют
все
элементы
множества
X
,
т
.
е
.
выборки
имеют
одинаковый
состав
элементов
.
Такие
выборки
называются
перестановками
.
Количество
перестановок
из
n
элементов
обозначают
n
P
:
(
)
(
)
(
)
1 ... 1 1 ... !
n
n n
P A n n n n n n n
= = ⋅ − ⋅ ⋅ − + = ⋅ − ⋅ ⋅ =
Пример
.
Сколькими
способами
можно
выстроить
очередь
в
кассу
,
если
хотят
получить
зарплату
шесть
человек
?
6
6! 1 2 ... 6 720.
P
= = ⋅ ⋅ ⋅ =
7.
ПЕРЕСТАНОВКА
С
ПОВТОРЕНИЯМИ
Пусть
множество
X
состоит
из
k
различных
элементов
:
{
}
1 2
, ,...,
k
X x x x
=
.
Перестановкой
с
повторениями
состава
(
)
1 2
,...,
k
m m m
⋅
будем
называть
упорядоченный
набор
длины
1 2
...
k
n m m m
= + + +
,
в
котором
элемент
i
x
встречается
i
m
раз
(
)
1,2,...,
i k
=
.
Количество
таких
перестановок
обозначается
(
)
1 2
, ,...,
n k
P m m m
.
Пример
.
Из
букв
{
}
, ,
a b c
запишем
перестановку
с
повторением
состава
(2.2.1).
Ее
длина
2 2 1 5
n
= + + =
,
причем
буква
a
входит
2
раза
,

Страницы