ВУЗ:
Составители:
Рубрика:
подразделение на дежурство. Следовательно, эти комбинации – сочетания, но не обычные, а с повторе-
ниями.
Определение. Сочетанием с повторениями из т элементов по k элементов (или короче: сочетани-
ем с повторениями из т по k) называется множество, содержащее k элементов, причем каждый элемент
принадлежит к одному из т типов.
Число всех вышеупомянутых сочетаний с повторениями из т по k обозначается
k
т
С (обратите вни-
мание на отличие от обозначения числа сочетаний из n по k – черта сверху).
Пример. Напишем все сочетания с повторениями из трех элементов А, В, С по 3. Сколько их?
Вот они: ААА ВВВ ССС
АВВ ВСС
АСС ВВС
ААВ
ААС
АСВ
Их 10 штук, т.е. 10
3
3
=С .
Теорема. Число сочетаний с повторениями из т по k равно:
)!1(!
)!1(
)1,(
−
−+
=−=
mk
mk
mkPС
k
т
.
Доказательство. Каждое сочетание с повторениями полностью определяется, если указать, сколько
элементов каждого из т типов в него входит. Поставим в соответствие каждому сочетанию с повторения-
ми последовательность нулей и единиц, составленную по такому правилу: напишем подряд столько еди-
ниц, сколько элементов первого типа входит в сочетание с повторениями, далее поставим нуль, и после
него напишем столько единиц, сколько элементов второго типа содержит это сочетание и т.д.
Таким образом, каждому сочетанию с повторениями из т по k соответствует последовательность из
k единиц и т – 1 нулей, и наоборот, по каждой такой последовательности однозначно восстанавливается
сочетание с повторениями из т по k. Поэтому число сочетаний с повторениями из т по k равно числу
перестановок с повторениями k единиц и т – 1 нулей, т.е.
)!1(!
)!1(
)1,(
−
−+
=−=
mk
mk
mkPС
k
т
.
Теорема доказана.
Следствие.
k
km
m
km
k
m
CCС
1
1
1 −+
−
−+
==
.
Доказательство. В силу формулы
)!(!
!
knk
n
C
k
n
−
=
, доказательство очевидно. Следствие доказано.
Пример. Сколько можно сделать костей домино, используя числа 0, 1, 2, …, 9 (а не 0, 1, 2, …, 6 как
обычно).
Решение. Кости «нового» домино можно рассматривать как сочетания с повторениями из 10 по 2.
Следовательно, число костей такого домино было бы:
55115
!2 !9
!11
9
11
110
110
2
10
=⋅====
−
+
ССС .
3.6 Задачи по теме «Элементы комбинаторики»
Вычислить:
1 a)
!5
!5!6
−
; б)
!8!7
!6
+
.
2 а)
!16!5
!20
; б)
!18!19
!20!21
+
+
.
3 а)
7
10
4
7
5
76
)(
A
CCP +
; б)
2
3
1
3
+
−
+
nn
n
n
CP
A
.
Найти n, если:
Страницы
- « первая
- ‹ предыдущая
- …
- 22
- 23
- 24
- 25
- 26
- …
- следующая ›
- последняя »
