Введение в комбинаторику. Теория и задачи

Учебное пособие

 М.А.Иванов, Ю.В.Якубович

ВВЕДЕНИЕ 
В КОМБИНАТОРИКУ

ТЕОРИЯ И ЗАДАЧИ

ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

УДК 519.1
ББК 22.176
И20

Р е ц е н з е н т ы: д-р физ.-мат. наук, проф. Е. В. Дыбкова (С.-Петерб. ун-т),
д-р физ.-мат. наук, cтарший науч. сотрудник С. В. Дужин (С.-Петерб. отд.
математического ин-та РАН (ПОМИ РАН))

Рекомендовано к публикации Учебно-методической комиссией
математико-механического факультета
Санкт-Петербургского государственного университета

И20
Иванов М. А., Якубович Ю. В.
Введение в комбинаторику. Теория и задачи: учеб. пособие. —
СПб.: Изд-во С.-Петерб. ун-та, 2018. — 136 с.

ISBN 978-5-288-05792-2

В учебном пособии рассматриваются основные понятия комбинаторики, которые
лежат в основе многих математических доказательств. Материал изложен доступным языком без сложного математического аппарата, что отличает настоящее пособие от других учебников по комбинаторике. Помимо теоретического материала,
в учебном пособии представлено около 330 задач различного уровня сложности.
Пособие предназначено для студентов младших курсов математических специальностей, но может быть также полезно старшеклассникам, интересующимся математикой.

УДК 519.1

ББК 22.176

При оформлении обложки использована  цв. литография 
В. В. Кандинского «Фиолетовый». 1923 г. 
Shutterstock.com

ISBN 978-5-288-05792-2

c⃝
Санкт-Петербургский
государственный
университет, 2018

c⃝
М. А. Иванов, Ю. В. Якубович, 2018

С О Д Е Р Ж А Н И Е

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5

Список используемых обозначений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6

1. Метод математической индукции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.1. Неформальное введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
—
1.2. Формализация и обобщения.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
Задачи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9

2. Основные комбинаторные объекты и методы. . . . . . . . . . . . . . . . . . . . . . . .
13
2.1. Простейшие способы комбинаторных подсчетов .. . . . . . . . . . . . . . . . . . . . . .
—
2.2. Cm
n и его свойства.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.3. Наборы с повторениями.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.4. Формула включений-исключений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.5. Разбиения перестановок на циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.6. Разбиения множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
2.7. Разбиения натуральных чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
Задачи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23

3. Введение в теорию графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
3.1. Неформальное введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
—
3.2. Вершины и рёбра . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
3.3. Изоморфизмы графов.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
3.4. Пути, циклы и маршруты. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
3.5. Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
3.6. Двудольные графы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
3.7. Эйлеровы графы .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
3.8. Лемма Шпернера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
Задачи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58

4. Элементарная теория вероятностей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
4.1. Схема равновероятных исходов .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
—
4.2. Условная вероятность и независимость .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
4.3. Применение условных вероятностей .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
4.4. Схема Бернулли. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
Задачи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77

5. Рекуррентные соотношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
5.1. Неформальное введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
—
5.2. Линейные однородные рекуррентные соотношения с постоянными коэффициентами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
5.3. Линейные неоднородные рекуррентные соотношения с постоянными
коэффициентами.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
5.4. Числа Каталана.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
Задачи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95

6. Производящие функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
102
6.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
—
6.2. Производящие функции и рекуррентные соотношения .. . . . . . . . . . . . . . .
111
6.3. Экспоненциальные производящие функции. . . . . . . . . . . . . . . . . . . . . . . . . . . .
119

3

6.4. Разбиения целых чисел и производящие функции. . . . . . . . . . . . . . . . . . . . .
120
Задачи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
122

7. Дополнительные материалы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
129
Вариант экзамена 2011 г.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
—
Вариант экзамена 2012 г.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
130
Вариант экзамена 2013 г.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
131
Вариант экзамена 2014 г.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
132
Вариант экзамена 2015 г.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
133
Вариант экзамена 2016 г.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
134

Список литературы для дополнительного чтения . . . . . . . . . . . . . . . . . . . . .
135

Предисловие

Настоящее учебное пособие предназначено для самостоятельной работы студентов, изучающих предмет «Комбинаторика», при подготовке к занятиям
и экзаменам, выполнении домашних работ. Авторы вели занятия по этому
предмету в течении последних шести лет и столкнулись с нехваткой подходящей учебной литературы. Это послужило причиной разработки данного
издания, в котором достаточно подробно изложены все основные темы, входящие в программу, а также разобраны различные примеры.
Комбинаторика является одной из старейших математических дисциплин,
которая активно развивается в настоящее время в связи с новыми возможностями и потребностями, появившимися с развитием вычислительной техники,
новыми приложениями комбинаторных задач в физике и биологии, усовершенствованием алгебраической и вероятностной техники. Затрагиваемые в
пособии темы являются классическими, по ним имеется обширная литература, однако рассмотренный материал поностью не был изложен ни в одной из
книг. К тому же большинство учебников либо слишком элементарны, либо,
наоборот, трудно воспринимаются студентами первого курса, поскольку часто апеллируют к ещё незнакомым им понятиям. Мы, напротив, старались
излагать необходимую информацию, не выходя за рамки программы первого
семестра.
В ряде мест, тем не менее, поясняется связь рассматриваемых тем с понятиями алгебры и анализа, которые обычно вводятся в соответствующих
курсах позже. Такие места набраны шрифтом без засечек и могут быть опущены без ущерба для понимания основного текста. Эти пояснения, однако,
могут оказаться полезными тем студентам, которые уже знакомы с необходимыми понятиями.
Помимо теоретического материала в пособии разбираются примеры решения задач и даются упражнения на понимание и закрепление рассмотренных
понятий. В конце каждого раздела приводятся задачи для самостоятельной
работы. Некоторые из них достаточно просты и служат в основном для проверки усвоения теоретических сведений, другие — сложнее и требуют некоторой изобретательности для их решения. В ряде задач даны ответы; более
сложные задачи снабжены указаниями. В приложении приводятся варианты
задач, которые выносились в 2011–2016 годах на экзамены по предмету «Комбинаторика» на первом курсе математико-механического факультета СПбГУ.

Список используемых обозначений

Общие обозначения

|A|
количество элементов (мощность) множества A;
δn,k
символ Кронекера, равный 1 при n = k и 0 при n ̸= k;
[x]
целая часть x, т. е. наибольшее целое, не превосходящее x;

Комбинаторные функции

b(n)
число Белла, т. е. количество разбиений множества из
n элементов;
cn
число Каталана;
Cm
n
число сочетаний без повторений или биномиальный
коэффициент;

C
n
m
количество представлений числа n в виде упорядоченной суммы m неотрицательных слагаемых;
p(n)
количество разбиений натурального числа n;
P(n1, . . . , nk)
число перестановок с повторениями;
s(n, k)
число Стирлинга первого рода без знака, т. е. количество перестановок n-элементного множества с k циклами;
¯s(n, k)
число Стирлинга первого рода со знаком;
S(n, k)
число Стирлинга второго рода, т. е. количество разбиений n-элементного множества на k подмножеств;

Графы

G
дополнение графа G;
d(x, y)
расстояние между вершинами x и y в графе, т. е. длина
кратчайшего пути между ними;
degG(x)
степень вершины x в графе G;
e(G)
количество рёбер в графе G;
E(G)
множество рёбер в графе G;
v(G)
количество вершин в графе G;
V (G)
множество вершин в графе G;
Kn
клика или полный граф с n вершинами;
Kn,m
полный двудольный граф с долями n и m вершин;
G ∖ H
подграф, содержащий все вершины графа G и рёбра,
которые не лежат в его подграфе H

1. Метод математической индукции

1.1. Неформальное введение

Одним из простейших методов математического доказательства является метод перебора. А что делать, если утверждение касается бесконечного множества объектов, и перебрать их все не удастся? Существует метод рассуждения, заменяющий неосуществимый перебор бесконечного числа случаев.
Достаточно проверить первый случай и доказать, что если утверждение истинно в некотором случае, то оно окажется истинно и в следующем за ним
случае. Такой метод называется методом математической индукции.
Опишем метод на простейшем примере. Будем вычислять последовательные суммы нечётных чисел: 1, 1+3, 1+3+5, 1+3+5+7, . . . Мы получим числа
1, 4, 9, 16, являющиеся квадратами чисел 1, 2, 3, 4. Можно ожидать, что для
следующей суммы со слагаемым 9 мы получим квадрат числа 5, т. е. 25, что
легко проверить. Итак, мы выдвигаем гипотезу, что для любого натурального
n выполняется равенство:

1 + 3 + 5 + . . . + (2n − 1) = n2.
(1)

Мы проверили это равенство для n = 1, 2, 3, 4, 5, но, как было отмечено
выше, последовательный перебор натуральных чисел никогда не даст доказательства этой гипотезы, т. к. сколько бы чисел мы не проверили, всегда
остается возможность, что среди оставшихся чисел есть такое, для которого
равенство не выполняется. Нам нужно провести рассуждение, позволяющее
неограниченно увеличивать те числа, для которых верно утверждение. Иными словами нам надо доказать, что если

1 + 3 + 5 + . . . + (2k − 1) = k2,
(2)

то такое же равенство будет справедливо и при добавлении к левой части
равенства следующего нечётного числа 2k+1 и одновременной замене правой
части на (k + 1)2, т. е.

1 + 3 + 5 + . . . + (2k − 1) + (2k + 1) = (k + 1)2.
(3)

Итак, доказательство справедливости равенства (1) для всех натуральных
чисел свелось к тому, чтобы доказать следующее утверждение: если истинно равенство (2), то истинно и равенство (3). Равенство (3), истинность
которого мы хотим доказать, можно переписать следующим образом:
1 + 3 + 5 + . . . + (2k − 1)
+ (2k + 1) = (k + 1)2.

Но, по предположению (2), квадратную скобку в левой части равенства можно заменить на k2. В результате получаем тождество k2 + (2k + 1) = (k + 1)2.

7

Итак, равенство (1) истинно для n = 1 (база индукции), и из истинности
для n = k следует, что оно истинно для n = k + 1 (индукционный переход).
Но тогда из его истинности для n = 1 следует истинность для n = 1 + 1 = 2,
а тогда и для n = 2 + 1 = 3, и так далее для всех натуральных n.

1.2. Формализация и обобщения

Для доказательства методом математической индукции необходимо следующее:
1) сформулировать утверждение T(n), зависящее от натурального параметра n;
2) установить базу индукции, т. е. проверить истинность утверждения T(1);
3) осуществить индукционный переход, т. е. доказать, что для любого натурального n из истинности T(n) следует истинность T(n + 1).
Почему метод математической индукции работает? Воспользуемся одной
из аксиом множества натуральных чисел:

В любом непустом подмножестве множества натуральных чисел есть
наименьшее число.

Выведем отсюда метод математической индукции. Пусть T(n) истинно не
для всех натуральных n, т. е. множество

{k | T(k) ложно}

не пустое. Тогда по аксиоме в нем есть наименьший элемент. Обозначим его
n0. Возможны два варианта:
1) n0 = 1. Это противоречит базе индукции;
2) n0 > 1. Тогда T(n0 − 1) истинно, а T(n0) ложно. Это противоречит
индукционному переходу.

Упражнение. Выведите следующие модификации метода математической индукции:

а) T(n) истинно для любого натурального n ⩾ k0, если
• T(k0) истинно;
• из истинности T(n) следует истинность T(n+1) для любого натурального
n ⩾ k0.

б ) T(n) истинно для любого натурального n, если
• T(1) истинно;
• из истинности T(k) для всех k < n следует истинность T(n) для любого
натурального n > 1.

в) T(n) истинно для любого натурального n, если
• T(1) и T(2) истинно;

8

• из истинности T(n − 1) и T(n) следует истинность T(n + 1) для любого
натурального n ⩾ 2.

г) T(n) истинно для любого натурального n, если
• T(1) истинно;
• из истинности T(n) следует истинность T(2n) для любого натурального n;
• из истинности T(n) следует истинность T(n−1) для любого натурального
n ⩾ 2.

Математическую индукцию можно сравнить с бесконечным рядом костяшек домино. Свойство выстроенных в ряд домино состоит в том, что если
опрокинуть одну костяшку, падает следующая. Пусть утверждение P(n) состоит в том, что падает n-ая костяшка. Толкнем первую костяшку домино,
т. е. обеспечим истинность P(1). Поскольку каждая костяшка опрокидывает
следующую, то из истинности P(k) следует истинность P(k + 1). Поскольку падают все костяшки, P(k) истинно для каждого положительного целого
числа n.
В дальнейшем, проводя доказательство при помощи описанного выше принципа математической индукции, мы будем просто говорить, что доказываем
утверждение по индукции.

Упражнение. Выведите аксиому о наименьшем элементе из метода математической индукции.

Задачи

1.1. Докажите, что для любого натурального n

а)
1 + 2 + 3 + 4 + . . . + n = n(n + 1)

2
;

б )
12 + 22 + 32 + 42 + . . . + n2 = n(n + 1)(2n + 1)

6
;

в)
13 + 23 + 33 + 43 + . . . + n3 = (1 + 2 + 3 + 4 + . . . + n)2 ;

г)

n
i=1
i(i + 1)(i + 2) . . . (i + k − 1) = n(n + 1)(n + 2) . . . (n + k − 1)(n + k)

k + 1
;

д)
12

1 · 3 + 22

3 · 5 + . . . +
n2

(2n − 1) · (2n + 1) = n(n + 1)

2(2n + 1);

е)
1 − 1

2 + 1

3 − 1

4 + . . . +
1

2n − 1 − 1

2n =
1

n + 1 +
1

n + 2 + . . . + 1

2n;

ж)
1 · 1! + 2 · 2! + . . . + n · n! = (n + 1)! − 1.

9

1.2. Найдите общую формулу для произведения
1 − 1

4

1 − 1

9

. . .
1 − 1

n2

и докажите её по индукции.

1.3. Неравенство Бернулли. Для любого x > −1 и натурального n докажите
неравенство (1 + x)n ⩾ 1 + nx.

1.4. Докажите, что для любого натурального n

а)
n3 − n делится на 3;
б ) 4n + 15n − 1 делится на 9.

Числа Фибоначчи

1.5. Докажите, что последовательность Фибоначчи, задаваемая равенством
fn+2 = fn+1 + fn и начальными данными f0 = 0, f1 = 1, удовлетворяет
следующим соотношениям:

а)
fn+m = fn−1fm + fnfm+1;

б )
f1 + f2 + . . . + fn = fn+2 − 1;

в)
f2 + f4 + . . . + f2n = f2n+1 − 1;

г)
f 2
1 + f 2
2 + . . . + f 2
n = fnfn+1;

д)
f 2
n+1 = fnfn+2 + (−1)n;

е)
f1f2 + f2f3 + . . . + f2n−1f2n = f 2
2n;

ж)
f1f2 + f2f3 + . . . + f2nf2n+1 = f 2
2n+1 − 1;

з)
nf1 + (n − 1)f2 + (n − 2)f3 + . . . + 2fn−1 + fn = fn+4 − (n + 3);

и)
f3 + f6 + . . . + f3n = f3n+2 − 1

2
;

й)
f2n = f 2
n+1 − f 2
n−1;

к)
f3n = f 3
n+1 + f 3
n − f 3
n−1;

л)
1 +
√

5

2

n−2
< fn <
1 +
√

5

2

n−1
при n > 3.

1.6. Формула Бине. Докажите, что последовательность Фибоначчи удовлетворяет равенству:

fn =

1+
√

5

2
n
−
1−
√

5

2
n

√

5
.

10