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

UptoLike

ВУЗ: 

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

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

Рубрика: 

12
∑
=
=
n
k
nk
n
C
0
,2 (14)
поскольку −
k
n
C число −
k
элементных подмножеств множества из n элементов, то
сумма в левой части есть число всех подмножеств.
§ 6. Перестановки данного конечного множества
Пусть задано конечное множество
A
с .)( n
A
N
=
Определение 1.
Упорядоченные −n ки (кортежи длины )n , содержащие все элементы множе-
ства ,
A
называются перестановками этого множества. Другими словами, переста-
новки - это комбинации или соединения из n элементов, содержащие все элементы,
и которые считаются различными, если отличаются порядком элементов.
Пример 9. Пользуясь определением составить все перестановки множества
}.,,{ cba
A
=
Решение ),,,(),,,( bcacba ),,,(),,,( acbcab ).,,(),,,( abcbac Всего шесть пе-
рестановок.
Теорема 8.
Если через
n
P обозначить число всех перестановок множества
,
A
то
!.nP
n
=
(15)
Доказательство. Будем последовательно выбирать элементы множества
A
и
размещать их в определенном порядке на n местах. На первое место можно поста-
вить любой из n элементов. После того как заполнено первое место, на второе ме-
сто можно поставить любой из 1
−
n оставшихся элементов и т.д. По принципу
умножения все n мест можно заполнить и получить в результате перестановку
!12...)2()1( nnnn =⋅⋅⋅−⋅−⋅ способами. Теорема 8 доказана.
§ 7 Размещения данного конечного множества
Пусть дано конечное множество
A
с .)( n
A
N
=
Определение 2.
Перестановки −
k
элементных подмножеств множества
A
называются раз-
мещениями из n элементов по
k
элементов. Другими словами, размещения из n
элементов по
-- это комбинации или соединения, содержащие
k
различных эле-
ментов, и которые считаются различными, если отличаются либо своими элемента-
ми, либо порядком элементов.
Пример 10. Пользуясь определением составить все размещения из 3 по 2 для мно-
жества
}.,,{ cba
A
=
Решение.
Выписываем все двухэлементные подмножества
},,{{)(
2
baAM = }},{},,{ cbca и для каждого из них - все перестановки. Получаем
искомые размещения ),,(),,(),,(),,(),,(),,( bccbaccaabba всего шесть размещений.
Теорема 9. Если через
k
n
A обозначить число всех размещений из n по
k
элемен-

Страницы