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

UptoLike

ВУЗ: 

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

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

Рубрика: 

10
ЛЕКЦИЯ 2
§ 4. Количество k – элементных подмножеств данного конечного множе-
ства
Пусть задано конечное множество
A
с .)( n
A
N
=
Через )(
A
M
будем
обозначать множество всех подмножеств множества ,
A
через −)(AM
k
множество
всех −
k
элементных подмножеств множества ,
A
т.е ),(AMB
k
∈
если )(
A
M
∈
и
k
N
=)( , ).( n
k
≤
Теорема 6.
Число ))(( AMN
k
всех
−
k
элементных подмножеств множества
A
из n
элементов вычисляется по формуле
.
)!(!
!
))((
knk
n
AMN
k
−⋅
=
(11)
Доказательство. Обозначим искомое число ))(( AMN
k
для краткости через .
k
n
C
Будем строить −
k
элементные подмножества множества
A
действием из двух
этапов. На первом этапе построим
−
−
)1(
k
элементное подмножество, тогда число
способов осуществления первого этапа будет равно .
1
1
−
=
k
n
Cn На втором этапе к
полученному
−
− )1(
k
элементному подмножеству присоединим один из 1
+
−
k
n
элементов множества ,
A
которые не входят в это подмножество; ясно, что
.1
2
+−= knn Значит, согласно принципу умножения, в результате описанного
действия получим )1(
1
21
+−⋅=⋅
−
knCnn
k
n
−
k
элементных подмножеств. Но не
все они будут разными, так как каждое
−
k
элементное подмножество можно так
построить
k
способами: присоединением каждого из
k
его элементов к остальным
1−
k
его элементам. Поэтому найденное число в
k
раз больше, чем число
k
n
C
−
k
элементных подмножеств множества
A
. Следовательно,
.)1(
1−
⋅+−=⋅
k
n
k
n
CknCk Отсюда находим
=⋅
+−
=
−1
1
k
n
k
n
C
k
kn
C
.
2
1
...
1
21
...
1
n
C
n
k
kn
k
kn
⋅
−
⋅⋅
−
+
−
⋅
+
−
=
Но число одноэлементных подмножеств множества
A
равно ),(
A
N
т.е. .
1
nC
n
=
Следовательно,
.
)!(!
!
)!(
)!(
!
)1(...)1(
knk
n
kn
kn
k
knnn
C
k
n
−⋅
=
−
−
⋅
+
−
⋅
⋅−⋅
=
Теорема 6 до-
казана.
Замечание. Произвольное −
k
элементное подмножество множества из
n
элемен-
тов в комбинаторике называется сочетанием из n элементов по
k
элементов. По-
рядок элементов в подмножестве не имеет значения, поэтому часто вместо слова
«сочетание» употребляется термин – комбинация или соединение из n элементов
по
k
элементов, которые отличаются, по крайней мере одним элементом, но не по-
рядком элементов.

Страницы