Дискретная математика. Элементы теории, задачи и упражнения. Часть 1. Булгакова И.Н. - 37 стр.

UptoLike

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

37
Сочетания без повторений и с повторениями
Сочетаниями без повторений из п элементов по k называются не-
упорядоченные k-выборки из п элементов без повторений. Их число обо-
значается
k
n
C
и вычисляется по формуле
k
n
C
=
k)!-(nk!
!n
, k
£
n. (5)
Сочетания из n по k без повторений образуют k-элементарные под-
множества исходного множества мощности n. Числа
k
n
C
называются би-
номиальными коэффициентами.
Пример 11. Сколькими способами можно выбрать три различные
краски из имеющихся пяти?
Решение. Очевидно, что нужно подсчитать число 3-выборок из
5 элементов, причем по условию задачи понятно, что среди выбранных эле-
ментов не должно быть одинаковых и что порядок расположения выбранных
красок не существенен. Значит, нужно найти число неупорядоченных выбо-
рок, т. е. число сочетаний без повторений из 5 по 3. По формуле (5) имеем:
3
5
С
=
)!35(!3
!5
-
= 5
´
!
2
4
= 10.
Сочетаниями с повторениями из п элементов по k называются не-
упорядоченные k-выборки из п элементов с повторениями. Их число обо-
значается
k
n
H
и вычисляется по формуле
k
n
H
=
k
kn
C
1-+
=
)!1(!
)!1(
-
-
+
nk
kn
, Nkn
Î
, . (6)
Пример 12. В киоске имеются открытки 10 видов. Сколькими спосо-
бами можно купить: а) 5 открыток? б) 5 разных открыток? в) 15 открыток с
повторениями?
Решение. В случаях а) и в) нас интересуют неупорядоченные выбор-
ки из 10 элементов с повторениями длины 5 и 15 соответственно. Их число
определяется по формуле (6):
a)
5
10
H
=
5
1051
C
+-
=
5
14
C
=
)!514(!5
!14
-
=
5!
10 11 12 13 14
´
´
´
´
=2002 (способа);
в)
15
10
H
=
15
10151
C
+-
=
15
24
C
=
)!1524(!15
!24
-
=
!
9
!
15
!24
(способов).
В случае б) нужно подсчитать число неупорядоченных 5-выборок из
10 элементов без повторений (все открытки разные). Их число определяет-
ся по формуле (5) :
5
10
C
=
!
5
!
5
!10
= 252 (способа).