Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2023
Просмотров: 558
Скачиваний: 6
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
158
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Два подпространства V
1
и V
2
векторного пространства V
m
(Z
2
) называют- ся ортогональными (обозначается V
1
⊥V
2
), если для любых векторов a ∈ V
1
и b ∈ V
2
их внутреннее произведение (a, b) равно 0.
Заметим, что по теореме 4.12.3 любой цикл C с любым разрезом K име- ет четное число общих ребер, т. е. для соответствующих векторов a и b их внутреннее произведение (a, b) равно нулю. В частности, для любых векто- ров a
i
∈ B
C
и b
j
∈ B
K
справедливо (a, b) = 0. Так как множества B
C
и B
K
образуют базисы подпространств V
Γ
и V
K
, то V
Γ
⊥V
K
Отметим также, что при умножении матрицы фундаментальных цик- лов C на транспонированную матрицу фундаментальных разрезов K
T
в поле Z
2
строка a
i
умножается на столбец b
j
по правилу внутреннего про- изведения и (a
i
, b
j
) = 0. Это означает, что C · K
T
= 0, а также K · C
T
= 0.
Упражнение.Проверить, что для матриц C и K из примеров 4.11.1
и 4.12.1 справедливо C · K
T
= 0.
§ 4.14.
Раскраски графов
Пусть G = hM; Ri — неорграф без петель. Раскраской (вершин) графа G
называется такое задание цветов вершинам G, что если [a, b] — ребро, то вер- шины a и b имеют различные цвета. Хроматическим числом χ(G) графа G
называется минимальное число цветов, требующееся для раскраски G.
Пример 4.14.1. Так как в полном графе K
n
любые две различные вер- шины связаны ребром, то χ(K
n
) = n. ¤
Многие практические задачи сводятся к построению раскрасок графов.
Пример 4.14.2. 1. Рассмотрим задачу составления расписания. Пред- положим, что нужно прочесть несколько лекций за кратчайшее время. Чте- ние каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно (например, их читает один и тот же лек- тор). Построим граф G, вершины которого биективно соответствуют лекци- ям и две вершины смежны тогда и только тогда, когда соответствующие им лекции нельзя читать одновременно. Очевидно, что любая раскраска этого графа определяет допустимое расписание: лекции, соответствующие верши- нам одного цвета, могут читаться одновременно. Напротив, любое допусти- мое расписание определяет раскраску графа G. Оптимальные расписания
4.14. РАСКРАСКИ ГРАФОВ
159
соответствуют раскраскам с минимальным числом цветов, а число часов,
необходимое для прочтения всех лекций, равно χ(G).
2. Рассмотрим граф G, вершины которого — страны, а ребра соединяют страны, имеющие общую границу. Числу χ(G) соответствует наименьшее число красок, необходимых для раскраски карты так, чтобы никакие две соседние страны не были окрашены в один цвет. ¤
Существуют и практические задачи, связанные с раскраской ребер в муль- тиграфе.
Раскраска ребер в мультиграфе G может быть определена с помощью раскраски вершин так называемого реберного мультиграфа L(G). Для про- извольного неориентированного мультиграфа G = hM, U, P i реберным муль-
тиграфом L(G) называется тройка hU, M, P
0
i, где P
0
⊆ U × M × U, и выпол- няется (u, a, v) ∈ P
0
тогда и только тогда, когда в мультиграфе G вершина a
является концом ребер u и v. Раскраской ребер мультиграфа G называется раскраска вершин мультиграфа L(G).
Пример 4.14.3. Проводится монтаж аппаратуры. Чтобы не перепутать проводники, необходимо их окрасить таким образом, чтобы два проводни- ка, идущие к одной плате, имели разные цвета. В этом случае вершинами являются платы, а ребрами — проводники. ¤
Неорграф G называется бихроматическим, если χ(G) = 2. Неорграф
G = hM; Ri называется двудольным, если множество всех ребер графа G
образует разрез графа G, т. е. для некоторого разбиения множества вершин
{M
1
, M
2
} концы любого ребра принадлежат разным частям разбиения.
Теорема 4.14.1. Пусть G — неорграф без петель, имеющий хотя бы
одно ребро. Тогда следующие условия эквивалентны:
1) G — бихроматический граф;
2) G — двудольный граф;
3) G не содержит циклов нечетной длины. ¤
Следствие 4.14.2. Если G — лес, то χ(G) 6 2. ¤
Оценим хроматическое число графа G через его параметры. Обозначим через deg(G) максимальную степень вершин графа G.
Теорема 4.14.3. Для любого неорграфа G без петель выполняется нера-
венство χ(G) 6 deg(G) + 1. ¤
160
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Рассмотрим простой алгоритм построения раскраски, который во многих случаях приводит к раскраскам, близким к минимальным.
Алгоритм последовательной раскраски.
1. Произвольная вершина a
1
графа G принимает цвет 1.
2. Если вершины a
1
, . . . , a
i
раскрашены l цветами 1, 2, . . . , l, l 6 i, то новой произвольно взятой вершине a
i+1
припишем минимальный цвет, не исполь- зованный при раскраске вершин из множества {a
j
| ρ(a
i+1
, a
j
) = 1, j < i}. ¤
Для некоторых классов графов последовательная раскраска является ми- нимальной. В общем случае это не так.
§ 4.15.
Планарные графы
Неорграф G называется планарным, если его можно изобразить на плос- кости так, что никакие два ребра не будут иметь общих точек, кроме, может быть, общего конца этих ребер. Такое изображение графа на плоскости на- зывается плоским. Таким образом, если граф имеет плоское изображение,
то он является планарным.
Пример 4.15.1. Граф K
4
(рис. 4.48а) планарен, поскольку может быть изображен, как показано на рис. 4.48б. ¤
Граф, описанный в примере 4.14.2, п. 2, является планарным. Также пла- нарным является граф, вершины которого — отверстия печатной платы, а ребра — проводники печатной платы, соединяющие отверстия.
Рассмотрим операцию подразбиения ребра в графе G = hM; Ri. После подразбиения ребра [a, b] ⊆ R получается граф G
0
= hM
0
; R
0
i, где M
0
= M∪
∪{ab}, R
0
= (R\[a, b])∪[a, ab]∪[ab, b], т. е. ребро [a, b] заменяется на (a, b)-цепь длины два. Два графа называются гомеоморфными, если их можно получить из одного графа с помощью последовательности подразбиений ребер.
•
•
•
•
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
•
•
•
•
¢
¢
¢
¢
¢
¢
¡
¡
¡
A
A
A
A
A
A
@
@
@
а
б
Рис. 4.48
4.15. ПЛАНАРНЫЕ ГРАФЫ
161
•
•
•
•
•
•
•
•
•
•
•
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
@
@
@
@
@
@
©©
©©
©©
©©
©©
©
©
HH
HH
HH
HH
HH
H
H
K
5
K
3,3
Рис. 4.49
Не всякий неорграф является планарным. Критерий планарности опи- сывает
Теорема 4.15.1 (теорема Понтрягина—Куратовского). Неорграф G пла-
нарен тогда и только тогда, когда G не содержит часть, гомеоморфную K
5
или K
3,3
(рис. 4.49). ¤
Эквивалентная форма критерия планарности описана в следующей тео- реме.
Теорема 4.15.2. Тогда и только тогда неорграф G планарен, когда G не
содержит частей, стягиваемых (т. е. получаемых последовательностью
отождествлений вершин, связанных ребрами) к графу K
5
или K
3,3
(рис.
4.49). ¤
Вместе с тем трехмерного евклидова пространства оказывается доста- точно для изображения любого конечного и счетного графа без пересечения дуг вне их концов.
Теорема 4.15.3. Любой граф, состоящий не более чем из 2
ω
вершин,
может быть изображен в пространстве R
3
без пересечения дуг вне их
концов.
Доказательство. Пусть G = hM; Ri — граф, для которого |M| 6 2
ω
Тогда имеем |R| 6 2
ω
. Расположим все точки графа G на некоторой пря- мой l и каждой дуге из R разнозначно сопоставим плоскость, содержащую прямую l. Искомое изображение графа G получается после проведения всех дуг в соответствующих плоскостях. ¤
Известна оценка хроматического числа планарных графов.
162
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Теорема 4.15.4 (теорема о четырех красках). Если G — планарный граф,
то χ(G) 6 4. ¤
При исследовании принципиальной электрической схемы радиоэлектрон- ного устройства с точки зрения возможности ее реализации с помощью пе- чатного монтажа или монтажа на слоях микросхемы важно знать ответ на следующие вопросы:
1 ... 13 14 15 16 17 18 19 20 ... 29
1) является ли граф, соответствующий рассматриваемой принципиаль- ной схеме, планарным?
2) если граф планарен, то как получить его изображение без пересечения ребер?
На первый вопрос принципиальный ответ дает теорема Понтрягина—
Куратовского, а методы получения плоских изображений планарных графов можно найти в книге Б. Н. Деньдобренько, А. С. Малика [7].
Если граф G непланарен, то для его геометрической реализации удаля- ют отдельные ребра (переносят на другую плоскость). Минимальное число ребер, которое необходимо удалить из графа для получения его плоского изображения, называется числом планарности графа G. При вынесении этих ребер на вторую плоскость получают часть графа, которая также может оказаться неплоской. Тогда вновь решают задачу вынесения отдельных ре- бер на следующую плоскость и т. д. Минимальное число плоскостей m, при котором граф G разбивается на плоские части G
1
, G
2
, . . ., G
m
(разбиение ведется по множеству ребер), называется толщиной графа G.
Таким образом, толщина планарного графа равна 1.
Пример 4.15.2. Каждый из графов K
5
и K
3,3
имеет толщину 2. ¤
Задачи и упражнения
1. Представить граф (рис. 4.50) в аналитической и матричной формах, списком дуг и структурой смежности.
2. Составить матрицу инцидентности для мультиграфа, изображенного на рис. 4.51.
3. Найти все неизоморфные подграфы и части графа K
3 4. Представить в геометрической и матричной формах графы G
1
∪ G
2
,
G
1
∩ G
2
, G
1
⊕ G
2
(рис. 4.52).
5. Для графов G
1
и G
2
из предыдущей задачи найти G
1
× G
2
, G
1
[G
2
] и G
2
[G
1
].
ЗАДАЧИ И УПРАЖНЕНИЯ
163
•
•
•
•
•
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
R ?
¾
-
±°
²¯
•
•
•
•
¡
¡
¡
¡
¡
¡
µ
¸
?
Y
K
*
¼
g
±°
²¯
Рис. 4.50
Рис. 4.51
6. С помощью матрицы смежности графа (рис. 4.53) найти его матрицы дости- жимости, контрдостижимости и сильных компонент.
7. Найти матрицу расстояний, диаметр, радиус, центральные и периферийные вершины графа, изображенного на рис. 4.54.
8. Найти все кратчайшие маршруты из вершины 2 для взвешенного графа
(рис. 4.55).
9. Доказать, что в любом конечном бесконтурном графе существуют вершины с нулевой полустепенью исхода и с нулевой полустепенью захода.
10. Проверить на эйлеровость и найти минимальное множество покрывающих цепей:
а) графа K
5
; б) графа K
3,3
; в) графа, изображенного на рис. 4.56.
•
•
•
¢
¢
¢
¢¢¸
A
A
A
AAU
1 2
3
G
1
•
•
•
•
¾
A
A
A
AAU
¢
¢
¢
¢
¢®
1 2
3 4
G
2
•
•
•
•
@
@
@
I
¡
¡
¡
µ
?
@
@
@
R
h
1 2
3 4
Рис. 4.52
Рис. 4.53
•
•
•
•
•
•
•
¡
¡
¡
¡
@
@
@
@
@
@
•
•
•
•
•
½
½
½
½
>
Z
Z
Z
Z
?
-
@
@
@
@
@
@
R
¡
¡
¡
¡
¡
¡
µ
¾
6
K
®
1 2
3 5
4
(3)
(4)
(6)
(2)
(1)
(2)
(2)
(3)
(−2)
(−5)
Рис. 4.54
Рис. 4.55
164
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
•
•
•
•
•
•
•
¶
¶
¶
¶
¶
¶
³³
³³
³³
³³
´
´
´
´
PPP
PPP
PP
Q
Q
Q
Q
E
E
E
E
E
E
E
E
¢
¢
¢
¢
¢
¢¡
¡
¡
•
•
•
•
•
•
•
¶
¶
¶
¶
¶
¶
@
@
@
´
´
´
´
@
@
@
@
@
@
E
E
E
E
E
E
E
E
S
S
S
S
S
S
¡
¡
¡
¡
¡
¡
¢
¢
¢
¢
¢
¢
(2)
(2)
(3)
(3)
(1)
(2)
(2)
(4)
(3)
(1)
Рис. 4.56
Рис. 4.57
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
@
@
R
¡
¡
ª
¡
¡
ª ?
?
¡
¡
ª
@
@
R
@
@
R
@
@
R
@
@
R
¡
¡
ª
¡
¡
ª
¡
¡
ª
¡
¡
ª
@
@
R
¡
¡
ª
1 2
3 4
5 6
7 8
9 10 11 12 13 14 15 16
•
•
•
•
•
•
•
J
J
JJ
1 2
3 4
5 9
7 8
6 10
Рис. 4.58
Рис. 4.59
11. Построить все неизоморфные трех-, четырех- и пятивершинные деревья.
12. Найти остов минимального веса взвешенного графа (рис. 4.57).
13. Найти упорядоченный лес, соответствующий бинарному дереву, изображен- ному на рис. 4.58.
14. Найти матрицы фундаментальных циклов и фундаментальных разрезов гра- фа (рис. 4.59).
15. Найти хроматическое число графа (рис. 4.60).
16. Найти толщину графа (рис. 4.61).
•
•
•
•
•
•
•
¡
¡
¡
@
@
@
@
@
@
@
@
@
S
S
S
S
S
S
¦
¦
¦
¦
¦
¦
¦
¦
•
•
•
•
•
•
¡
¡
¡
¡
@
@
@
@
HH
HH
HH
H
HH
HH
HH
H
©©
©©
©©
©
©©
©©
©©
©
Рис. 4.60
Рис. 4.61
Глава 5
КОМБИНАТОРИКА
Комбинаторика — раздел математики, посвященный решению задач вы- бора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множе- ства, называемой комбинаторной конфигурацией. Поэтому целями комби- наторного анализа являются изучение комбинаторных конфигураций, алго- ритмов их построения, оптимизация таких алгоритмов, а также решение за- дач перечисления. Простейшими примерами комбинаторных конфигураций являются перестановки, размещения, сочетания и разбиения. При подсчете комбинаторных конфигураций используются правила суммы, произведения и степени, сформулированные в § 1.4.
§ 5.1.
Перестановки и подстановки
Пусть дано множество M = {a
1
, a
2
, . . . , a
n
}. Перестановкой элементов множества M называется любой кортеж (a
i
1
, a
i
2
, . . . , a
i
n
), состоящий из n
различных элементов множества M.
Перестановки отличаются друг от друга только порядком входящих в них элементов. Покажем, что число P
n
всех перестановок множества M
равно n!. Действительно, на первое место в кортеже можно подставить лю- бой из n элементов, на второе место — любой из n − 1 оставшихся и т. д. Для последнего места остается единственный элемент. Поэтому получаем всего
n(n − 1)(n − 2) . . . 2 · 1 = n! перестановок.
166
Глава 5. КОМБИНАТОРИКА
Пример 5.1.1. 1. Расставить на полке 10 книг можно P
10
= 10! =
= 3 628 800 различными способами.
2. Список студентов группы, состоящей из 25 человек, можно составить
P
25
= 25! способами. ¤
Напомним, что биекция σ: M ↔ M называется подстановкой множе- ства M. Пусть σ — подстановка множества M = {1, 2, . . . , n}. Тогда
σ(k) = s
k
, где 1 6 s
k
6 n, k = 1, 2, . . . , n, {s
1
, s
2
, . . . , s
n
} = {1, 2, . . . , n},
и поэтому подстановку σ можно представить в виде матрицы, состоящей из двух строк:
[σ]
µ
1 2 . . . n
s
1
s
2
. . . s
n
¶
.
Ясно, что если в матрице [σ] переставить столбцы, то полученная матрица будет также определять подстановку σ. Множество всех подстановок мно- жества {1, 2, . . . , n} обозначается через S
n
. Для подстановок σ, τ ∈ S
n
можно определить произведение σ · τ как произведение двух функций. Зная матри- цы подстановок
[σ] =
µ
1 2 . . . n
s
1
s
2
. . . s
n
¶
и [τ ], переставив столбцы матрицы [τ ] так, чтобы ее первая строка совпала со второй строкой матрицы [σ]:
µ
s
1
s
2
. . . s
n
t
1
t
2
. . . t
n
¶
,
получаем
[στ ] =
µ
1 2 . . . n
s
1
s
2
. . . s
n
¶ µ
s
1
s
2
. . . s
n
t
1
t
2
. . . t
n
¶
=
µ
1 2 . . . n
t
1
t
2
. . . t
n
¶
.
Пример 5.1.2. Если [σ] =
µ
1 2 3 4 2 1 4 3
¶
, [τ ] =
µ
1 2 3 4 3 1 4 2
¶
, то
[στ ] =
µ
1 2 3 4 2 1 4 3
¶ µ
2 1 4 3 1 3 2 4
¶
=
µ
1 2 3 4 1 3 2 4
¶
. ¤
Теорема 5.1.1. Алгебра hS
n
; ·i является группой. При n > 3 она неком-
мутативна.
5.1. ПЕРЕСТАНОВКИ И ПОДСТАНОВКИ
167
Доказательство. Операция · ассоциативна как операция произведе- ния функций. Легко проверяется, что существует единичная подстановка ε
с матрицей [ε] =
µ
1 2 . . . n
1 2 . . . n
¶
и для любой подстановки σ с матрицей
[σ] =
µ
1 2 . . . n
s
1
s
2
. . . s
n
¶
существует обратная подстановка σ
−1
, соответству- ющая матрице
µ
s
1
s
2
. . . s
n
1 2 . . . n
¶
Если n > 3, то рассмотрим подстановки σ и τ
с матрицами
[σ] =
µ
1 2 3 4 . . . n
2 1 3 4 . . . n
¶
и [τ ] =
µ
1 2 3 4 . . . n
3 2 1 4 . . . n
¶
Имеем [στ ] =
µ
1 2 3 4 . . . n
2 3 1 4 . . . n
¶
, [τ σ] =
µ
1 2 3 4 . . . n
3 1 2 4 . . . n
¶
, т. е.
στ 6= τ σ. Таким образом, группа hS
n
; ·i некоммутативна. ¤
Группа hS
n
; ·i называется симметрической группой степени n. Число элементов этой группы |S
n
| равно P
n
n!.
Подстановка σ называется циклом длины r, если матрицу [σ] переста- новкой столбцов можно привести к виду
µ
s
1
s
2
s
3
. . . s
r−1
s
r
s
r+1
. . . s
n
s
2
s
3
s
4
. . .
s
r
s
1
s
r+1
. . . s
n
¶
.
Очевидно, что в этом случае σ задает биекцию, в которой s
1
7→ s
2
,
s
2
7→ s
3
, . . ., s
r
7→ s
1
, а остальные элементы неподвижны. Описанный цикл σ
обозначается через (s
1
s
2
. . . s
r
).
Пример 5.1.3. Подстановка с матрицей
µ
1 2 3 4 5 6 1 5 6 4 3 2
¶
является циклом (2 5 3 6), а подстановка с матрицей
µ
1 2 3 4 5 6 4 5 2 1 6 3
¶
циклом не яв- ляется, так как из нее можно выделить два цикла (1 4) и (2 5 6 3). ¤
Циклы (s
1
s
2
. . . s
r
) и (t
1
t
2
. . . t
p
) называются независимыми, если
{s
1
, s
2
, . . . , s
r
} ∩ {t
1
, t
2
, . . . , t
p
} = ∅.
Теорема 5.1.2. Каждую подстановку можно однозначно, с точностью
до порядка сомножителей, представить в виде произведения независимых
циклов. ¤
168
Глава 5. КОМБИНАТОРИКА
В примере 5.1.3 имеем
µ
1 2 3 4 5 6 1 5 6 4 3 2
¶
= (2 5 3 6) и
µ
1 2 3 4 5 6 4 5 2 1 6 3
¶
= (1 4)(2 5 6 3).
Двухэлементный цикл (i j) называется транспозицией. При транспози- ции i-й и j-й элементы меняются местами, а остальные сохраняют свое по- ложение.
Теорема 5.1.3. Каждая подстановка есть произведение транспозиций.
Доказательство. По теореме 5.1.2 достаточно установить, что любой цикл (s
1
s
2
. . . s
r
) можно представить в виде произведения транспозиций,
но легко проверяется, что (s
1
s
2
. . . s
r
) = (s
1
s
2
)(s
1
s
3
) . . . (s
1
s
r
). ¤
Пример 5.1.4. (1 2 3 4) = (1 2)(1 3)(1 4). ¤
§ 5.2.
Размещения и сочетания
Пусть M — множество, состоящее из n элементов, m 6 n. Размещением
из n элементов по m или упорядоченной (n, m)-выборкой, называется любой кортеж (a
i
1
, a
i
2
, . . . , a
i
m
), состоящий из m попарно различных элементов мно- жества M. Размещение можно рассматривать как разнозначную функцию
f : {1, 2, . . . , m} → M, для которой f (j) = a
i
j
Пример 5.2.1. Для множества M = {a, b, c} пары (a, b) и (b, a) являются размещениями из 3 по 2, тройка (a, c, b) — размещением из 3 по 3, а тройка
(b, a, b) размещения не образует. ¤
Число размещений из n по m обозначается через A
m
n
или P (n, m). Пока- жем, что
A
m
n
=
n!
(n − m)!
= n(n − 1) . . . (n − m + 1)
(5.1)
(напомним, что 0! = 1). Действительно, размещение m элементов мож- но представить как заполнение некоторых m позиций элементами множе- ства M. При этом первую позицию можно заполнить n различными спосо- бами. После того как 1-я позиция заполнена, элемент для заполнения 2-й позиции можно выбрать (n − 1) способами. Если продолжить этот процесс,
5.2. РАЗМЕЩЕНИЯ И СОЧЕТАНИЯ
169
то после заполнения позиций с 1-й по (m − 1)-ю будем иметь (n − m + 1) спо- собов заполнения последней, m-й позиции. Перемножая эти числа, получаем формулу (5.1).
Пример 5.2.2. Из десяти различных книг произвольным образом бе- рутся и ставятся на полку одна за другой 3 книги. Имеется A
3 10
вариантов расстановок, где A
3 10
=
10!
7!
= 10 · 9 · 8 = 720. ¤
Cочетанием из n элементов по m или неупорядоченной (n, m)-выборкой
называется любое подмножество множества M, состоящее из m элементов.
Пример 5.2.3. Если M = {a, b, c}, то {a, b}, {a, c}, {b, c} — все сочетания из 3 по 2. ¤
Число сочетаний из n по m обозначается через C
m
n
,
¡
n
m
¢
или C(n, m).
Если объединить размещения из n элементов по m, состоящие из од- них и тех же элементов (не учитывая порядка их расположения), в клас- сы эквивалентности, то можно установить биекцию ϕ между сочетаниями и полученными классами по следующему правилу: ϕ({a
i
1
, a
i
2
, . . . , a
i
m
})
{(b
1
, b
2
, . . . , b
m
) | {b
1
, b
2
, . . . , b
m
} = {a
i
1
, a
i
2
, . . . , a
i
m
}}. Так как из каждого сочетания C можно получить m! размещений (упорядочивая m! способами элементы из множества C по числу перестановок этого множества), то каж- дый класс эквивалентности содержит m! размещений и, значит, A
m
n
= m!·C
m
n
,
т. е. C
m
n
=
A
m
n
m!
. Таким образом,
C
m
n
=
n!
(n − m)! m!
.
Пример 5.2.4. Из десяти чисел четыре можно выбрать C
4 10
=
10!
6!4!
=
=
7·8·9·10 4!
=
7·8·9·10 1·2·3·4
= 210 способами. ¤
Число C
m
n
обладает следующими свойствами:
1) C
m
n
= C
n−m
n
;
2) C
m
n
+ C
m+1
n
= C
m+1
n+1
(правило Паскаля);
3) (a + b)
n
=
n
P
m=0
C
m
n
a
m
b
n−m
для любых a, b ∈ R, n ∈ ω (бином Ньютона).
В силу последнего свойства числа C
m
n
называются биномиальными коэф-
фициентами.
Пример 5.2.5. Из свойства 3 следует, что 2
n
=
n
P
m=0
C
m
n
. Действительно,
2
n
= (1 + 1)
n
=
n
P
m=0
C
m
n
1
m
1
n−m
=
n
P
m=0
C
m
n
. ¤
170
Глава 5. КОМБИНАТОРИКА
§ 5.3.
Размещения и сочетания с повторением
Размещением с повторением из n элементов по m или упорядоченной
(n, m)-выборкой с возвращениями называется любой кортеж (a
1
, a
2
, . . . , a
m
)
элементов множества M, для которого |M| = n.
Поскольку в кортеж (a
1
, a
2
, . . . , a
m
) на каждое место может претендовать любой из n элементов множества M, число размещений с повторениями
ˆ
P (n, m) равно n · n · . . . · n
|
{z
}
m раз
= n
m
:
ˆ
P (n, m) = n
m
.
Пример 5.3.1. Из цифр 1, 2, 3, 4 можно составить ˆ
P (4, 3) = 4 3
= 64
трехзначных числа. ¤
Определим отношение эквивалентности на множестве размещений с по- вторениями из n по m:
(a
1
, a
2
, . . . , a
m
) ∼ (b
1
, b
2
, . . . , b
m
) ⇔ для любого c ∈ M число элементов a
i
,
равных c, совпадает с числом элементов b
i
, равных c.
Сочетанием с повторением из n элементов по m или неупорядоченной
(n, m)-выборкой с возвращениями называется любой класс эквивалентности по отношению ∼ множества размещений с повторениями из n элементов по
m. Другими словами, сочетания с повторениями суть множества, которые состоят из элементов, выбранных m раз из множества M, причем один и тот же элемент допускается выбирать повторно.
Число сочетаний с повторениями из n элементов по m обозначается через ˆ
C(n, m) и вычисляется по формуле
ˆ
C(n, m) = C
m
n+m−1
=
(n + m − 1)!
m!(n − 1)!
.
Пример 5.3.2. Число различных бросаний двух одинаковых кубиков равно ˆ
C(6, 2) = C
2 7
= 21. ¤
§ 5.4.
Разбиения
Пусть M — множество мощности n, {M
1
, M
2
, . . . , M
k
} — разбиение мно- жества M на k подмножеств, |M
i
| = m
i
, m
1
+ m
2
+ . . . + m
k
= n. Кортеж
(M
1
, . . . , M
k
) называется упорядоченным разбиением множества M.
5.4. РАЗБИЕНИЯ
171
Если k = 2, то упорядоченное разбиение множества M на два подмноже- ства, имеющие соответственно m
1
и m
2
элементов, определяется сочетанием
(без повторений) из n элементов по m
1
или из n по m
2
(m
2
= n − m
1
). Следо- вательно, число разбиений R(m
1
, m
2
) равно биномиальному коэффициенту
C
m
1
n
= C
m
2
n
. Таким образом,
R(m
1
, m
2
) =
n!
m
1
!(n − m
1
)!
=
n!
m
1
! m
2
!
.
В общем случае число R(m
1
, m
2
, . . . , m
k
) упорядоченных разбиений
(M
1
, M
2
, . . . , M
k
), для которых |M
i
| = m
i
, равно
n!
m
1
! m
2
! . . . m
k
!
, а число
R
0
(n, k) упорядоченных разбиений на k подмножеств вычисляется по фор- муле
R
0
(n, k) =
X
m
1
+ ... +m
k
=n,
m
i
>0
R(m
1
, m
2
, . . . , m
k
).
Числа R(m
1
, m
2
, . . . , m
k
) называются полиномиальными коэффициентами,
поскольку для всех a
1
, a
2
, . . . , a
k
∈ R справедливо соотношение
(a
1
+ a
2
+ . . . + a
k
)
n
=
X
m
1
+ ... +m
k
=n,
m
i
>0
n!
m
1
! . . . m
k
!
· a
m
1 1
a
m
2 2
. . . a
m
k
k
.
Пример 5.4.1. В студенческой группе, состоящей из 25 человек, при вы- боре старосты за выдвинутую кандидатуру проголосовали 12 человек, про- тив — 10, воздержались — 3. Сколькими способами могло быть проведено такое голосование?
Пусть M — множество студентов в группе, M
1
— множество студентов,
проголосовавших за выдвинутую кандидатуру, M
2
— множество студентов,
проголосовавших против, M
3
— множество студентов, воздержавшихся от голосования. Тогда |M| = 25, |M
1
| = 12, |M
2
| = 10, |M
3
| = 3, (M
1
, M
2
, M
3
) —
упорядоченное разбиение множества M. Искомое число R(12, 10, 3) равно
25!
12!10!3!
= 1487285800. ¤
Число ˆ
R(l
1
, l
2
, . . . , l
r
; m
1
, m
2
, . . . , m
r
) разбиений исходного множества M
на k подмножеств, неупорядоченных между собой, среди которых l
i
множеств
172
Глава 5. КОМБИНАТОРИКА
имеет мощность m
i
, i = 1, . . . , r, l
1
+ . . . + l
r
= k, m
1
l
1
+ . . . + m
r
l
r
= n,
вычисляется по формуле
ˆ
R(l
1
, . . . , l
r
; m
1
, . . . , m
r
) =
n!
l
1
! . . . l
r
!(m
1
!)
l
1
. . . (m
r
!)
l
r
,
а число всех возможных разбиений множества M на k подмножеств, неупо- рядоченных между собой, равно
X
l
1
+...+l
r
=k,
m
1
l
1
+ ... +m
r
l
r
=n,
m
i
>0
при
l
i
>0
ˆ
R(l
1
, . . . , l
r
; m
1
, . . . , m
r
).
1 ... 14 15 16 17 18 19 20 21 ... 29
ЗАДАЧИ И УПРАЖНЕНИЯ
163
•
•
•
•
•
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
R ?
¾
-
±°
²¯
•
•
•
•
¡
¡
¡
¡
¡
¡
µ
¸
?
Y
K
*
¼
g
±°
²¯
Рис. 4.50
Рис. 4.51
6. С помощью матрицы смежности графа (рис. 4.53) найти его матрицы дости- жимости, контрдостижимости и сильных компонент.
7. Найти матрицу расстояний, диаметр, радиус, центральные и периферийные вершины графа, изображенного на рис. 4.54.
8. Найти все кратчайшие маршруты из вершины 2 для взвешенного графа
(рис. 4.55).
9. Доказать, что в любом конечном бесконтурном графе существуют вершины с нулевой полустепенью исхода и с нулевой полустепенью захода.
10. Проверить на эйлеровость и найти минимальное множество покрывающих цепей:
а) графа K
5
; б) графа K
3,3
; в) графа, изображенного на рис. 4.56.
•
•
•
¢
¢
¢
¢¢¸
A
A
A
AAU
1 2
3
G
1
•
•
•
•
¾
A
A
A
AAU
¢
¢
¢
¢
¢®
1 2
3 4
G
2
•
•
•
•
@
@
@
I
¡
¡
¡
µ
?
@
@
@
R
h
1 2
3 4
Рис. 4.52
Рис. 4.53
•
•
•
•
•
•
•
¡
¡
¡
¡
@
@
@
@
@
@
•
•
•
•
•
½
½
½
½
>
Z
Z
Z
Z
?
-
@
@
@
@
@
@
R
¡
¡
¡
¡
¡
¡
µ
¾
6
K
®
1 2
3 5
4
(3)
(4)
(6)
(2)
(1)
(2)
(2)
(3)
(−2)
(−5)
Рис. 4.54
Рис. 4.55
164
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
•
•
•
•
•
•
•
¶
¶
¶
¶
¶
¶
³³
³³
³³
³³
´
´
´
´
PPP
PPP
PP
Q
Q
Q
Q
E
E
E
E
E
E
E
E
¢
¢
¢
¢
¢
¢¡
¡
¡
•
•
•
•
•
•
•
¶
¶
¶
¶
¶
¶
@
@
@
´
´
´
´
@
@
@
@
@
@
E
E
E
E
E
E
E
E
S
S
S
S
S
S
¡
¡
¡
¡
¡
¡
¢
¢
¢
¢
¢
¢
(2)
(2)
(3)
(3)
(1)
(2)
(2)
(4)
(3)
(1)
Рис. 4.56
Рис. 4.57
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
@
@
R
¡
¡
ª
¡
¡
ª ?
?
¡
¡
ª
@
@
R
@
@
R
@
@
R
@
@
R
¡
¡
ª
¡
¡
ª
¡
¡
ª
¡
¡
ª
@
@
R
¡
¡
ª
1 2
3 4
5 6
7 8
9 10 11 12 13 14 15 16
•
•
•
•
•
•
•
J
J
JJ
1 2
3 4
5 9
7 8
6 10
Рис. 4.58
Рис. 4.59
11. Построить все неизоморфные трех-, четырех- и пятивершинные деревья.
12. Найти остов минимального веса взвешенного графа (рис. 4.57).
13. Найти упорядоченный лес, соответствующий бинарному дереву, изображен- ному на рис. 4.58.
14. Найти матрицы фундаментальных циклов и фундаментальных разрезов гра- фа (рис. 4.59).
15. Найти хроматическое число графа (рис. 4.60).
16. Найти толщину графа (рис. 4.61).
•
•
•
•
•
•
•
¡
¡
¡
@
@
@
@
@
@
@
@
@
S
S
S
S
S
S
¦
¦
¦
¦
¦
¦
¦
¦
•
•
•
•
•
•
¡
¡
¡
¡
@
@
@
@
HH
HH
HH
H
HH
HH
HH
H
©©
©©
©©
©
©©
©©
©©
©
Рис. 4.60
Рис. 4.61
Глава 5
КОМБИНАТОРИКА
Комбинаторика — раздел математики, посвященный решению задач вы- бора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множе- ства, называемой комбинаторной конфигурацией. Поэтому целями комби- наторного анализа являются изучение комбинаторных конфигураций, алго- ритмов их построения, оптимизация таких алгоритмов, а также решение за- дач перечисления. Простейшими примерами комбинаторных конфигураций являются перестановки, размещения, сочетания и разбиения. При подсчете комбинаторных конфигураций используются правила суммы, произведения и степени, сформулированные в § 1.4.
§ 5.1.
Перестановки и подстановки
Пусть дано множество M = {a
1
, a
2
, . . . , a
n
}. Перестановкой элементов множества M называется любой кортеж (a
i
1
, a
i
2
, . . . , a
i
n
), состоящий из n
различных элементов множества M.
Перестановки отличаются друг от друга только порядком входящих в них элементов. Покажем, что число P
n
всех перестановок множества M
равно n!. Действительно, на первое место в кортеже можно подставить лю- бой из n элементов, на второе место — любой из n − 1 оставшихся и т. д. Для последнего места остается единственный элемент. Поэтому получаем всего
n(n − 1)(n − 2) . . . 2 · 1 = n! перестановок.
166
Глава 5. КОМБИНАТОРИКА
Пример 5.1.1. 1. Расставить на полке 10 книг можно P
10
= 10! =
= 3 628 800 различными способами.
2. Список студентов группы, состоящей из 25 человек, можно составить
P
25
= 25! способами. ¤
Напомним, что биекция σ: M ↔ M называется подстановкой множе- ства M. Пусть σ — подстановка множества M = {1, 2, . . . , n}. Тогда
σ(k) = s
k
, где 1 6 s
k
6 n, k = 1, 2, . . . , n, {s
1
, s
2
, . . . , s
n
} = {1, 2, . . . , n},
и поэтому подстановку σ можно представить в виде матрицы, состоящей из двух строк:
[σ]
µ
1 2 . . . n
s
1
s
2
. . . s
n
¶
.
Ясно, что если в матрице [σ] переставить столбцы, то полученная матрица будет также определять подстановку σ. Множество всех подстановок мно- жества {1, 2, . . . , n} обозначается через S
n
. Для подстановок σ, τ ∈ S
n
можно определить произведение σ · τ как произведение двух функций. Зная матри- цы подстановок
[σ] =
µ
1 2 . . . n
s
1
s
2
. . . s
n
¶
и [τ ], переставив столбцы матрицы [τ ] так, чтобы ее первая строка совпала со второй строкой матрицы [σ]:
µ
s
1
s
2
. . . s
n
t
1
t
2
. . . t
n
¶
,
получаем
[στ ] =
µ
1 2 . . . n
s
1
s
2
. . . s
n
¶ µ
s
1
s
2
. . . s
n
t
1
t
2
. . . t
n
¶
=
µ
1 2 . . . n
t
1
t
2
. . . t
n
¶
.
Пример 5.1.2. Если [σ] =
µ
1 2 3 4 2 1 4 3
¶
, [τ ] =
µ
1 2 3 4 3 1 4 2
¶
, то
[στ ] =
µ
1 2 3 4 2 1 4 3
¶ µ
2 1 4 3 1 3 2 4
¶
=
µ
1 2 3 4 1 3 2 4
¶
. ¤
Теорема 5.1.1. Алгебра hS
n
; ·i является группой. При n > 3 она неком-
мутативна.
5.1. ПЕРЕСТАНОВКИ И ПОДСТАНОВКИ
167
Доказательство. Операция · ассоциативна как операция произведе- ния функций. Легко проверяется, что существует единичная подстановка ε
с матрицей [ε] =
µ
1 2 . . . n
1 2 . . . n
¶
и для любой подстановки σ с матрицей
[σ] =
µ
1 2 . . . n
s
1
s
2
. . . s
n
¶
существует обратная подстановка σ
−1
, соответству- ющая матрице
µ
s
1
s
2
. . . s
n
1 2 . . . n
¶
Если n > 3, то рассмотрим подстановки σ и τ
с матрицами
[σ] =
µ
1 2 3 4 . . . n
2 1 3 4 . . . n
¶
и [τ ] =
µ
1 2 3 4 . . . n
3 2 1 4 . . . n
¶
Имеем [στ ] =
µ
1 2 3 4 . . . n
2 3 1 4 . . . n
¶
, [τ σ] =
µ
1 2 3 4 . . . n
3 1 2 4 . . . n
¶
, т. е.
στ 6= τ σ. Таким образом, группа hS
n
; ·i некоммутативна. ¤
Группа hS
n
; ·i называется симметрической группой степени n. Число элементов этой группы |S
n
| равно P
n
n!.
Подстановка σ называется циклом длины r, если матрицу [σ] переста- новкой столбцов можно привести к виду
µ
s
1
s
2
s
3
. . . s
r−1
s
r
s
r+1
. . . s
n
s
2
s
3
s
4
. . .
s
r
s
1
s
r+1
. . . s
n
¶
.
Очевидно, что в этом случае σ задает биекцию, в которой s
1
7→ s
2
,
s
2
7→ s
3
, . . ., s
r
7→ s
1
, а остальные элементы неподвижны. Описанный цикл σ
обозначается через (s
1
s
2
. . . s
r
).
Пример 5.1.3. Подстановка с матрицей
µ
1 2 3 4 5 6 1 5 6 4 3 2
¶
является циклом (2 5 3 6), а подстановка с матрицей
µ
1 2 3 4 5 6 4 5 2 1 6 3
¶
циклом не яв- ляется, так как из нее можно выделить два цикла (1 4) и (2 5 6 3). ¤
Циклы (s
1
s
2
. . . s
r
) и (t
1
t
2
. . . t
p
) называются независимыми, если
{s
1
, s
2
, . . . , s
r
} ∩ {t
1
, t
2
, . . . , t
p
} = ∅.
Теорема 5.1.2. Каждую подстановку можно однозначно, с точностью
до порядка сомножителей, представить в виде произведения независимых
циклов. ¤
168
Глава 5. КОМБИНАТОРИКА
В примере 5.1.3 имеем
µ
1 2 3 4 5 6 1 5 6 4 3 2
¶
= (2 5 3 6) и
µ
1 2 3 4 5 6 4 5 2 1 6 3
¶
= (1 4)(2 5 6 3).
Двухэлементный цикл (i j) называется транспозицией. При транспози- ции i-й и j-й элементы меняются местами, а остальные сохраняют свое по- ложение.
Теорема 5.1.3. Каждая подстановка есть произведение транспозиций.
Доказательство. По теореме 5.1.2 достаточно установить, что любой цикл (s
1
s
2
. . . s
r
) можно представить в виде произведения транспозиций,
но легко проверяется, что (s
1
s
2
. . . s
r
) = (s
1
s
2
)(s
1
s
3
) . . . (s
1
s
r
). ¤
Пример 5.1.4. (1 2 3 4) = (1 2)(1 3)(1 4). ¤
§ 5.2.
Размещения и сочетания
Пусть M — множество, состоящее из n элементов, m 6 n. Размещением
из n элементов по m или упорядоченной (n, m)-выборкой, называется любой кортеж (a
i
1
, a
i
2
, . . . , a
i
m
), состоящий из m попарно различных элементов мно- жества M. Размещение можно рассматривать как разнозначную функцию
f : {1, 2, . . . , m} → M, для которой f (j) = a
i
j
Пример 5.2.1. Для множества M = {a, b, c} пары (a, b) и (b, a) являются размещениями из 3 по 2, тройка (a, c, b) — размещением из 3 по 3, а тройка
(b, a, b) размещения не образует. ¤
Число размещений из n по m обозначается через A
m
n
или P (n, m). Пока- жем, что
A
m
n
=
n!
(n − m)!
= n(n − 1) . . . (n − m + 1)
(5.1)
(напомним, что 0! = 1). Действительно, размещение m элементов мож- но представить как заполнение некоторых m позиций элементами множе- ства M. При этом первую позицию можно заполнить n различными спосо- бами. После того как 1-я позиция заполнена, элемент для заполнения 2-й позиции можно выбрать (n − 1) способами. Если продолжить этот процесс,
5.2. РАЗМЕЩЕНИЯ И СОЧЕТАНИЯ
169
то после заполнения позиций с 1-й по (m − 1)-ю будем иметь (n − m + 1) спо- собов заполнения последней, m-й позиции. Перемножая эти числа, получаем формулу (5.1).
Пример 5.2.2. Из десяти различных книг произвольным образом бе- рутся и ставятся на полку одна за другой 3 книги. Имеется A
3 10
вариантов расстановок, где A
3 10
=
10!
7!
= 10 · 9 · 8 = 720. ¤
Cочетанием из n элементов по m или неупорядоченной (n, m)-выборкой
называется любое подмножество множества M, состоящее из m элементов.
Пример 5.2.3. Если M = {a, b, c}, то {a, b}, {a, c}, {b, c} — все сочетания из 3 по 2. ¤
Число сочетаний из n по m обозначается через C
m
n
,
¡
n
m
¢
или C(n, m).
Если объединить размещения из n элементов по m, состоящие из од- них и тех же элементов (не учитывая порядка их расположения), в клас- сы эквивалентности, то можно установить биекцию ϕ между сочетаниями и полученными классами по следующему правилу: ϕ({a
i
1
, a
i
2
, . . . , a
i
m
})
{(b
1
, b
2
, . . . , b
m
) | {b
1
, b
2
, . . . , b
m
} = {a
i
1
, a
i
2
, . . . , a
i
m
}}. Так как из каждого сочетания C можно получить m! размещений (упорядочивая m! способами элементы из множества C по числу перестановок этого множества), то каж- дый класс эквивалентности содержит m! размещений и, значит, A
m
n
= m!·C
m
n
,
т. е. C
m
n
=
A
m
n
m!
. Таким образом,
C
m
n
=
n!
(n − m)! m!
.
Пример 5.2.4. Из десяти чисел четыре можно выбрать C
4 10
=
10!
6!4!
=
=
7·8·9·10 4!
=
7·8·9·10 1·2·3·4
= 210 способами. ¤
Число C
m
n
обладает следующими свойствами:
1) C
m
n
= C
n−m
n
;
2) C
m
n
+ C
m+1
n
= C
m+1
n+1
(правило Паскаля);
3) (a + b)
n
=
n
P
m=0
C
m
n
a
m
b
n−m
для любых a, b ∈ R, n ∈ ω (бином Ньютона).
В силу последнего свойства числа C
m
n
называются биномиальными коэф-
фициентами.
Пример 5.2.5. Из свойства 3 следует, что 2
n
=
n
P
m=0
C
m
n
. Действительно,
2
n
= (1 + 1)
n
=
n
P
m=0
C
m
n
1
m
1
n−m
=
n
P
m=0
C
m
n
. ¤
170
Глава 5. КОМБИНАТОРИКА
§ 5.3.
Размещения и сочетания с повторением
Размещением с повторением из n элементов по m или упорядоченной
(n, m)-выборкой с возвращениями называется любой кортеж (a
1
, a
2
, . . . , a
m
)
элементов множества M, для которого |M| = n.
Поскольку в кортеж (a
1
, a
2
, . . . , a
m
) на каждое место может претендовать любой из n элементов множества M, число размещений с повторениями
ˆ
P (n, m) равно n · n · . . . · n
|
{z
}
m раз
= n
m
:
ˆ
P (n, m) = n
m
.
Пример 5.3.1. Из цифр 1, 2, 3, 4 можно составить ˆ
P (4, 3) = 4 3
= 64
трехзначных числа. ¤
Определим отношение эквивалентности на множестве размещений с по- вторениями из n по m:
(a
1
, a
2
, . . . , a
m
) ∼ (b
1
, b
2
, . . . , b
m
) ⇔ для любого c ∈ M число элементов a
i
,
равных c, совпадает с числом элементов b
i
, равных c.
Сочетанием с повторением из n элементов по m или неупорядоченной
(n, m)-выборкой с возвращениями называется любой класс эквивалентности по отношению ∼ множества размещений с повторениями из n элементов по
m. Другими словами, сочетания с повторениями суть множества, которые состоят из элементов, выбранных m раз из множества M, причем один и тот же элемент допускается выбирать повторно.
Число сочетаний с повторениями из n элементов по m обозначается через ˆ
C(n, m) и вычисляется по формуле
ˆ
C(n, m) = C
m
n+m−1
=
(n + m − 1)!
m!(n − 1)!
.
Пример 5.3.2. Число различных бросаний двух одинаковых кубиков равно ˆ
C(6, 2) = C
2 7
= 21. ¤
§ 5.4.
Разбиения
Пусть M — множество мощности n, {M
1
, M
2
, . . . , M
k
} — разбиение мно- жества M на k подмножеств, |M
i
| = m
i
, m
1
+ m
2
+ . . . + m
k
= n. Кортеж
(M
1
, . . . , M
k
) называется упорядоченным разбиением множества M.
5.4. РАЗБИЕНИЯ
171
Если k = 2, то упорядоченное разбиение множества M на два подмноже- ства, имеющие соответственно m
1
и m
2
элементов, определяется сочетанием
(без повторений) из n элементов по m
1
или из n по m
2
(m
2
= n − m
1
). Следо- вательно, число разбиений R(m
1
, m
2
) равно биномиальному коэффициенту
C
m
1
n
= C
m
2
n
. Таким образом,
R(m
1
, m
2
) =
n!
m
1
!(n − m
1
)!
=
n!
m
1
! m
2
!
.
В общем случае число R(m
1
, m
2
, . . . , m
k
) упорядоченных разбиений
(M
1
, M
2
, . . . , M
k
), для которых |M
i
| = m
i
, равно
n!
m
1
! m
2
! . . . m
k
!
, а число
R
0
(n, k) упорядоченных разбиений на k подмножеств вычисляется по фор- муле
R
0
(n, k) =
X
m
1
+ ... +m
k
=n,
m
i
>0
R(m
1
, m
2
, . . . , m
k
).
Числа R(m
1
, m
2
, . . . , m
k
) называются полиномиальными коэффициентами,
поскольку для всех a
1
, a
2
, . . . , a
k
∈ R справедливо соотношение
(a
1
+ a
2
+ . . . + a
k
)
n
=
X
m
1
+ ... +m
k
=n,
m
i
>0
n!
m
1
! . . . m
k
!
· a
m
1 1
a
m
2 2
. . . a
m
k
k
.
Пример 5.4.1. В студенческой группе, состоящей из 25 человек, при вы- боре старосты за выдвинутую кандидатуру проголосовали 12 человек, про- тив — 10, воздержались — 3. Сколькими способами могло быть проведено такое голосование?
Пусть M — множество студентов в группе, M
1
— множество студентов,
проголосовавших за выдвинутую кандидатуру, M
2
— множество студентов,
проголосовавших против, M
3
— множество студентов, воздержавшихся от голосования. Тогда |M| = 25, |M
1
| = 12, |M
2
| = 10, |M
3
| = 3, (M
1
, M
2
, M
3
) —
упорядоченное разбиение множества M. Искомое число R(12, 10, 3) равно
25!
12!10!3!
= 1487285800. ¤
Число ˆ
R(l
1
, l
2
, . . . , l
r
; m
1
, m
2
, . . . , m
r
) разбиений исходного множества M
на k подмножеств, неупорядоченных между собой, среди которых l
i
множеств
172
Глава 5. КОМБИНАТОРИКА
имеет мощность m
i
, i = 1, . . . , r, l
1
+ . . . + l
r
= k, m
1
l
1
+ . . . + m
r
l
r
= n,
вычисляется по формуле
ˆ
R(l
1
, . . . , l
r
; m
1
, . . . , m
r
) =
n!
l
1
! . . . l
r
!(m
1
!)
l
1
. . . (m
r
!)
l
r
,
а число всех возможных разбиений множества M на k подмножеств, неупо- рядоченных между собой, равно
X
l
1
+...+l
r
=k,
m
1
l
1
+ ... +m
r
l
r
=n,
m
i
>0
при
l
i
>0
ˆ
R(l
1
, . . . , l
r
; m
1
, . . . , m
r
).
1 ... 14 15 16 17 18 19 20 21 ... 29
Пример 5.4.2. Сколькими способами из группы в 28 человек можно сформировать 4 коалиции по 7 человек?
Пусть M — множество людей в группе, l
i
— число коалиций по i человек,
где i = 1, . . . , 28. Тогда по условиям задачи имеем |M| = 28, l
7
= 4, l
i
= 0,
i ∈ {1, 2, . . . , 28} \ {7}, m
7
= 7, и, следовательно, искомое число будет равно
ˆ
R(4; 7) =
28!
4!(7!)
4
. ¤
§ 5.5.
Метод включений и исключений
Пусть множество A имеет N элементов и n одноместных отношений
(свойств) P
1
, P
2
, . . ., P
n
. Каждый из N элементов может обладать или не обладать любым из этих свойств. Обозначим через N
i
1
...i
k
число элемен- тов, обладающих свойствами P
i
1
, . . . , P
i
k
и, может быть, некоторыми дру- гими. Тогда число N(0) элементов, не обладающих ни одним из свойств
P
1
, P
2
, . . . , P
n
, определяется по следующей формуле, называемой формулой
включений и исключений:
N(0) = S
0
− S
1
+ S
2
− . . . + (−1)
n
S
n
,
(5.2)
где S
0
= N; S
k
=
P
16i
1
<...
k
6n
N
i
1
...i
k
, k = 1, 2, . . . , n.
Пример 5.5.1. Пусть колода состоит из n карт, пронумерованных чис- лами 1, 2, . . . , n. Сколькими способами можно расположить карты в колоде так, чтобы ни для одного i (1 6 i 6 n) карта с номером i не занимала i-е место?
5.5. МЕТОД ВКЛЮЧЕНИЙ И ИСКЛЮЧЕНИЙ
173
Имеется n свойств P
i
в виде “i-я карта занимает в колоде i-е место”. Число всевозможных расположений карт в колоде равно n!. Число N
i
1
...i
k
располо- жений, при которых карта с номером i
j
занимает место i
j
(j = 1, . . . , k),
равно (n − k)!. Тогда S
0
= n!,
S
k
=
X
16i
1
<...
k
6n
N
i
1
...i
k
= C
k
n
(n − k)! =
n!
k!
.
Используя формулу (5.2), получаем, что число N(0) расположений, при ко- торых ни одно из свойств P
i
не выполнено, равно
n
X
k=0
(−1)
k
S
k
= n!
n
X
k=0
(−1)
k
1
k!
. ¤
Обобщая формулу (5.2), получаем формулу, позволяющую вычислить число N(r) элементов, обладающих ровно r свойствами (1 6 r 6 n):
N(r) =
n−r
X
k=0
(−1)
k
C
r
r+k
S
r+k
.
(5.3)
В § 3.4 мы определили функцию [x] для вещественных чисел x как наи- большее целое число, не превосходящее x. Для положительных целых чисел
a и b значение функции [
b
a
] равно количеству чисел из множества {1, 2, . . . , b},
которые делятся на a, т. е. кратных a.
Пример 5.5.2. Сколько натуральных чисел от 1 до 500 делятся ровно на одно из чисел 3, 5 или 7?
Обозначим свойства делимости на 3, 5 и 7 соответственно через P
1
, P
2
и P
3
. Тогда для N = 500 имеем N
1
= [
500 3
] = 166, N
2
= [
500 5
] = 100,
N
3
= [
500 7
] = 71. Так как N
12
— число общих кратных для чисел 3 и 5,
наименьшее общее кратное которых равно 15, то N
12
совпадает с количе- ством чисел, которые делятся на 15, т. е. N
12
= [
500 15
] = 33. Аналогич- но N
13
= [
500 21
] = 23, N
23
= [
500 35
] = 14, N
123
= [
500 105
] = 4. По формуле
(5.3) находим искомое число чисел N(1) =
3−1
P
k=0
(−1)
k
C
1 1+k
S
1+k
= (−1)
0
C
1 1
S
1
+
+(−1)
1
C
1 2
S
2
+ (−1)
2
C
1 3
S
3
= (N
1
+ N
2
+ N
3
) − 2(N
12
+ N
13
+ N
23
) + 3N
123
=
= 166 + 100 + 71 − 2(33 + 23 + 14) + 3 · 4 = 209. ¤
174
Глава 5. КОМБИНАТОРИКА
§ 5.6.
Рекуррентные соотношения.
Возвратные последовательности
Рекуррентным соотношением, рекуррентным уравнением или рекуррент-
ной формулой называется соотношение вида
a
n+k
= F (n, a
n
, a
n+1
, . . . , a
n+k−1
),
которое позволяет вычислять все члены последовательности a
0
, a
1
, a
2
, . . .,
если заданы ее первые k членов.
Пример 5.6.1. 1. Формула a
n+1
= a
n
+ d задает арифметическую про- грессию.
2. Формула a
n+1
= q · a
n
определяет геометрическую прогрессию.
3. Формула a
n+2
= a
n+1
+ a
n
задает последовательность чисел Фибо-
наччи. ¤
В случае, когда рекуррентное соотношение линейно и однородно, т. е.
выполняется соотношение вида
a
n+k
+ p
1
a
n+k−1
+ . . . + p
k
a
n
= 0
(5.4)
(p
i
= const), последовательность a
0
, a
1
, a
2
, . . . называется возвратной. Мно- гочлен
P
a
(x) x
k
+ p
1
x
k−1
+ . . . + p
k
(5.5)
называется характеристическим для возвратной последовательности {a
n
}.
Корни многочлена P
a
(x) называются характеристическими.
Множество всех последовательностей, удовлетворяющих данному ре- куррентному соотношению, называется общим решением.
Описание общего решения соотношения (5.4) имеет аналоги с описани- ем решения обыкновенного дифференциального уравнения с постоянными коэффициентами.
Теорема 5.6.1. 1. Пусть λ — корень характеристического многочле-
на (5.5). Тогда последовательность {cλ
n
}, где c — произвольная константа,
удовлетворяет соотношению (5.4).
2. Если λ
1
, λ
2
, . . ., λ
k
— простые корни характеристического многочле-
на (5.5), то общее решение рекуррентного соотношения (5.4) имеет вид
a
n
= c
1
λ
n
1
+ c
2
λ
n
2
+ . . . + c
k
λ
n
k
, где c
1
, c
2
, . . . , c
k
— произвольные константы.
5.6. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ
175 3. Если λ
i
— корень кратности r
i
(i = 1, . . . , s) характеристического
многочлена (5.5), то общее решение рекуррентного соотношения (5.4) име-
ет вид
a
n
=
s
X
i=1
(c
i1
+ c
i2
n + . . . + c
ir
i
n
r
i
−1
) · λ
n
i
,
где c
ij
— произвольные константы. ¤
Зная общее решение рекуррентного уравнения (5.4), по начальным усло- виям a
0
, a
1
, . . ., a
k−1
можно найти неопределенные постоянные c
ij
и тем самым получить решение уравнения (5.4) с данными начальными условия- ми.
Пример 5.6.2. Найти последовательность {a
n
}, удовлетворяющую ре- куррентному соотношению a
n+2
− 4a
n+1
+ 3a
n
= 0 и начальным условиям
a
1
= 10, a
2
= 16.
Корнями характеристического многочлена P
a
(x) = x
2
− 4x + 3 являются числа x
1
= 1 и x
2
= 3. Следовательно, по теореме 5.6.1 общее решение имеет вид a
n
= c
1
+ c
2 3
n
. Используя начальные условия, получаем систему
(
c
1
+ 3c
2
= 10,
c
1
+ 9c
2
= 16,
решая которую, находим c
1
= 7 и c
2
= 1. Таким образом, a
n
= 7 + 3
n
. ¤
Рассмотрим неоднородное линейное рекуррентное уравнение
a
n+k
+ p
1
a
n+k−1
+ . . . + p
k
a
n
= f (n), n = 0, 1, . . .
(5.6)
Пусть {b
n
} — общее решение однородного уравнения (5.4), а {c
n
} —
частное (конкретное) решение неоднородного уравнения (5.6). Тогда после- довательность {b
n
+c
n
} образует общее решение уравнения (5.6), и тем самым справедлива
Теорема 5.6.2. Общее решение неоднородного линейного рекуррентного
уравнения представляется в виде суммы общего решения соответствую-
щего однородного линейного рекуррентного уравнения и некоторого част-
ного решения неоднородного уравнения. ¤
176
Глава 5. КОМБИНАТОРИКА
Таким образом, в силу теоремы 5.6.1 задача нахождения общего решения рекуррентного уравнения (5.6) сводится к нахождению некоторого частного решения.
В отдельных случаях имеются общие рецепты нахождения частного ре- шения.
Если f (n) = β
n
(где β не является характеристическим корнем), то, под- ставляя a
n
= cβ
n
в (5.6), получаем c(β
k
+ p
1
β
k−1
+ . . . + p
k
) · β
n
= β
n
и отсюда
c · P
a
(β) = 1, т. е. частное решение можно задать формулой a
n
=
1
P
a
(β)
· β
n
Пусть f (n) — многочлен степени r от переменной n и число 1 не является характеристическим корнем. Тогда P
a
(1) = 1 + p
1
+ . . . + p
k
6= 0 и частное решение следует искать в виде a
n
=
r
P
i=0
d
i
n
i
. Подставляя многочлены в фор- мулу (5.6), получаем
r
X
i=0
d
i
(n + k)
i
+ p
1
r
X
i=0
d
i
(n + k − 1)
i
+ . . . + p
k
r
X
i=0
d
i
n
i
=
=
r
X
i=0
d
i
((n + k)
i
+ p
1
(n + k − 1)
i
+ . . . + p
k
n
i
) =
=
r
X
i=0
d
i
(g
1
n
i
+ . . .) = f (n).
Сравнивая коэффициенты в левой и правой частях последнего равенства,
получаем соотношения для чисел d
i
, позволяющие эти числа определить.
Пример 5.6.3. Найти решение уравнения
a
n+1
+ 2a
n
= n + 1
(5.7)
с начальным условием a
0
= 1.
Рассмотрим характеристический многочлен P
a
(x) = x+2. Так как P
a
(1) =
= 3 6= 0 и правая часть f (n) уравнения (5.6) равна n + 1, то частное реше- ние будем искать в виде c
n
= d
0
+ d
1
· n. Подставляя c
n
в уравнение (5.7),
получаем (d
0
+d
1
(n+1))+2(d
0
+d
1
·n) = (3d
0
+d
1
)+3d
1
·n = 1+n. Приравни- вая коэффициенты в левой и правой частях последнего равенства, получаем систему
(
3d
0
+ d
1
= 1,
3d
1
= 1,
ЗАДАЧИ И УПРАЖНЕНИЯ
177
откуда находим d
0
=
2 9
, d
1
=
1 3
. Таким образом, частное решение уравне- ния (5.7) имеет вид c
n
=
2 9
+
1 3
n. По теореме 5.6.1 общее решение однородно- го уравнения a
n+1
+ 2a
n
= 0 задается формулой b
n
= c · (−2)
n
, и по теореме
5.6.2 получаем общее решение уравнения (5.7): a
n
=
2 9
+
1 9
n + c · (−2)
n
. Из на- чального условия a
0
= 1 находим
2 9
+ c = 1, т. е. c =
7 9
. Таким образом,
a
n
=
2 9
+
1 3
n +
7 9
(−2)
n
. ¤
Задачи и упражнения
1. Сколько различных слов можно составить из букв a, b, c, d, если использо- вать каждую букву по одному разу?
2. Сколькими способами можно расставить 8 ладей на шахматной доске так,
чтобы они не били друг друга?
3. Сколько различных флагов можно составить из трех горизонтальных полос белого, синего и красного цветов?
4. Сколькими способами можно составить список из 22 студентов?
5. В чемпионате участвуют 12 спортсменов. Сколькими способами могут быть распределены золотая, серебряная и бронзовая медали?
6. 15 студентов обменялись попарно друг с другом фотографиями. Сколько всего фотографий?
7. Сколько существует неупорядоченных четырехзначных кодов, составленных из 10 цифр?
8. Во взводе 3 сержанта и 30 солдат. Сколько существует способов выделения одного сержанта и трех солдат для патрулирования?
9. Сколькими способами из 20 студентов можно выбрать 5 делегатов?
10. Сколькими способами из простых делителей числа 2310 можно составить числа, имеющие ровно два простых делителя?
11. Сколько диагоналей имеет выпуклый n-угольник?
12. Найти наибольшее возможное число пересечений диагоналей выпуклого
n-угольника.
13. Сколькими способами можно разбить группу из 15 человек на две подгруп- пы, в одну из которых входят 4 человека, а в другую — 11?
178
Глава 5. КОМБИНАТОРИКА
14. Решить уравнение:
а) A
5
n
= 18 · A
4
n−2
;
б) C
x−2
x
= 45,
в) C
2x+3 2x+8
= 13 · A
3 2x+6 15. Найти два средних члена разложения (a
3
− ab)
31 16. Доказать, что а) 1 − C
1
n
+ C
2
n
− C
3
n
+ . . . + (−1)
n
= 0;
б) 1 2
+ (C
2
n
)
2
+ . . . + (C
n
n
)
2
= C
n
2n
17. Крокодил имеет 68 зубов. Доказать, что среди 16 17
крокодилов может не ока- заться двух с одним и тем же набором зубов.
18. Сколько различных десятизначных чисел можно написать, используя циф- ры 0, 1 и 2?
19. Алфавит X состоит из двух символов. Сколько существует слов алфавита X,
длины которых не превосходят 4?
20. Автомобильные номера данного региона состоят из трех цифр и трех букв алфавита X = {A, B, C, D, E, H, K, M, O, P, T, X, Y}. Сколько автомобилей может быть занумеровано различными номерами?
21. Сколькими способами можно разложить 5 монет достоинством 1 коп., 5 коп.,
10 коп., 50 коп., 1 руб. в два кармана?
22. Чему равно число различных результатов бросаний двух неотличимых ку- биков, на грани каждого из которых нанесены цифры 1, 2, 3, 4, 5, 6?
23. Сколько различных перестановок образуется из следующих слов:
а) зебра; б) баран; в) водород; г) абракадабра?
24. Группе из пяти сотрудников выделено три путевки. Сколько существует спо- собов распределения путевок, если:
а) все путевки различны; б) все путевки одинаковы?
25. Сколько существует способов размещения 8 человек в восьмиместном авто- мобиле, если место водителя могут занять 4 человека?
26. На арену цирка выводятся 5 львов и 4 тигра. Сколькими способами мож- но расположить зверей в цепочку, если запрещено выводить тигров одного за другим?
ЗАДАЧИ И УПРАЖНЕНИЯ
179 27. В лотерее разыгрывается 5 выигрышных билетов. Подошедший к урне вы- нимает наугад 5 билетов из 100 имеющихся. Сколькими способами можно вынуть 3 выигрышных билета?
28. Имеется 2n билетов в театр на один ряд, состоящий из 2n мест. Сколько су- ществует способов распределения мест для компании из n мужчин и n жен- щин, если не располагаются рядом двое мужчин и две женщины?
29. На плоскости заданы m параллельных прямых, а также n параллельных прямых так, что каждая из m прямых пересекается с каждой из n прямых в единственной точке. Сколько различных параллелограммов можно соста- вить из рассматриваемых прямых?
30. Сколько решений в натуральных числах имеет уравнение
x
1
+ x
2
+ . . . + x
n
= n?
1 ... 15 16 17 18 19 20 21 22 ... 29