Четыре лекции по комбинаторике. Семенов А.С. - 11 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

13
тов множества ,
A
то
).1(...)1( +−⋅⋅−⋅= knnnA
k
n
(16)
Доказательство. В соответствии с определением размещений рассмотрим дейст-
вие из двух этапов, приводящее в результате к получению размещения из n по .
k
Первый этап: образование
−
k
элементного подмножества, ;
1
k
n
Cn = второй этап:
образование перестановки в полученном на первом этапе
−
k
элементном подмно-
жестве, !.
2
kn = Тогда, согласно принципу умножения, имеем
).1(...)1(
)!(!
!!
21
+−⋅⋅−⋅=
−
⋅
=⋅=⋅= knnn
knk
kn
PCnnA
k
k
n
k
n
Теорема 9 доказана.
Пример 11. Сколькими способами можно рассадить 4 учащихся на 25 местах ?
Решение. Искомое число способов равно .30360022232425
4
25
=⋅⋅⋅=A
§ 8. Перестановки с повторением
Пусть задано множество .)(},,...,,{
21
mANaaaA
m
=
=
Определение 3.
Упорядоченные −n ки, содержащие
i
k раз элемент ),...,1( miA
i
a =∈ , при-
чем
∑
=
=
m
i
i
nk
1
, называются перестановками с повторением.
Пример 12. Для множества },{ ba
A
= составить все перестановки с повторением,
если .1,2,3
21
=== kkn
Решение. Пользуясь определением 3, получаем ).,,(),,,(},,,( aabababaa Всего
три перестановки с повторением.
Теорема 10.
Если обозначить через
),...,,(
21 mn
kkkC число всех перестановок с повторе-
нием, то
.
!!!
!
),...,,(
21
21
m
mn
kkk
n
kkkC
⋅⋅⋅⋅
=
(17)
Доказательство.
Рассмотрим действие из
1
+
m
этапа. Первый этап: образование
перестановки с повторением,
=
1
n
),...,,(
21 mn
kkkC
; второй этап: в полученной пе-
рестановке с повторением заменим все элементы
1
a разными элементами из мно-
жества },...,,{
21 n
bbbB = и произведем перестановку их, !.
12
kn
=
Третий этап: в пе-
рестановке с повторением заменим все элементы
2
a разными из оставшихся эле-
ментов множества
B
и произведем перестановку их, !.
23
kn = Последний
−+ )1(m ый этап: в перестановке с повторением заменим все элементы
m
a
разны-
ми из оставшихся элементов множества
B
и произведем перестановку их,
!.
1 mm
kn =
+
В результате описанного действия получатся все перестановки из n
различных элементов, т.е.
!n
таких перестановок. Теперь, согласно принципу умно-
жения, имеем

Страницы