Материал: Дискретная математика. Методичка. Кацаран
ГЛАВА 3. КОМБИНАТОРИКА
Настоящая глава состоит из четырех параграфов:
Основные пра-
вила комбинаторики
,
Понятие
k
-выборки
,
Размещения, переста-
новки, сочетания
,
Формула включений и исключений
. Каждый из
этих параграфов содержит основные определения и теоремы по соответ-
ствующей тематике. Приводимые здесь подробные доказательства тео-
рем являются также иллюстрацией методики решения теоретических за-
дач разного уровня, помещенных в конце каждого раздела. Для успеш-
ного овладения материалом по теме
Комбинаторика
читателю ре-
комендуется предварительно ознакомиться с главами
Множества
и
Бинарные отношения
, результаты которых используются в настоя-
щей главе.
Комбинаторика изучает различные комбинации элементов множе-
ства. Все задачи, вопрос в которых начинается со слов
Сколькими
способами
или
Сколько
, относятся к разделу математики, кото-
рый называется
комбинаторикой
.
Итак,
комбинаторика
— раздел математики, изучающий вопрос о
том, сколько различных комбинаций, подчиненных тем или иным усло-
виям, можно составить из конечного числа заданных элементов.
§ 1. Основные правила комбинаторики
Основными способами решения комбинаторных задач являются ме-
тоды, которые мы будем именовать
правило суммы
и
правило про-
изведения
.
Правило суммы
. Правило суммы для двух объектов:
Пусть объ-
ект
a
можно выбрать
m
способами, а объект
b
—
n
способами, и
существует
k
общих способа выбора объектов
a
и
b
, тогда один из
объектов
a
или
b
можно выбрать
(
m
+
n
−
k
)
способами.
Это правило эквивалентно следующему свойству мощности:
|
A
∪
B
|
=
|
A
|
+
|
B
| − |
A
∩
B
|
.
Правило суммы можно сформулировать для произвольного числа
объектов. Для этого достаточно использовать формулу для мощности
объединения конечного числа множеств. Для случая трех множеств фор-
мула имеет вид:
|
A
∪
B
∪
C
|
=
|
A
|
+
|
B
|
+
|
C
| − |
A
∩
B
| − |
A
∩
C
| − |
B
∩
C
|
+
|
A
∩
B
∩
C
|
.
Правило суммы для трех объектов:
Пусть объект
a
можно вы-
брать
n
1
способами, объект
b
—
n
2
способами и объект
c
—
n
3
спо-
собами, и существует
n
12
общих способа выбора одного из объектов
a
26
и
b
,
n
13
общих способа выбора одного из объектов
a
и
c
,
n
23
общих
способа выбора одного из объектов
b
и
c
, а также известно
n
123
общих
способа выбора одного из объектов
a
,
b
и
c
, тогда число всех способов
выбора одного из объектов
a
или
b
или
c
вычисляется по формуле
:
n
1
+
n
2
+
n
3
−
n
12
−
n
13
−
n
23
+
n
123
.
Правило произведения
. Правило произведения для двух объек-
тов:
Пусть объект
a
можно выбрать
m
способами и после каждого
такого выбора объект
b
можно выбрать
n
способами, тогда выбор па-
ры объектов
a
и
b
в указанном порядке можно осуществить
m
·
n
способами
.
Данное правило произведения равносильно утверждению
|
A
×
B
|
=
|
A
||
B
|
(см. главу 1
Множества
).
Правило произведения является следствием теоремы о мощности
прямого произведения конечного числа конечных множеств.
Правило произведения для случая произвольного числа объектов
формулируется следующим образом:
Пусть объект
a
1
можно выбрать
n
1
способами,
a
2
—
n
2
способами, . . . ,
a
k
—
n
k
способами, причем вы-
бор каждого из последующих объектов не зависит от выбора предыду-
щих объектов, тогда общее число полученных таким образом упорядо-
ченных наборов
(
a
1
, a
2
, . . . , a
k
)
можно выбрать
n
1
·
n
2
·
. . . n
k
способами
.
Последнее правило применяется, если требуется выполнить одно за
другим одновременно
k
действий, на одно из которых наложено огра-
ничение.
§ 2. Понятие
k
-выборки
Пусть
A
=
{
a
1
, . . . , a
n
}
— конечное непустое множество. Возможны
два способа выбора
k
элементов из множества
A
: выбор с возвращением
и выбор без возвращения. Опишем их при помощи следующей таблицы.
Номер шага Выбор с возвращением
Выбор без возвращения
1
выбираем
a
i
1
∈
A
выбираем
a
i
1
∈
A
2
выбираем
a
i
2
∈
A
выбираем
a
i
2
∈
A
\ {
a
i
1
}
. . .
. . .
. . .
k
выбираем
a
i
k
∈
A
выбираем
a
i
k
∈
A
\
S
k
−
1
s
=1
{
a
i
s
}
При реализации описанных в таблице процедур мы получаем ком-
бинацию элементов из множества
A
вида
[
a
i
1
, a
i
2
, . . . , a
i
k
]
, которая на-
зывается
k
-выборкой из
n
элементов.
27
В случае
выбора с возвращением
эта комбинация может содер-
жать повторяющиеся элементы и называется
k
-выборкой из
n
эле-
ментов с повторениями
.
При реализации процедуры
выбор без возвращения
получен-
ная комбинация не содержит повторяющихся элементов и называется
r
-выборкой из
n
элементов без повторений.
Выборка называется упорядоченной, если существенным является
не только состав элементов в ней, но и порядок их выбора
.
Две упорядоченные
k
-выборки считаются различными, если они от-
личаются либо составом элементов, либо порядком их расположения. В
неупорядоченных выборках порядок расположения элементов не суще-
ственен, две различные неупорядоченные
k
-выборки имеют разный со-
став элементов.
Элементы упорядоченной выборки заключаются в круглые скобки
(например
(1
,
2)
).
Элементы неупорядоченной выборки без повторений заключаются
в фигурные скобки (например
{
1
,
2
}
), а элементы неупорядоченной вы-
борки с повторениями — в квадратные скобки (например
[1
,
2]
).
Упорядоченные выборки
(3
,
2)
и
(2
,
3)
считаются различными, хотя
и составлены из одних и тех же элементов. Для тех же самых элементов
2
и
3
неупорядоченные выборки
{
3
,
2
}
и
{
2
,
3
}
(или
[3
,
2]
и
[2
,
3]
) считаются одной и той же.
Рассмотрим множество, которое содержит три элемента
A
=
{
1
,
2
,
3
}
.
Составим из элементов этого множества всевозможные
2
-выборки.
Упорядоченные 2-выборки без повторений:
(1
,
2)
,
(2
,
1)
,
(1
,
3)
,
(3
,
1)
,
(2
,
3)
,
(3
,
2)
.
Упорядоченные 2-выборки с повторениями:
(1
,
2)
,
(2
,
1)
,
(1
,
3)
,
(3
,
1)
,
(2
,
3)
,
(3
,
2)
,
(1
,
1)
,
(2
,
2)
,
(3
,
3)
.
Неупорядоченные 2-выборки без повторений:
{
1
,
2
}
,
{
1
,
3
}
,
{
2
,
3
}
.
Неупорядоченные 2-выборки с повторениями:
[1
,
2]
,
[1
,
3]
,
[2
,
3]
,
[1
,
1]
,
[2
,
2]
,
[3
,
3]
.
В следующих параграфах будут даны формулы для подсчета коли-
чества
k
-выборок из
n
элементов.
§ 3. Размещения с повторениями и без повторений.
Перестановки без повторений
Размещениями из
n
элементов по
k
называются упорядоченные
k
-выборки из
n
элементов
.
Размещениями без повторений из
n
элементов по
k
называются
упорядоченные
k
-выборки из
n
элементов без повторений. Их число
28
обозначается
A
k
n
.
Размещениями с повторениями из
n
элементов по
k
называются
упорядоченные
k
-выборки из
n
элементов с повторениями. Их число
обозначается
˜
A
k
n
.
Перестановками из
n
элементов называются размещения без по-
вторений из
n
элементов по
n
. Их число обозначается
P
(
n
)
.
Теорема
.
Имеют место следующие равенства
:
A
k
n
=
n
!
(
n
−
k
)!
,
f
A
k
n
=
n
k
, P
(
n
) =
n
!
(3
.
1)
где
k
! = 1
·
2
·
. . .
·
(
k
−
1)
·
k
,
0! = 1
.
Доказательство. Пусть
A
=
{
a
1
, . . . , a
n
}
— произвольное множе-
ство,
(
a
i
1
, a
i
2
, . . . , a
i
k
)
— упорядоченная
k
-выборка без повторений, со-
ставленная из элементов множества. Она представляет собой набор дли-
ны
k
вида
(
a
i
1
, a
i
2
, . . . , a
i
k
)
, в котором
a
i
1
∈
A, a
i
2
∈
A
\ {
a
i
1
}
, . . . , a
i
k
∈
A
\
k
−
1
[
l
=1
{
a
i
l
}
.
Число таких наборов равно мощности прямого произведения множеств
A
×
(
A
\ {
a
i
1
}
)
×
. . .
×
(
A
\
k
−
1
[
l
=1
{
a
i
l
}
)
.
В силу теоремы о мощности прямого произведения имеем:
A
k
n
=
|
A
×
(
A
\ {
a
i
1
}
)
×
. . .
×
(
A
\
k
−
1
[
l
=1
{
a
i
l
}|
=
=
|
A
||
(
A
\ {
a
i
1
}
)
|
. . .
|
A
\
k
−
1
[
l
=1
{
a
i
l
}|
=
n
(
n
−
1)
...
(
n
−
k
+ 1)
.
Умножим и разделим последнее выражение на
(
n
−
k
)!
и получим первое
равенство из (3.1).
Размещения с повторениями из элементов множества
A
по
k
пред-
ставляют собой упорядоченный набор
(
a
i
1
, a
i
2
, . . . , a
i
k
)
, в котором каж-
дый из элементов
a
i
l
,
l
= 1
, k
может быть выбран
n
способами. В силу
правила произведения указанный набор может быть выбран
n
k
спосо-
бами, что и доказывает второе из равенств (3.1).
Третье получается из первого при
k
=
n
. Теорема доказана.
29
§ 4. Сочетания с повторениями и без повторений
Сочетаниями из
n
элементов по
k
называются неупорядоченные
k
-выборки из
n
элементов
.
Сочетаниями без повторений из
n
элементов по
k
называются
неупорядоченные
k
-выборки из
n
элементов без повторений. Их число
обозначается
C
k
n
.
Сочетаниями с повторениями из
n
элементов по
k
называются
неупорядоченные
k
-выборки из
n
элементов с повторениями. Их число
обозначается
H
k
n
.
Теорема
.
Имеют место следующие равенства
:
C
k
n
=
n
!
k
!(
n
−
k
)!
, H
k
n
=
C
k
n
+
k
−
1
.
(3
.
2)
Доказательство. Прежде чем доказать равенство для
C
k
n
в общем
случае, рассмотрим пример. Пусть
A
=
{∗
,
∨
,
0
}
, тогда выборки
[
∗
,
∨
]
,
[
∨
,
0]
,
[
∗
,
0]
представляют собой сочетания без повторений по 2, состав-
ленные из элементов множества
A
. Из каждого сочетания можно по-
лучить, производя в нем
перестановку
элементов, размещения без
повторений по 2 из элементов множества
A
. Этот процесс изобразим в
виде следующей схемы (см. рис. 13).
Рис.13
На основании вышеизложенного имеем равенство:
A
2
3
=
C
2
3
P
(2)
.
Аналогичная ситуация имеет место в общем случае: чтобы полу-
чить все
A
k
n
размещений, нужно получить всевозможные сочетания из
n
элементов по
k
(их число равно
C
k
n
), затем в каждом из сочетаний
сделать всевозможные
перестановки
. Число перестановок, которые
можно получить из одного сочетания длины
k
, равно
P
(
k
)
. Очевидно,
что из разных сочетаний без повторений не могут получиться одина-
ковые перестановки. Поэтому
A
k
n
=
C
k
n
P
(
k
)
, откуда следует первое из
равенств (3.2).
Перейдем к доказательству второго равенства (3.2). Введем обозна-
чения:
I
k
n
— множество сочетаний с повторениями из чисел
{
1
,
2
, . . . , n
}
30