Материал: Дискретная математика. Методичка. Кацаран
по
k
,
J
k
n
+
k
−
1
— множество сочетаний без повторений из натуральных
чисел
1
,
2
, . . . , n
+
k
−
1
по
k
.
Неупорядоченная
k
-выборка
[
a
i
1
, a
i
2
, . . . , a
i
k
]
однозначно определя-
ется комбинацией из номеров ее элементов
[
i
1
, . . . , i
k
]
∈
I
k
n
. Не ограничи-
вая общности рассуждений, можно считать, что
i
1
≤
i
2
≤
. . .
≤
i
k
. По-
ложим,
j
1
=
i
1
,
j
2
=
i
2
+1
,
j
k
=
i
k
+
k
−
1
, тогда
j
s
∈ {
1
,
2
, . . . , n
+
k
−
1
}
для
∀
s
= 1
, k
и выборка
{
j
1
, j
2
, . . . , j
k
} ∈
J
k
n
+
k
−
1
.
Пусть
{
j
0
1
, j
0
2
, . . . , j
0
k
}
— произвольная комбинация из
J
k
n
+
k
−
1
, так
как она не зависит от порядка расположения элементов, то можно счи-
тать, что
j
0
1
< j
0
2
< . . . < j
0
k
. Положим
i
0
1
=
j
0
1
,
i
0
2
=
j
0
2
−
1
, . . . ,
i
0
k
=
j
0
k
−
k
+ 1
, так как
i
0
l
∈ {
1
, . . . , n
}
для
∀
l
= 1
, k
, следовательно,
[
i
0
1
, . . . , i
0
k
]
∈
I
k
n
.
Мы установили взаимооднозначное соответствие между множества-
ми
I
k
n
и
J
k
n
+
k
−
1
, откуда следует, что их мощности совпадают
|
I
k
n
|
=
|
J
k
n
+
k
−
1
|
,
т. е.
H
k
n
=
C
k
n
+
k
−
1
.
Теорема доказана.
§ 5. Перестановки с повторениями. Подсчет числа беспорядков
Классическая задача комбинаторики о числе разбиений с повторени-
ями формулируется следующим образом:
сколькими способами можно
разбить
n
различных предметов на
k
групп по
n
1
предметов в первой
группе,
n
2
— во второй группе
,
. . .
,
n
k
— в последней группе?
Такие комбинации называются перестановками с повторениями.
Число различных перестановок из
n
1
предметов первого вида,
n
2
предметов второго вида,
. . .
,
n
k
предметов
k
-го вида вычисляется по
формуле:
P
(
n
1
, n
2
, . . . , n
k
) =
(
n
1
+
n
2
+
. . .
+
n
k
)!
n
1
!
n
2
!
. . . n
k
!
.
Действительно, для первой группы можно выбрать
n
1
предметов из
n
=
n
1
+
n
2
+
. . .
+
n
k
имеющихся в наличии
C
n
1
n
способами. Для второй
группы —
n
2
предметов из
(
n
−
n
1
)
оставшихся в наличии
C
n
2
n
−
n
1
спосо-
бами. Для третьей группы —
n
3
предметов из
(
n
−
n
1
−
n
2
)
оставшихся в
наличии
C
n
3
n
−
n
1
−
n
2
способами. Этот процесс продолжается вплоть до по-
следней группы. Общее число разбиений, которое мы будем обозначать
P
(
n
1
, n
2
, . . . , n
k
)
, равно:
P
(
n
1
, n
2
, . . . , n
k
) =
n
!
n
1
!(
n
−
n
1
)!
·
(
n
−
n
1
)!
n
2
!(
n
−
n
1
−
n
2
)!
·
·
(
n
−
n
1
−
n
2
)!
n
3
!(
n
−
n
1
−
n
2
−
n
3
)!
·
. . .
·
(
n
−
n
1
−
. . .
−
n
k
−
1
)!
n
k
!0!
=
n
!
n
1
!
n
2
!
. . . n
k
!
.
31
Таким образом, число разбиений обобщает число сочетаний. Дей-
ствительно, если мы разбиваем
n
предметов на две группы, то
n
1
+
n
2
=
n
, откуда
n
2
=
n
−
n
1
и
P
(
n
1
, n
2
) =
n
!
n
1
!
·
n
2
!
=
n
!
n
1
!
·
(
n
−
n
1
)!
=
C
n
1
n
=
C
n
2
n
.
Рассмотрим еще один вид перестановок
n
предметов —
циклические
перестановки
.
Задача заключается в следующем: рассматриваются
n
предметов,
расположенных не в ряд, а по кругу. В этом случае перестановки счита-
ются одинаковыми, если они получаются при переходе друг в друга при
вращении, т. е. при
циклическом сдвиге
. Число таких перестановок из
различных предметов
e
P
(
n
)
равно:
e
P
(
n
) = (
n
−
1)!
.
Немаловажной является и задача о
подсчете числа беспорядков
,
когда требуется найти число
N
перестановок из цифр
{
1
,
2
, . . . , n
}
, та-
ких, что никакая цифра не остается на своем месте. Число таких пере-
становок находится по формуле:
N
=
n
!
n
X
k
=0
(
−
1)
k
1
k
!
.
§ 6. Свойства сочетаний. Бином Ньютона
При помощи формулы (3.2) посредством алгебраических преобразо-
ваний легко получить следующие свойства сочетаний:
1
. C
n
n
=
C
0
0
;
2
. C
k
n
=
C
n
−
k
n
;
3
. C
k
n
=
C
k
−
1
n
−
1
+
C
k
n
−
1
;
4
. C
k
n
·
C
m
−
k
n
−
k
=
C
k
m
·
C
m
n
,
k
= 1
, n.
Биномом Ньютона называется равенство
(
x
+
a
)
n
=
n
X
j
=0
C
j
n
x
j
a
n
−
j
.
(3
.
3)
Докажем его, пользуясь методом математической индукции. При
n
= 1
имеем очевидное равенство:
x
+
a
=
1
X
j
=0
C
j
1
x
j
a
1
−
j
=
a
+
x.
32
Предположим, что равенство (3.3) имеет место при
n
=
k
и, исходя из
этого предположения, докажем его для случая
n
=
k
+ 1
:
(
x
+
a
)
k
+1
= (
x
+
a
)
k
(
x
+
a
) =
k
X
j
=0
C
j
k
x
j
a
k
−
j
(
x
+
a
) =
=
k
X
j
=0
C
j
k
x
j
+1
a
k
−
j
+
k
X
j
=0
C
j
k
x
j
a
k
+1
−
j
=
=
C
0
k
+1
a
k
+1
+
k
X
i
=1
(
C
i
−
1
k
+
C
i
k
)
x
i
a
k
+1
−
i
+
C
k
+1
k
+1
x
k
+1
a
0
=
=
k
+1
X
i
=0
C
i
k
+1
x
i
a
k
+1
−
i
.
Из равенства (3.3), положив сначала
x
=
a
= 1
, затем
x
= (
−
a
) = 1
,
получим новые свойства сочетаний:
5
.
P
k
j
=0
C
j
k
= 2
k
;
6
.
P
k
j
=0
(
−
1)
j
C
j
k
= 0
.
Так как сочетание без повторений из
n
элементов по
k
представляет
собой
k
-элементное подмножество множества мощности
n
, то величина
P
n
k
=0
C
k
n
равна числу различных подмножеств этого множества. В связи
с этим из свойства 5) сочетаний получаем теорему о мощности булеана
(см. стр. 10).
§ 7. Общий случай формулы включений и исключений
Пусть имеется
N
элементов, каждый из которых может обладать
или не обладать свойствами
α
1
,
α
2
,
. . .
,
α
n
. Через
N
(
α
i
, α
j
, . . . , α
k
)
обозначается количество элементов, обладающих свойствами
α
i
,
α
j
,
. . .
,
α
k
. Если необходимо подчеркнуть, что берутся элементы, заведомо не об-
ладающие некоторым свойством, то это свойство пишется с чертой; на-
пример,
N
(
α
1
, α
2
)
— количество элементов, не обладающих свойством
α
1
и обладающих свойством
α
2
.
Задача состоит в том, чтобы найти
N
(
α
1
, . . . , α
n
)
— количество эле-
ментов, не обладающих ни одним из свойств
α
1
,
α
2
,
. . .
,
α
n
.
Для решения этой задачи в случае трех свойств воспользуемся сле-
дующим выражением для мощности объединения множеств
A
,
B
и
C
:
|
A
∪
B
∪
C
|
=
|
A
|
+
|
B
|
+
|
C
|−|
A
∩
B
|−|
A
∩
C
|−|
B
∩
C
|
+
|
A
∩
B
∩
C
|
.
(3
.
4)
33
Обозначим через
A
,
B
,
C
множества элементов, обладающих свой-
ствами
α
1
,
α
2
,
α
3
соответственно, тогда
|
A
|
=
N
(
α
1
)
,
|
B
|
=
N
(
α
2
)
,
|
C
|
=
N
(
α
3
)
,
|
A
∩
B
|
=
N
(
α
1
, α
2
)
,
|
A
∩
C
|
=
N
(
α
1
, α
3
)
,
|
B
∩
C
|
=
N
(
α
2
, α
3
)
,
|
A
∩
B
∩
C
|
=
N
(
α
1
, α
2
, α
3
)
.
На приведенном рисунке множество элементов, изображенное в виде
прямоугольника, имеет мощность
N
. Множество элементов, не облада-
ющих ни одним из свойств (его мощность равна
N
( ¯
α
1
,
¯
α
2
,
¯
α
3
)
), пред-
ставлено заштрихованной частью прямоугольника. Исходя из того, что
N
( ¯
α
1
,
¯
α
2
,
¯
α
3
) =
N
− |
A
∪
B
∪
C
|
и используя равенство (3.4), получим
формулу включений и исключений для случая трех свойств:
N
( ¯
α
1
,
¯
α
2
,
¯
α
3
) =
N
−
N
(
α
1
)
−
N
(
α
2
)
−
N
(
α
3
)+
+
N
(
α
1
, α
2
) +
N
(
α
1
, α
3
) +
N
(
α
2
, α
3
)
−
N
(
α
1
, α
2
, α
3
)
.
Теорема
.
При сделанных ранее предположениях и обозначениях
формула включений и исключений для случая
n
свойств имеет вид
:
N
( ¯
α
1
, . . . ,
¯
α
n
) =
N
−
n
X
i
=1
N
(
α
i
) +
X
1
≤
i<j
≤
n
N
(
α
i
, α
j
) +
. . .
. . .
+ (
−
1)
s
X
1
≤
i
1
<...<i
s
≤
n
N
(
α
i
1
, . . . , α
i
s
) +
. . .
+ (
−
1)
n
N
(
α
1
, . . . , α
n
)
.
(3
.
5)
Доказательство. Следует отметить, что алгебраическая сумма
X
1
≤
i
1
<...<i
s
≤
n
N
(
α
i
1
, . . . , α
i
s
)
в (3.5) распространена на все сочетания свойств из множества
α
1
, . . . , α
n
по
s
, причем, знак плюс ставится, если число
s
учитываемых свойств
четно, и знак минус, если это число нечетно.
34
Доказательство равенства (3.5) будем проводить методом матема-
тической индукции по числу
n
свойств. В случае
n
= 1
равенство (3.5)
приобретает вид:
N
(
α
1
) =
N
−
N
(
α
1
)
. Оно верно, так как каждый эле-
мент либо обладает свойством
α
1
, либо не обладает. Далее пусть
N
(
α
1
, . . . , α
n
−
1
) =
N
−
N
(
α
1
)
−
. . .
−
N
(
α
n
−
1
) +
N
(
α
1
, α
2
) +
. . .
. . .
+
N
(
α
n
−
2
, α
n
−
1
)
−
N
(
α
1
, α
2
, α
3
)
−
. . .
−
N
(
α
n
−
3
, α
n
−
2
, α
n
−
1
) +
. . .
. . .
+ (
−
1)
n
−
1
N
(
α
1
, α
2
, . . . , α
n
−
1
)
.
(3
.
6)
Это равенство верно для любого конечного множества элементов,
в частности для множества элементов, обладающих свойством
α
n
. Об-
щее количество этих элементов равно
N
(
α
n
)
. Число
N
(
α
1
, . . . , α
n
−
1
, α
n
)
элементов, не обладающих
(
n
−
1)
свойством на множестве элементов,
обладающих свойством
α
n
, вычисляется по формуле, которая следует
из (3.6):
N
(
α
1
, . . . , α
n
−
1
, α
n
) =
N
(
α
n
)
−
N
(
α
1
, α
n
)
−
. . .
−
N
(
α
n
−
1
, α
n
)+
+
N
(
α
1
, α
2
, α
n
)+
. . .
+
N
(
α
n
−
2
, α
n
−
1
, α
n
)+
. . .
−
(
−
1)
n
−
1
N
(
α
1
, . . . , α
n
−
1
, α
n
)
.
В каждом слагаемом здесь присутствует
α
n
. Вычтем это равенство
из (3.6). В левой части результата получим выражение:
N
(
α
1
, . . . , α
n
−
1
)
−
N
(
α
1
, . . . , α
n
−
1
, α
n
) =
N
(
α
1
, . . . , α
n
−
1
, α
n
)
,
а в правой части, сгруппировав слагаемые с одинаковым количеством
свойств, получим правую часть равенства (3.5). Теорема доказана.
§ 8. Частный случай формулы включений и исключений
Предположим, что число
N
(
α
i
1
, . . . , α
i
s
)
элементов, обладающих свой-
ствами
α
i
1
, . . . , α
i
s
, не зависит от характера свойств, а зависит от их
числа, т. е. пусть
N
(
α
i
) =
N
(1)
,
∀
i
∈ {
1
, . . . , n
}
, N
(
α
i
, α
j
) =
N
(2)
,
∀
i, j
∈ {
1
, . . . , n
}
,
N
(
α
i
1
, . . . , α
i
s
) =
N
(
s
)
,
∀
i
1
, . . . i
s
∈ {
1
, . . . , n
}
.
Используя введенные обозначения, получим следующие выражения
для сумм в (3.5):
n
X
i
=1
N
(
α
i
) =
C
1
n
N
(1)
,
X
1
≤
i<j
≤
n
N
(
α
i
, α
j
) =
C
2
n
N
(2)
,
X
1
≤
i
1
<...<i
s
≤
n
N
(
α
i
1
, . . . α
i
s
) =
C
s
n
N
(
s
)
, s
= 1
, . . . , n.
35