Дискретная математика. Азарнова Т.В - 32 стр.

UptoLike

Комбинаторика
32
В общем случае число сочетаний из
n
элементов по
k
элементов
определяется следующей формулой:
()
!!
!
kkn
n
C
k
n
=
. (4)
Сначала образуем все возможные упорядоченные подмножества,
содержащие
k
элементов. Их число равно
k
n
C
. Затем из каждого полученного
подмножества перестановкой его элементов получим все упорядоченные
подмножества, которых будет в !
k
раз больше, так как каждое
k
-элементное
множество можно упорядочить !
k
способами. Итак,
k
n
k
n
CkA
!
=
, откуда и
следует формула (4).
Формулу (4) можно записать в другом, более удобном для вычислений
виде. Сократив числитель и знаменатель дроби на
()
!
kn
, получим
()( )( )
!
121
k
knnnn
C
k
n
+
=
Κ
т.е.
число сочетаний из n элементов по k элементо в равно
произведению всех натуральных чисел от n до
1
+
kn включительно,
деленному на
!
k .
Задача 8.
Сколько экзаменационных комиссий, состоящих из 7 членов,
можно образовать из 14 преподавателей?
Решение. Очевидно, столько, сколько существует семиэлементных
подмножеств у четырн адцати элементного множества. По формуле (4)
находим:
()
.3432
1234567
891011121314
!7!714
!14
7
14
=
=
=
C
Задача 9.
В чемпионате страны по футболу (высшая лига) участвуют
18 команд, причем каждые две команды встречаются между собой 2 раза.
Сколько матчей играется в течение сезона?
Решение. В первом круге состоится столько матчей, сколько
существует двухэлементных подмножеств у множества, содержащего 18
элементов, т.е. их число равно
2
18
C
. По формуле (4) получаем
153
!2!16
!18
2
18
=
=
C
.
Во втором круге играется столько же матчей, поэтому в течение сезона
состоится
3062
2
18
=
C
встреч.
Задача
10.
Решить неравенство
xx
CC
10
1
10
2
>
.