МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Московский физико-технический институт
(государственный университет)
СБОРНИК ЗАДАЧ
ПО ДИСКРЕТНОМУ АНАЛИЗУ
Комбинаторика. Элементы
алгебры логики. Теория графов
Рекомендовано Учебно-методическим советом
Московского физико-технического института
(государственного университета)
в качестве учебного пособия
для студентов высших учебных заведений
но направлению "Прикладные математика и физика "
МОСКВА 2000
удкдтд
С23
Авторы:
Ю.И. Журавлев, Ю.А. Флеров, О.С. Федько, Т.М. Дадашев
Рецензенты:
Кафедра математической кибернетики
Московского государственного университета им. М.В. Ломоносова
Доктор физико-математических наук, профессор В.К. Леонтьев
С23 СБОРНИК ЗАДАЧ ПО ДИСКРЕТНОМУ
АНАЛИЗУ. Комбинаторика. Элементы алгебры
логики. Теория графов: Учеб, пособие. — М.:
МФТИ, 2000. — 100 с.
ISBN 5-7417-0154-Х
Включены задачи и упражнения, связанные с курсом лекций по
одноименной дисциплине, читаемой студентам факультета приклад-
ной математики и экономики в первом семестре.
Сборник может быть использован в учебном процессе для подго-
товки семинарских занятий, заданий, экзаменационного материала и
как источник проблемных задач.
УДК 519.95
ISBN 5-7417-0154-Х
© Московский физико-технический институт
(государственный университет), 2000
© Журавлев Ю.И., Флеров Ю.А.,
Федько О.С., Дадашев Т.М., 2000
СОДЕРЖАНИЕ
ПРЕДИСЛОВИЕ..........................4
Глава I. КОМБИНАТОРНЫЕ МЕТОДЫ ДИСКРЕТНОЙ
МАТЕМАТИКИ ................................5
§ 1.	Комбинаторные задачи о числе функций, слов в алфа-
вите и размещений объектов по ячейкам при различных
ограничениях..................................5
§ 2.	Биномиальные и полиномиальные коэффициенты,
производящие функции для них.................. 11
§ 3.	Разбиения и размещения. Рекуррентные соотношения. 33
§ 4.	Логические методы комбинаторного анализа. Принцип
включений-исключений. Системы представителей
множеств.....................................54
Глава 2. ЭЛЕМЕНТЫ АЛГЕБРЫ ЛОГИКИ...........61
§ 1.	Функции алгебры логики и способы их задания.61
§ 2.	Функционально замкнутые классы........67
Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ...............76
§ 1.	Основные понятия теории графов...........76
§ 2.	Пути и циклы в графе. Связность......... 82
§ 3.	Эйлеровы и гамильтоновы пути и циклы.....86
§ 4.	Деревья..................................91
§ 5.	Ориентированные графы...„.'..1...'....   96
3
ПРЕДИСЛОВИЕ
Сборник предназначен для студентов первого курса фа-
культета прикладной математики и экономики МФТИ.
Включены задачи и упражнения ио комбинаторике, элемен-
там алгебры логики, теории графов. Представление о содер-
жании сборника даст оглавление.
Среди задач и упражнений выделены две группы. Первая
ориентирована на первоначальное знакомство с предметом п
содержит, в частности, теоремы и утверждения, рассматри-
ваемые на лекциях и семинарах. Их решение необходимо для
начального освоения дисциплины.
Решение задач, отмеченных знаком «*», потребует от сту-
дентов определенных (в некоторых случаях значительных)
усилий. Эти задачи - повышенной трудности, предназначены
для достаточно глубокого изучения комбинаторики, теории
графов и их связей с другими разделами курсов математики,
информатики и их приложений.
Несколько слов о структуре сборника. Каждая из грех его
глав разделена на параграфы. В каждом параграфе задачи
имеют двойную нумерацию: i.j, где i - номер параграфа, j -
номер задачи внутри параграфа. Ссылки на параграфы имеют
вид § u.v, где и - номер главы, v - номер параграфа внут-
ри главы, па который дается ссылка.
4
ГЛАВА I
КОМБИНАТОРНЫЕ МЕТОДЫ
ДИСКРЕТНОЙ МАТЕМАТИКИ
§ 1. Комбинаторные задачи о числе функций, слов в
алфавите и размещений объектов по ячейкам при
различных ограничениях
1.1. 1) Даны множества X, Y, причем |Х1 = п, 1У1 = т.
Сколько существует функций/: X —> У ?
2)	Каково число слов длины п в алфавите из т букв?
3)	Сколькими способами можно разместить п различ-
ных объектов по т различным ячейкам?
4)	Установить соответствие между постановками за-
дач 1), 2), 3). Охарактеризовать это соответствие.
1.2. 1) Найти число инъективных отображений множества
X из и элементов во множество У из т элементов.
2) Сколько можно составить слов длины п без повто-
рений букв в алфавите из т букв?
3) Сформулировать задачу о размещении объектов по
ячейкам, соответствующую постановкам 1) и 2).
1.3.	Доказать, что число упорядоченных размещений п
различных объектов по т различным ячейкам равно
[т]" = т(т + 1)...(щ + п- 1).
1.4.	Доказать справедливость следующих соотношений:
[m]„ = (jn-n + 1) [7?1]л_ 1,
5
[т]п
т!
(т- и)!
[т]" = [т + и - 1]„,
[m]" = (т + п - 1) [т]"~ 1 .
1.5.	Пусть А - множество букв а1г ат, упорядоченных
так, что
< а2 < ... < ат .
Слово Х[Х2 ...х„ длины п в алфавите А - монотонное, если
XJ <х2< ... <х„.
Доказать, что число монотонных слов длины п в алфавите
из т букв равно [т]п/п!.
1.6.	Найти число способов представления целого положи-
тельного числа т как суммы п неотрицательных целых чисел
(задача Муавра).
1.7.	Доказать, что число различных подмножеств
л-элементного множества равно 2".
1.8.	В теории вероятностей рассматриваются комбина-
торные схемы, связанные с выбором к шаров из урны с п
шарами.
При этом шары могут различаться или нет, выбор шаров
может производиться с возвращением или без (вынутый шар
кладется обратно в урну или нет) и выбор может рассматри-
ваться как упорядоченный или нет.
Найти число способов выбора для следующих схем:
1)	неупорядоченный выбор с возвращением к шаров
из урны с п различными шарам;
2)	упорядоченный выбор с возвращением к шаров из
урны с п различными шарами;
3)	неупорядоченный выбор без возвращения к шаров
из урны с п различными шарами;
6
4)	упорядоченный выбор без возвращения к шаров из
урны с п различными шарами.
Установить соответствие схем 1) - 4) размещениям эле-
ментов по ячейкам и словам в алфавите.
1.9.	Сколько существует возможностей трижды вытащить
туза червей из колоды в 52 карты при пятикратном выборе
с возвращением?
1.10.	Пусть 5 = {1, 2, .... п]. Сколько можно образовать из
элементов 5 упорядоченных /'-выборок с повторением, упо-
рядоченных r-выборок без повторения, неупорядоченных
r-выборок с повторением, неупорядоченных r-выборок без
повторения?
1.11.	Найти насколько возможно простые решения сле-
дующих задач:
1)	Сколько четырехбуквенных слов можно образовать
из букв слова “ИНТЕГРАЛ”?
2)	Сколько имеется пятизначных чисел, которые де-
лятся на 5?
3)	Сколько двузначных чисел, у которых все цифры
четные?
4)	Сколько пятизначных чисел, у которых все цифры
нечетные?
5)	Сколько четырехзначных чисел можно написать
с помощью цифр 0, 1, 2, 3, 4, 5? Найти сумму этих чисел.
6)	Сколько есть трехзначных чисел, которые записы-
ваются с помощью цифр 0, 1, 2, 3, 4, 5 и делятся на 3?
7)	Сколько есть пятизначных чисел, которые одина-
ково читаются справа налево и слева направо?
8)	Сколько разных слов можно составить перестанов-
кой букв в слове “МАТЕМАТИКА”?
9)	Сколько различных делителей имеет число
а а
т =	... рпп , где pi - различные простые числа, не равные
единице, а, - некоторые натуральные числа?
7
1.12.	Сколько подмножеств множества {1, 2,	12} со-
держат по крайней мере одно нечетное число?
1.13.	Сколькими способами можно получить, 8 раз бросая
игральную кость,
-дважды 3,
-	дважды 4,
-	три раза 5,
- один раз 6?
(безразлично, в каком порядке).
1.14.	Сколько возможностей существует для того, чтобы
среди 30 человек оказался по крайней мере один, родивший-
ся 1 января?
1.15.	Доказать, что каждое целое положительное число п
может быть 2" ~ 1 - 1 различными способами представлено в
виде суммы меньших целых положительных слагаемых, если
два представления, отличающиеся хотя бы порядком слагае-
мых, считать различными.
1.16.	а) Сколькими способами можно упорядочить множе-
ство {1, 2, п} так, чтобы числа 1, 2, 3 стояли рядом в по-
рядке возрастания?
б) Сколькими способами можно упорядочить множе-
ство {1, 2, ..., п} так, чтобы каждое число, кратное 2, имело
номер, кратный 2, и каждое число, кратное 3, имело номер,
кратный 3?
1.17. а) Каково число матриц из п строк и т столбцов с
элементами из множества {0, 1}.
8
б) То же при условии, что строки матриц различны.
1.18. Доказать, что каждое целое положительное число
можно представить в виде суммы различных целых положи-
тельных слагаемых столькими способами, сколькими спосо-
бами его можно представить в виде суммы одинаковых или
различных, но нечетных слагаемых. Например, все возмож-
ные представления числа 6 посредством различных слагае-
мых будут:
6, 1 + 5,2 + 4, 1 + 2 + 3,
посредством нечетных:
1+5, 3 + 3, 1 + 1 + 1 +3, 1 + 1 + 1 + 1 + 1 + 1.
1.19.	Рассмотрим игру в “крестики-нолики” на трехмер-
ном кубе 8x8x8. Сколько можно указать прямых, на кото-
рых лежат 8 значков в ряд? Определите также количество
выигрывающих прямых для куба с ребром к в п-мерном про-
странстве.
1.20.	Образуем наборы по к чисел (аь ..., из множества
чисел {1, 2, ..., п}, разрешая числам а, повторяться. Для каж-
дого такого набора отметим наименьшее из а.
а)	Доказать, что сумма наименьших а,- во всех набо-
рах равна
1к + 2к + ... + пк,
п к
т.е.	X ш(а\,аг,...,ак)=^т.
т=\
б)	Вычислить количество ^-наборов (ai, ..., ак~) с ми-
нимумом > т.
в)	Вычислить количество ^-наборов (<2ь ..., ак) с ми-
нимумом = т.
9
1.21.	Пусть п и ^-фиксированные, положительные целые
числа.
Сколько существует последовательностей (Хь Х2,
подмножеств множества {1,2, и} таких, что
Xi пХ2п ... пХк = 0?
1.22*	. Пусть 151 = п и зафиксируем положительное це-
лое к. Сколько существует таких последовательностей
(Гь Г2, ..., Тк) подмножеств Т, множества 5, что
Т^ТгС ... с7)?
1.23.	Определить количество способов, расставить в по-
следовательность числа 1,2, ..., п так, чтобы при произвольно
выбранном первом числе появлению числа к в последова-
тельности предшествовало бы появление числа к - 1 либо
к + 1 (необязательно непосредственно перед ним). Например,
для /1 = 6 среди возможных последовательностей имеются
следующие: 4, 3, 5, 2, 6, 1 и 3, 4, 2, 1, 5, 6.
1.24.	а) Сколькими способами можно рассадить за круг-
лым столом п человек?
б)	Сколькими способами можно рассадить за круг-
лым столом п юношей и п девушек так, чтобы юноши и де-
вушки чередовались?
1.25*	. Пусть 1 < к < п. Привести комбинаторное доказа-
тельство того, что среди всех 2'1'1 разложений (упорядочен-
ных разбиений) числа п число к встречается слагаемым
(п - к + 3) 2п~к~2 раз. Например, если и = 4 и к = 2, двойка
встречается один раз в2 + 1 + 1,1+2 + 1,1 + 1+ 2 и дважды
в 2 + 2, всего пять раз.
1.26.	Доказать неравенства
10
1.27.	Сколько перестановок множества {1, 2, п} не
имеют циклов длины к (k > 1)?
1.28.	Пусть п - перестановка n-элементного множества
{1, 2,	и}. Сколько перестановок обладают тем свойством,
ЧТО 7Г (1) < 71 (2) < ... < 7Г (£)?
1.29.	Пусть {Вь .... В2] - слова в алфавите А = {Ь^ ..., Ьч}
такие, что никакое слово В, не содержит другое слово Bj в
качестве своего префикса, т.е. B.^Bj U ни для каких слов U в
алфавите А.
!В,1 = г = 1, ..., г,
Ц< 12< ... < 1г.
Тогда
§ 2. Биномиальные и полиномиальные
коэффициенты, производящие функции для них
Комбинаторные тождества
2.1.	Доказать, что число ^-элементных подмножеств
n-элементного множества А есть
11
п
'п} [n]fe _ п!
к, к\ к\(п-к)\
2.2. Доказать:
а) Ск
б) скп
__п к .
— ,
__z~i к । z-’ к 1
- Си_1 тС 1 .
п—1 п-1
2.3.	Доказать, что производящей функцией последо-
вательности биномиальных коэффициентов
С®, С^,..., С" является степень бинома, т.е.
fckxk =(1 + х)".
к=0
2.4.	Доказать с помощью комбинаторных рассуждений:
а) ХС^=2";
к =0
2.5.	Пусть X - множество п различных объектов и пусть
пь п2, пр - неотрицательные целые числа, удовлетворяю-
щие условию П[ + п2 +...+ Пр = п. Доказать, что количество
размещений п объектов по ячейкамУ!; Yp , каждая из кото-
рых содержит соответственно nlt п2, пр объектов, есть
12
nl
п,! п2!
О
п
п}, п2, п
	, если п, +-+ ... + п„ = п ,
t-------------------1	Z.	[}
... пр\
в противном случае.
2.6.	Доказать, что (xi + х2 + ... +хД” есть производящая
Г п
функция для	:
[пх,п2,...,пр J
п
ni,n2,...,nI, >0
п1 +п2 + ... + пр =п
пх,п2,...,пр
2.7. Доказать:
Г п >

13
2.8.	а) Сколько имеется четырехзначных чисел, у которых
каждая следующая цифра больше предыдущей?
б)	Сколько имеется четырехзначных чисел, у которых
каждая следующая цифра меньше предыдущей?
2.9.	1) Сколько рациональных членов содержит
разложение (\/2 + д/з)1 ?
2)	Выписать разложения в виде многочлена от х, у, z
для (х + у + z)3 И (х + у + z)4.
3)	Чему равен коэффициент при x2y’z2 в разложении
(х + у + z)7 ?
4)	Найти коэффициент при хкуг в разложении
(1+х + у)”.
5)	Найти коэффициенты при х17 и х18 в разложении
(1 +х5 + х7)".
2.10.	Сколькими способами можно разместить п
одинаковых шаров по т различным урнам:
а)	при отсутствии ограничений;
б)	при условии, что пустых урн нет;
в)	во второй урне (т > 2) к шаров;
г)	в первых к урнах соответственно а\, ..., ак шаров
(<2i+ ... + ак < и);
д)	в С-й урне не менее чем ак шаров {к = 1, 2, ..., т)?
2.11.	Найти число всех слов длины тп в п-буквенном
алфавите, в которых каждая буква алфавита встречается т
раз.
2.12.	1) Доказать, что Ср, Ср,..., делятся на р, если
р - простое число.
2)	Доказать, что разность ар - а при любом целом а
делится на р.
3)	Произведение любых т последовательных целых
чисел делится на т!
14
4)	Если кип целые положительные числа, то и
(Ли)!
----------целое число.
(Л!)пм!
5)	Чему равен наибольший общий делитель чисел
Cl >-.3	>-.5	2/t 1 q
2n> c2n> с2п •••’с2п
2.13.	а) Сколькими способами можно распределить п оди-
наковых монет между р лицами?
б)	Сколькими способами можно распределить п оди-
наковых монет между р лицами так, чтобы каждый получил
не менее одной монеты?
2.14.	а) Колода в 52 карты раздается 4 игрокам, каждому
по 13 карт. Сколько существует возможностей того, что у
одного игрока окажется:
1)13 карт одной масти;
2) 4 туза и 4 короля;
3)3 туза и 3 короля?
б) Игрок в бридж объявляет, что среди 13 его карт
есть туз. Подсчитать количество возможных случаев, когда у
него в точности 2 туза.
2.15. а) Сколько существует возможностей для того, что-
бы среди 6 человек в точности трое родились во вторник?
б) Пусть каждая из 5 семей состоит из 4 человек.
Предположим, что 6 из этих 20 человек больны скарлатиной.
Сколько существует различных вариантов для следующих
случаев:
1)	карантину должны быть подвергнуты в точности
2 семьи,
2)	в точности 3 семьи,
3)	не менее 3 семей,
4)	все семьи?
15
2.16.42 пассажира садятся в автобус, который делает
7 остановок. Подсчитать количество всех возможных ситуа-
ций при условии, что на каждой остановке выходят в точно-
сти 6 человек.
2.17. 1) Задача о книжной полке. На книжной полке стоят
п книг, из которых выбираются к книг. Сколько существует
способов выбора, если среди выбранных книг никакие две не
стояли рядом?
2)	Сколько существует последовательностей из п
символов “0” и к символов “1” таких, что две единицы не
стоят рядом?
3)	Сколько существует способов выбора к различных
точек из п точек, расположенных на окружности так, чтобы
никакие две выбранные точки не являлись соседними?
2.18. а) Даны п элементов 1, 2, ..., п, расположенных в
строку, причем любые элементы из множества
{!, ! + 1, ..., i+a} считаются “а-соседями”. Доказать, что чис-
ло различных способов выбора к элементов, из которых ни-
какие два не являются “а-соседями”, равно
'п-ак + а
б)	Доказать, что соответствующее число (см. п. а))
для п элементов, расположенных по окружности, дается со-
отношением
п (п-ак^ п(п-ак - Р
п-аку к J к ( к-1 ,
2.19.	Дан алфавит {а\, ..., ап}. Сколько из него можно со-
ставить слов длины 2п, содержащих каждую букву ровно два
раза, причем так, что нигде в слове рядом нет двух одинако-
вых букв? Например, для п = 2 возможны только слова
^1^2^1^2	4?2<2l^2^1*
16
2.20.	а) Число монотонных слов длины п в алфавите
R, 1/?1 = г, равно числу п-подмножеств произвольного
(г + п - 1)-множества.
б) Показать, что число монотонных слов длины п,
содержащих все символы некоторого алфавита R, 17?! = г,
равно числу (г - 1)-подмножеств (и - 1)-множества.
2.21.	Путем классификации различных слов длины п в
алфавите из п символов показать, что
2.22.	Доказать с помощью комбинаторных рассуждений
тождества:
Jt=O
л2/7 + Г
.2к >
= 4‘
п- 2
5)
к-2
к-2
+... + (п-к + 1)
'к-2У
к-2
+ 2
п
к
17
6)
где п = min {a,b}.
2.23.	Доказать, что для целых положительных п и
т, п > т
,	к ] т
к-т \ J
2.24.	Дать комбинаторные доказательства тождеств:
т
\ 7
п — ЗЛ (п — 3\ (п — 3
+ 3	+
т — 1	I т — 2 т — 3
\ J \ J \	/
^п+ р
4)
Р
? А:=о\^дт-^
18
5)
'п- р
\у(п ¥“р
J А:=Ок™~^Д к
V р + к-\Л
2.25.	Разложение п есть представление числа п в виде
упорядоченной суммы положительных целых. Если разло-
жение содержит в точности к слагаемых, то оно назы-
вается ^-разложением.
(п-П
1)	Доказать, что существует	^-разложений п и
[к-1)
2п ”1 разложений п.
2)	Сколько целых положительных решений имеет уравне-
ние X] + Х2 + ... +Х*. = П ?
3)	Сколько целых неотрицательных решений имеют
уравнение X] + х2 + ... + хк = п,
неравенство X] + х2 + ... + хк < п ?
4)	Сколько разложений числа 23 состоят лишь из чисел
2 и 3?
5)	Найти число разложений числа п > 1, имеющих четное
число четных слагаемых.
2.26.	а) Доказать, что число ^-сочетаний из п символов
с повторениями
'п + к-1'
п-1
б) Привести
дества
комбинаторное доказательство тож-
2.27.	1) Пусть 1X1 - п, \Y\ = т. Найти число способов, ко-
торыми можно выбрать функцию f: X —> У, а затем линейно
упорядочить каждый блок кообраза/. (Для любого у е У со-
19
соответствующий блок кообраза задается непустым
множеством/-/(у) = {х е X : fix) - у}.) Элементы множеств X
и Y различны.
2)	Сколько таких способов существует при условии,
что функция/сюръективна?
3)	То же задание, что и в п. 1), но элементы
множества X неразличимы. Дать ответ в виде конечной
суммы.
2.28.	а) Показать, что
И )

б)	Доказать, что
V т2 = — п(п -1)(2н + 1) .
л 6
т=0
п
в)	Вывести формулу для У, т'1 .
т=0
2.29.	Найти простые выражения для сумм:
п
а)	Хйг;
/=1
б)	X2n4z2;
/=1
и (
в) Е
т
к
2.30.	Найти минимальное значение суммы
\ Р
р
п}
к
п,.
1
к
п2
к
20
2.31.	а) Доказать формулу
Получить отсюда выражение для
2.32.	Показать, что
2.33.	Вычислить значение суммы
£(-!)* •
к=1 Iк)
2.34.	Доказать следующие соотношения:
1)	(? + ,)"= £с„‘р‘.Л‘;
к=0
2)	f/’+d =ЁСЛН kL;
з)	[p^]n=i^[P]k[qrk-,
k=Q
4)	(p + q)(p + q + n)n^ =
= 1скпр(р + к/-1 q(q + (n-k^n-k+1
k=0
21
Будем рассматривать кратчайшие пути из левого нижнего
угла (0, 0) в правый верхний угол (т, п), проходящие по сто-
ронам решетки.
1)	Найти число различных путей из (0, 0) в (т, п).
2)	Группируя пути по месту попадания на верхнюю сто-
рону, получить тождества
3)	Подсчитывая количество путей в соответствии с тем,
где они пересекают вертикальную линию, получить тож-
дество
4)	Группируя пути по месту пересечения с наклонной
линией, получить тождество
2.36, а) Доказать тождество

Vn)
23
б) Пусть
Воспользовавшись взаимно обратными соотношениями, по-
лучить тождество
bfll(n) =
2.37. Доказать тождества
п
а) X
к=0
'п V к — 1
Л Л т
Л	т
= 2п~т £ (-2)*
)	к=0
' п
т-к
3.38. а) Пусть
т
snm = £ (-1/ , .
к=0 Н
Используя одно из соотношений
(
$пт ~ $ п—1, т ~ $ п-1, т-1 — $ п, т-1 + (— О
и равенства
Sn0 =1, Snl =-(п-1), показать, что

т — п
т
т J
б) Дополнительной к сумме Snm из
п. а) является
сумма
24
т
1 п, т+1
$ птт+\ ~	1) — <5^0 •
Таким образом
Т„,т =5„0 +(-1)”+'["-1'.
к т >
2.39. Доказать:
п
ъ X
fc=0
^2^ + 0
п
4) X
fc=0
= и(2и-1)22""2-—и = 2,3,...;
25
Vi
к=0 к
к
к
к=0 V
(2п-1'\
= п(2п + 1)22п~1 -[2п + 1]2
, п = 2,Ъ,...;
п
2.40. Доказать следующие равенства:
а)
б)
в)
= (т + 1)
п А ( п
+ т
т + 1 т
к J \ J
^m + 2V п
< 2 )[т + 2
п
т + 1
'т+г-к''
т—к
т+г-к
, g = min(m, г)
2.41. Доказать следующие равенства:
п
'n + l'} (. п Л
+
т + 1 т + 1
к 7 к 7
а)
в)
q = min(m, г).
26
2.42. а) Доказать, что число сочетаний по к элементов из п
элементов, среди которых имеется р элементов одного типа и
по одному элементу из q других типов (спецификацию этих
элементов будем обозначать символом р\ч, р + q = п), равно
q
к
к-1
к-p }
б) Доказать, что число сочетаний по к элементов из п
элементов спецификации 2ml"'2m
С (2"V-2m ;£)=£
равно
1тГ\(п — 2m - к А
к-2г
2.43. Введем обозначения
” (n-kVk\
^пт
Доказать, что
а,г0=и + 1; д2„,„=1;
^0=°; Ь2п,п=2п + 1’
Доказать:
а)
ап1 =
bnl =
С
3
2
” к
Л=Ок т
б) Вывести рекуррентные соотношения:
а = а , + b , , т — 1, 2,
пт п-},т	’
Ь„,п =b„-X,m +«л-1,т-р т = 1’ 2— •
в) Доказать тождества
апт
Y к 1
^пт
^н + 1^	„ к п —к
< 2m J *=о1 т
т > 0.
27
2.44.	Обобщение задачи 2.43.
Рассмотрим сумму
к
пт(.Р)
к=0 I
т
т+ р у
1)	Получить рекуррентные соотношения:
апт (Р) — ап—1, т(Р^ + ап—1, т—1 (Р	—
— ап-Л, т(Р) + ап-1, т(Р ~ V
2)	Из этих соотношений и тождеств, доказанных
выше, получить
” (п-к}
апт(р} ~ Z-i
к=0 к
3)	Используя
тождества, показать, что
fп + р
к
т
п +1
2т + р +1
т + р
т
формулу свертки и доказанные
=1
к
т
amSn-p} =
= z
2k<m-n+py ‘
4)	В частности,
соотношения
<2n + P
2m
т
'2п'
2т
т + 1
п-р + 1 + 2к
А г )
показать, что выполняются
п
к=0 к
к2т + 1 'yfn + k'}
к=о [ V + l
( 2т + 1\( п + к\
2к
2т
2т
2.45. Доказать следующие равенства:
т
1) 2Р
Р)
К
= X (-1)
к=0
mV 2т-2ку
к р-2к
\ А г /
, К = min т,
£
2
28
I) 2Р = X (-1/
л=о
р-кУ(2р-2к
к Д р-к
,Р =
Р_
2
3)
' 2п
2т
\ /
т
= £4*
к=0
гт + к\( п
2к т + к
\ Л /
4)
(2п + 1А ™ fr2m + lf/n + A;Y п А
= > 4 -------
2т > k—Q	2& + 1 2к > т + к
2.46. Доказать тождества:
1) £/сС„Л =^2"-’;
к=\
2) ^к(к-1)С^ =п(п-1)2п^2;
к=2
3)
п 1	1
У Y-rf =—L_(2«+1
1с=0 к +1	п +1
-1);
4)	£(-1)'г"гС„г = У(-1)"-1-гС^;
г=к	г=0
„ ь fO, тФп,
5)	У (-1/ пСпкСкт= ’
к=п	[кт = п
6)	1(-^-1С‘Ск^_1Ч=Ск_т;
i=0
к
7) Х(-1)'С„к-;С'
i=0
{-1)к,2Ск'2, к - четно,
О, к - нечетно;
29
8) £(-l)*-pC* =
£=1
О, п Ф 1,
1, п = 1;
9)Х
' п + Р
• к \ к-I
i=Q \
Ю) ±
1=0
i
к
И) XZ£Z
i=l
п+1
па
- а---------------
(1-я)2	1-а
\-ап
п
12) ^2”~г z2 - 3 • 2п+| -(л2 +4л + 6);
к (
в) jN
i=0 I
= к
к
к-\
14) (l + 2 + ... + л)2 = I3 + 23 +...+ z?3 ;
15) Скп +С^+1 + ... + Ск+т -
к 4‘ 1	_z~* к +1
^п+тМ	’
м+1	? _
„п+т + \, К ~П,
< п,
16) cO-C,’+C2-...+(-l)wC
О, т = п,
( \\тст
(-1) сп-1
, т<п;
30
f 1, n = 3k,
17) d’,, - c'2n4 + c22 ,_2 -...+(-1)” c;; = o, n = зк+1,
[ -1, n = 3k -1;
1S) (С„° )2 - (C’’)2 + (C-')2 - ... + (-1)” (C„n)2 =
(	0, n - нечетно,
n- четно;
19) %-1)кСкпС'^ ^(-1)ПСГП-
к
2.47.	Доказать следующие равенства:
г < г - Р
I к-\
\ /
2)Е
3)
= (-1/
вещественное, к - целое Ф 0;
(г + к-\\
г - вещественное, п - целое > 0;
г - вещественное, к - целое;
к
п
к
к
'п Vп- кУ
^[т-к^
п, т, к - целые;
Г p + q}
31
'q + k
к \k J
(-1)^
Q
n-p
' p+q+X''
m + n + 1
2.48.	а) Пусть Q - некоторое множество, содержащее п
элементов, a Ai, .... Ак - подмножества этого множества.
Набор подмножеств Aj, Ак называется коллекцией
Шпернера, если ни одно из множеств А], Ак не является
частью другого. Доказать, что к < С^п/21.
б)	Пусть Q - множество, состоящее из п элементов,
А/, ...,Ак- коллекция Шпернера этого множества, |Д71= о,
\А2\ = /2, ..., 1АД = ц. Тогда
в)	Пусть хп - число различных коллекций Шпернера
для множества из п элементов. Доказать следующие
неравенства:
2Т" < хп < Стт" , где тп=С[пп/2].
2.49.	* Рассмотрим произведение Х;Х2 ... хп. Сколькими
способами можно расставить скобки так, чтобы вычисление
значения произведения стало однозначно определенным?
32
§ 3.	Разбиения и размещения. Рекуррентные
соотношения
3.1.	а) Доказать, что числа Стирлинга первого рода s(n, к)
удовлетворяют следующему рекуррентному соотношению:
s(n, к) - s(n, к - 1) - ns(n, к),
s(n, 0) - 0,
s(n, п) = 1.
б)	Показать, что начало таблицы значений чисел
Стирлинга первого рода имеет следующий вид:
s(n, к)	Л = 0	1	2	3	4	...
п = 1	0	1	0	0	0	
п = 2	0	-1	1	0	0	
п = 3	0	2	-3	1	0	
п = 4	0	-6	11	-6	1	
•						
3.2.	Чему равно число разбиений множества п объектов на
т классов? Найти число Стирлинга второго рода S(5, 3).
3.3.	Доказать, что число сюръективных отображений мно-
жества X, |Aj = п на множество Y, 1У1 = т равно m\S(n, т), где
S(n, т) - число Стирлинга второго рода.
3.4.	Доказать, что числа Стирлинга второго рода удовле-
творяют следующему рекуррентному соотношению:
S(n + 1, к) = S(n, к-1) + kS(n, к),
5(0, 0) = S(n, 1) = 5(1, 1)= 1,
S(n, 0) - 0, п > 0.
3.5.	Доказать тождества
1)	тп = ^C^k\S(n,k),
к=1
33
2) /и" =У
п!
nl!n2!...nm!’
где суммирование распространяется на все упорядоченные
разбиения п на т слагаемых: п = И/+ ... +пт, п;> 0 - целые
числа. Получить отсюда представление чисел Стирлинга
второго рода.
3.6.	Доказать формулу
хП =	,
Л=1
где S(n, к) - числа Стирлинга второго рода.
3.7.	Доказать рекуррентное соотношение для чисел Стир-
линга второго рода
п
S(n +1, т) = ^C^S(k, т-1).
к=0
3.8.	Доказать рекуррентное соотношение для чисел Бел-
ла Вк
п
Bn+i = ^C^Bk,BQ=\,n>0.
к=0
3.9.	Доказать справедливость следующих представлений
чисел Стирлинга второго рода:
1 к-1
a) S(n^) = ~y(-l)lClk(k-i)n ,
k'-i=0
(сравните с задачей 4.4);
где к] + к2 + + кп = к; 1 'ki +2.'к2 + ... + л ~кп — и.
34
в)5(п,к)=	...kbk .
(b},...,bky.
к
^b, =n-k
3.10.	1) Доказать, что для каждого т > 0 матрица чисел
Стирлинга первого рода lls(n, Л)П, 0 < п, к < т, есть обратная
матрица для матрицы чисел Стирлинга второго рода IIS(h,
Л)||, 0 < п, к < т, т.е.
т
Y'Stm, k)s(k,n) = 3mn,
k=Q
™	fl, т = п,
\s(m,k)S(k,ri}=8mn, где 8тп=\
10, mtn.
2)	Пусть а0, ah ... иЬ0, bt, ... — две последовательности
вещественных чисел. Доказать эквивалентность следующих
двух соотношений:
п
bn = YlS(n’ к)ак’
к=0
п
ап =
k=Q
3.11.	Показать, что
^8(п, к^В/^ = 1, н = 0,1,...,
к=0
где s(n, к) - числа Стирлинга первого рода, Вк - числа Белла.
35
3.12.	1) Обозначим через с(п, к~) число перестановок п эле-
ментов с к циклами. Найти с (6,2).
2)	Доказать следующее рекуррентное соотношение
для с(п, к):
с(п, к) = с(п - 1, к - 1) + (и - 1) с(п - 1, к).
3)	Показать, что производящая функция для с(п, к)
имеет вид:
п
сп(х) = ^с(п, к)хк = х(х + 1)...(х + и-1) = [х]".
к=0
4)	Показать, что имеет место следующее соотноше-
ние между числами Стирлинга первого рода s(n, к) и с(п, ку.
с(п, к) = ( -l)t+'1 s(n, к) = I s(n, к)|.
5)	Показать, что число перестановок п элементов,
каждая из которых состоит из к циклов, отличных от единич-
ных, равно
П (п}
d(n,k)=£ ' l(-l)J с (n-j, к-j).
j=OV)
3.13.	Проверить, что
1)	S(n,2) = 2n 1 -1;
2) S(n, и —1) =
и-2
3) S(n, n — 2) = У, (n - к -1)
k=l I 2 >
n>3;
4) S(n, n-2) =
36
5)	S(n, п-З) =
6
6)	Показать, что в общем случае
А (н)
5(лД)=2^ • b(n-j,k~j) или
7=0 V У
п
j + k
S(n, п — к)= У,
7=0 I
b<J + k, j),
где Ь(п, к) удовлетворяет рекуррентному соотношению
b(n + 1, к) - kb(n, к) + nb(n - 1, к - 1) .
3.14.	Обозначим через f(n, к) число последовательностей
Я1Й2 ... ап положительных целых чисел, таких, что первое
появление числа i > 1 встречается раньше, чем первое появ-
ление числа i + 1 (1 < i < к - 1), и при этом максимальное
встречающееся число есть к. Пусть, кроме того, каждое чис-
ло 1, 2, ..., к встречается по меньшей мере один раз. Выразить
fiji, к) через числа Стирлинга.
3.15.	Дать комбинаторное доказательство того, что число
разбиений множества {1, ..., п}, в которых ни одна пара по-
следовательных чисел не оказывается в одном блоке, есть
число Белла В(п - 1).
3.16.	Пусть Хи У- конечные множества, |Х1 = п, 1У1 = г.
1)	Доказать, что число отображений f :X—XY различ-
ных типов (произвольное, инъективное, сюръективное, биек-
тивное) при различных условиях на различимость-
неразличимость элементов множеств X и Y задается табли-
цей:
37
\ Тин о го- \Лражения Огра- ничспии на множества х	Произволь- ное	Инъектив- ное	Сюръек- тивное	Биек- тивное
Эл-ты Х-различ. У-различ.	гп	[г]„	r!S(n, г)	г!
Эл-ты Х-неразл. У-различ.	[г]" п\	1 r 1 1 гг 1		1
Эл-ты Х-различ. У-неразл.	YS(n,k) к=1	1, если п < г, 0, если п > г.	S(n, г)	1
Эл-ты Х-неразл. У-неразл.	ip(n,k) к=1	1, если п< г, 0, если п > г.	P(tl, г)	1
Здесь S(n, к) - число Стирлинга второго рода, Р(п, &) - число
разбиений п на/: частей:
к
п =	Л(>0, Aj >Лз
i=l
2)	Дать интерпретацию приведенных отображений в
терминах размещений объектов по ячейкам.
3.17.	Чему равно число таких (упорядоченных и
неупорядоченных) распределений п объектов по г ящикам,
что в точности г - к ящиков являются пустыми?
3.18.	1) Число способов размещения п различных объектов
по т различным ячейкам, когда объекты в ячейках
упорядочиваются и нет ограничений на число объектов в
каждой из них, равно
[т\п = т(т +1)...(m + п -1) = nl
2) При условии, что все ячейки должны быть заняты,
это число равно
т + п-
п
38
Г-IJ
3.19.	Число способов размещения п объектов
спецификации (щ«2 • •) по т различным ячейкам, когда
объекты в ячейках упорядочены, равно произведению
п\
-------. D(n, т),
где D(n, т) -- число способов размещения п одинаковых
объектов по т различным ячейкам.
3.20.	Число способов размещения п одинаковых элементов
по т одинаковым ячейкам при условии отсутствия пустых
ячеек р(п, т) равно числу разбиений п сомножителей на т
групп, а число способов размещения без указанного
ограничения равно
р(п, 1) + ... + р(п, т).
3.21.	Пусть Р(п, к) - число разбиений п на к частей, Q(n, к)
- число разбиений п на к различных частей. Например,
<2(8, 3) = 2; соответствующие разбиения есть 1+2 + 5 и
1+3+4. Доказать с помощью комбинаторных рассуждений,
что
3.22.	Обозначим через D(lb' ...nhn,ld' ...г'1') - число
размещений элементов спецификации 1Л| ... п'’" по ячейкам
спецификации 1J| ... rd’ .
39
Доказать:
1) £>(1”,Г) = гп-
2) Z>(n,lr) =
3)	D(l", г)=	S(n,k);
Л=1
3.23.	ПустьD(lb> ...nh" ,\di ...rdr) - число размещений
элементов спецификации l61 ... nb" по ячейкам спецификации
ld' ... rdr, при которых нет свободных ячеек.
Доказать:
1)	£>(l'1,f) = r!5(n, г);
2)D(n,lr)= л ;
3)	D(\n, r) = S(n,r);
4)	D(n, г) = Р(п, г);
3.24.	Обозначим D(n, т) число сюръективных
отображений f: X—YY множества X на множество Y, 1X1 =
и, Y =lml (число способов размещения п различных объектов
по т различным ячейкам при условии занятости всех ячеек).
Доказать, что
1)	(Z>(n, ) + 1)т = тп, где (D(n, ))^ sD(n,ky,
40
3.25.	Пусть f(n, т, s) - число размещений п различных
объектов по т различным ячейкам при условии, что каждая
из т ячеек может содержать не более 5 объектов.
Вывести рекуррентные соотношения
1) /(«, т, s') =
Показать далее, что
3)	/(«, т, s) = тп, п < 5;
4)	f(s +1, т, s) = ms+^ - т;
5)	f(s + 2, т, s') = ms+^-т-[w]2(5 + 2);
3.26. Пусть h(n, т, г) - число размещений п различных
объектов по т различным ячейкам при условии, что в
каждую ячейку попадает не менее г объектов.
Доказать рекуррентное соотношение:
h(n, т, r) = mh(n — l, т, г) + т
^п — Р
Р"1,
h(n-r,
т — 1,
г)
3.27.	Число возможных размещений п объектов
спецификации (Р 2^2...) по т различным ячейкам равно
41
т 1
кm + l'f2 (т + 2^3
3
спецификацию объектов и
через U([n],m) = mkl
- число размещений п
т различным ячейкам без
2
\ /
Обозначим [п] = (l^12^2...)
т + С^2
2
/
объектов спецификации [п] по
дополнительных ограничений. Обозначим далее через 7?([п],
т) число размещений при отсутствии свободных ячеек.
1)	Показать, что
т
£/([«], т) = У
к=0
т
/?([п], т — к)
п
или, что то же самое
U([n], т) = (/?([«], ) + 1)т, где	)еВД,£).
И обратно,
7?([и],т)=Х(-1/
к=0
U([и], m-k) = (U([и],
)-1)т,
где £/*([„], ) = t/СИД).
2)	Пусть [п] = (1Р?), т.е. имеется по одному объекту
У каждого из р типов, а остальные типы (в спецификации s )
содержат более одного элемента.
Тогда показать, что
U(lp s, т) = mU(l^-1 s, т),
R(lps, m) = mR(\p~^s,m) + mR(]p~ls, m-1).
3)	Подобным же образом показать для спецификации
[и] = (2^ У), в которой имеется по 2 однотипных элемента
каждого из р типов, а остальные типы содержат более двух
элементов, что
42
U(2ps,m) =
rm + P
2
U(2p~Xs,m),
R(2ps, m) =
m-k + P
2
к
2
-mk +
(Последнее соотношение основано на тождестве
т + 1
2
4)	Применяя для спецификаций обозначения,
аналогичные предыдущим, показать
Для доказательства последнего использовать тождество:
fm-k + q-1}	m+q - i-1}
= £(-1)7
I « J 7=0 I J
3.28.	Обозначим через L(n, т) число способов размещения
п одинаковых объектов по т различным ячейкам при
условии, что ни одна из них не остается пустой. Показать,
что
43
3.29.	Пусть заданы объекты спецификации (pq) и т раз-
личных ячеек, R(pq, т) - число размещений этих объектов по
т ячейкам. Показать, что
R(pq, т) =
3.30.	Число способов размещения к взаимно неатакующих
ладей на доске, имеющей форму прямоугольного треуголь-
ника со стороной q - 1, является числом Стирлинга второго
рода S(q, q- к).
3.31.	По определению, разбиением целого положительно-
го числа п называется набор целых положительных чисел,
сумма которых равна п, а порядок чисел в расчет не прини-
мается.
Докажите следующие утверждения:
1)	Число разбиений с неравными частями равно числу
разбиений, все части которых нечетны.
2)	Для каждого числа, большего 1, существует столько же
разбиений с четным числом частей, сколько и с нечетным.
3)	Число разбиений целого п > 0, в каждом из которых
точно т частей, равно числу разбиений п на части, наиболь-
шая их которых равна т.
4) Число разбиений целого п > 0, в каждом из которых
число частей не превышает к, равно числу разбиений, в кото-
рых нет частей, больших к.
5) Число разбиений целого п, каждое из которых содер-
жит точно к частей, равно числу разбиений числа п +
(к)
Л,
с к
различными частями.
6) Число разбиений целого п > 0, в котором нет частей,
превосходящих к, равно числу таких разбиений числа п + к, в
каждом из которых имеется в точности к частей.
44
3.32.	а) Показать, что число разбиений произвольного
«-множества на 2 блока равно 2”~! -1.
б)	Дать формулу для числа разбиений произвольного
«-множества на 3 блока.
3.33.	Пусть /’(«, г) - количество разбиений числа « на г
частей для всех « > г > 1. Доказать:
Pin, 1) = Р(п, «) = 1;
Р(п, г) = Р(п - г, 1) + Р(п - г, 2) + ... + Р(п - г, г).
3.34.	Пусть Р(х) - такой многочлен степени «, что Р(х) = 2х
длях = 1, 2, ..., п+1. Чему равняется Р(п + 2)?
3.35.	Сколькими способами можно уплатить за покупку
стоимостью сто рублей монетами достоинством в 1, 5, 10, 20
и 50 рублей?
3.36.	Доказать, что число, равное произведению « раз-
личных простых сомножителей, может быть 5(«, т) способа-
ми представлено в виде произведения т сомножителей.
3.37.	Пусть it = {Bi, ..., Вр}-разбиение множества 5 такое,
что IBJ = ... = L6pl = к. Пусть/: S —> S - отображение такое,
что если а, b е В,, то f(a),f(b) e Bj. Сколько существует раз-
личных таких отображений?
3.38.	Каково количество представлений натурального
числа « в виде суммы к неотрицательных целых слагаемых
« = Ш1 + «22 + ••• + тк
при условии, что i-e слагаемое может принимать значения в
интервале от а, до /л включительно:
а, < «I, < h, i - 1, ..., к .
45
Два представления (m,,тк) где (т',т'к) совпадают
тогда и только тогда, если
= т{, т2 = т2, . ., тк = т'к.
3.39.	Показать, что п знаков, каждый из которых либо
“плюс”, либо “минус”, можно (р (п) способами расположить в
последовательность, в которой нигде не окажутся рядом два
минуса, где
<р(0) = 1, <р(1) = 2,
(р (и) = (р (п - 1) + (р (и - 2), п > 1.
3.40.	Числа Фибоначчи определяются рекуррентной
формулой Fo = 0, Fi = 1, Fn = Fn.{ + F„_2 при и > 2.
Таким образом, последовательность чисел Фибоначчи
имеет вид
{0, 1, 1,2,3,5,8, 13,21,...}.
Доказать:
1)	Fn_xFn+x-F^ = (-!)”;
2) Fk । Fnk;
всегда равно числу Фибоначчи.
3.41.	Выразить через числа Фибоначчи:
1)	Число разложений п на части, превосходящие 1.
2)	Число разложений п на части, равные 1 или 2.
3)	Число разложений п на нечетные слагаемые.
4)	Число последовательностей (Ej, е2, ..., Е„) нулей и
единиц таких, что
Ei < Е2 — Ез S Е4 > Е5 < ... .
5)	Значение суммы ^х^х2 ...х^ , где суммирование
м —1
производится по всем 2 разложениям числа п :
+ х^ + ... + хк — 11 .
46
6)	^(2Л1 1 -1)...(2Хк 1 -1), где суммирование про-
м —1
изводится по всем 2 разложениям числа п:
X, + Х2 + ... + Хк =П .
3.42.	Пусть /(л, к) - число ^-подмножеств множества
{1,	п}, не содержащих ни одной пары последовательных
целых чисел. Доказать, что
Ги-Л + Р
к
/
б)	/(и, к) = Fn+2 > гДе F] - число Фибоначчи.
к>О
a) f(n,k) =
3.43.	Пусть q(n, к) - число Л-подмножеств множества
{I, ..., п}, не содержащих ни одной пары последовательных
целых чисел и пары (1, п) (из п точек, расположенных на
окружности, выбираются к точек так, чтобы среди них не
было соседей).
а) Доказать:
п (п-к'
п-ку к
б) Положим Gn — У,д(и, к), п>1.
к>0
Докажите справедливость следующего рекуррентного со-
отношения:
Gi=1,G2=3, g„=g„_1+g„_2.
3.44.	Упорядоченные разбиения принято называть компо-
зициями. Обозначим через с(и, т) - количество упорядочен-
ных разбиений целого положительного числа п, имеющих в
точности т частей (упорядоченное и?-разбиение).
47
1)	Доказать, что с(п, т) =
' п — 1У
2)	Вывести рекуррентное соотношение для с(и, q)\
с(п, q) - 2с(п-\,q) + c(n-q-\,q) = 8Хп - 8q+Xn .
11, т = п,
Здесь 8тп
О, т Ф п.
3)	Пусть с(п, т, q) - количество композиций (упоря-
доченных разбиений) числа п, имеющих в точности т частей,
из которых ни одна не превосходит q.
Доказать, что
с(м, т, q) =
c(n-qk, т-к, q - V).
Указание.
Производящей функцией для c(n,m,q) служит
ст(х, g) = (x + x2 + ... + x9)m =^с(и, т. q)xn .
4)	Пусть C(n, q) - количество композиций (упорядо-
ченных разбиений) числа п, ни одна из частей которых не
превосходит q. Доказать, что для С(п, 2) имеет место рекур-
рентное соотношение
С(п, 2) = С(п - 1, 2) + С(п - 2, 2),
т.е. С(п, 2) - числа Фибоначчи.
Вывести рекуррентное соотношение для С(п, <?):
С(п, q)-2C(n-\,q) + C(n-q-\,q) = 8Хп -8q+Xn .
3.45.	Показать, что число упорядоченных г-разбиений
числа п, имеющих тип I*1 ... пк" (т.е. каждое i появляется в
разбиении к, раз)? равно
г\1(к\ !&2-- -кп\), если п =	к,, г = ^к^ .
1=1	1=1
3.46.	Число представлений числа п в виде суммы слагае-
мых (с учетом их порядка), из которых каждое может при-
48
нимать одно из значений 1, 2, п, равно коэффициенту при
хп в разложении выражения
/	,	2 ,	, П\П
(X + X + ... + X ) .
3.47.	Диаграммой Ферре разбиения а : п\ + ... + пг целого
положительного числа п на г неупорядоченных слагаемых
(где, как всегда, «| > пг> ... > пг, П] + и2 + ... + п, = и) называ-
ется массив п точек из г строк, в z-й строке которого распо-
ложено п, точек.
Если а - разбиение, то сопряженное с ним разбиение а*
получается пересчетом точек по столбцам диаграммы Ферре.
Если а- а*, то разбиение а- самосопряженное.
Пусть а : щ + ... + лР Показать, что тогда
1)	а*: щ	. + и*, где п* =\{i\ni> j} I.
2)	(а*)* - а . В частности, (р : а —»«* - взаимно одно-
значное отображение на множестве разбиений.
3)	Число самосопряженных разбиений числа п равно
числу таких разбиений числа п, которые состоят из неравных
нечетных слагаемых.
3.48.	Если перестановка содержит к} циклов длины 1, Л2
циклов длины 2, ..., то ее принято называть перестановкой
класса (к) = (кь к2, ...). Тот же смысл имеет принятое в теории
разбиений обозначение (к) = l^12^ 2....
а)	Пусть c(ki, кг, , к„) - число перестановок из п эле-
ментов класса (Л), т.е. kt - число циклов длины i в каждой
рассматриваемой перестановке. Показать, что
\к{ кх\2к2 к?\...nk,ikn\ ’
где к} + 2кг + ... + пк„ = п .
б)	Отметим, что каждая перестановка относится к не-
которому цикловому классу, поэтому сумма всех с(к\, ..., кп)
равна п\. Получить отсюда известное тождество Коши:
49
\к'2кг ...пкпкх\к2\...кп\
где сумма берется по всем неотрицательным целым числам
кх, кп таким, что к\ + 2к2 + ... + пкп = п.
3.49.	Обозначим через PER(h}, число перестановок
типа l?22fc2 ... п’п некоторого «-множества N и через
Р(Ь}, ...,Ьп) - число разбиений такого же типа множества N
(т.е. в разбиении содержится ровно Е блоков мощности /).
Доказать, что
[ «!
a) PER(t\, ..., /?„) = <	lb2! ..bn! 1^2^ ... n"
если
п
n=^J<bk ,
к=1
О в остальных случаях.
О в остальных случаях.
п
3.50.	Пусть Ап - [п\к - число всевозможных
k=Q
инъективных отображений в некоторое «-множество.
Проверить, что
а)	Ап = пАп_х +1;
б)	Ап=п\£(1/к\).
<t=o
3.51.	Пусть /(«, к) - число перестановок множества
{1, ...,«}, у которых ровно к инверсий. Доказать
1)	/(«, 0) = 1, /(«, !) = «-!, /(«, к) = 0 для всех к > « ;
50
n
2
2) 1(п,
-k) = I(n, k)
3)	/(n, k) = I(n, к -1) + I(n -1, к) для к < n ;
4)	вывести явные формулы для 1(п, к), к = 2,3, 4, 5.
3.52.	а) Обозначим через а(п, к) число таких слов длины к
в алфавите из п символов, в которых любые две соседние
буквы различны; через а*(м, к) обозначим число таких слов, в
которых на первом месте стоит данный элемент. Показать,
что
а(п. к) = па*(п, Л);
а*(п, к) = (п - 1) а*(п, к - 1)
и, следовательно
а(п, к) = (п- 1) а(п, к - 1), к> 1;
а(п, к) = п(п - 1)к'\ к > 0.
б)	Рассмотрим те слова из предыдущей задачи, в ко-
торых не содержится т(т = 2, 3, ...) одинаковых букв под-
ряд. Число этих слов обозначим через а^(п, к).
Показать, что
а(т\п, к) =
= (п -1) {а(т) (п ,к -1) + а(т) (п,к - 2) +... + ам (п ,к - т+1)}
3.53.	Показать, что
W" =Х|Ц«Л)|[*Ь, гДе
4=0
\L(n, к)\ - числа Ла (без знака), задаваемые формулой
к\ к-1
3.54.	Число Ла Цп, к) (со знаком) определяется тождест-
вом
[—-*]„ = ^L(.n,k)[x]k .
к=0
51
1)	Доказать, что
„ п\(П-0
L(n,fc) = (-1)" —
Ц*-1}
2)	Доказать, что
п
к)[-х]к;
к=0
(-l)"L„>0.
3)	Доказать, что
—,	с	[О, т Ф п,
/ , Е(и, k)L(k, т) — опт, где оп т — s
,	1, т = п.
к	1
4)	Доказать, что
= s(n, да).
5)	Вывести рекуррентную формулу
L(n + 1, к) = -(« + к) Цп, к) - L(n, к - 1) .
3.55.	Последовательность вещественных чисел {ап} назы-
вается логарифмически вогнутой, если > an_jan+1 для
всех п > 2. Показать, что при фиксированном к последова-
тельности
< П >, {5(п, к)}, {^(п, к)\ }, {|L(n, Л)|} логарифми-
V Jj
чески вогнутые.
3.56.	Пусть { рп(х) I п е No} и { qn(x) I п е N} - последова-
тельности полиномов с коэффициентами связи ап к, Ьп к, т.е.
(nzN0),
к=0
Рп(х)=^Ьп,к^к(хУ (n^No).
к=0
Если и0, vo- ... - вещественные числа, то
52
п	п
vn = Yan,kuk ^ur,= Ybn,kvk (nt N0) 
k=0	k=0
3.57.	Доказать справедливость обращений:
а)	биномиальное обращение:
(пУ	J (п}
Vn=X <=> М» = У (-1)" . V>
к=0	)	к=0	\ у
б)	обращение Стирлинга:
п	п
vn = ^s{n,k)uk <=>ип= ^S(n,k)vk ;
к=0	к-й
в)	обращение Ла:
п	п
vn = YL(n’ к^ик ^“п=	•
£=0	к=0
3.58.	а) Пусть М(п) - максимальное значение к, при
котором S(n, к) имеет максимальное значение. (S(n,M (п)) =
= max{S(n,k)}) Тогда последовательность {S(n, к)} - одного
к
из следующих двух видов:
S(n, 0) < S(n, 1) < ... < S(n, М(пУ) > S(n, М (n)+l) > ... > S(n, к)’,
S(n, 0) < S(n, 1) < ... < S(n,M{n) - 1) = S(n, M(n)) > ... > S(n, k).
Иными словами, последовательность {S(n, к) I к = 0, ..., n}
- унимодальна для всех п е No.
б) Более того, М(п)=М(п - 1) + £(м), где Е(п) = 0 или 1.
§ 4.	Логические методы комбинаторного
анализа. Принцип включений-исключений.
Системы представителей множеств
4.1.	Пусть имеется N объектов и п различных свойств а\,
аг, , ап. Каждый из объектов может обладать любым из
этих свойств (в любом наборе) или не обладать никаким из
53
свойств. Пусть No - число объектов, не обладающих ни
одним из свойств ап, a N(at ,а, ) - число объектов,
обладающих свойствами а, ,..., а (и, быть может, некото-
Ч '	lk v
рыми другими).
Доказать справедливость формулы включений-исключе-
ний:
N0 =N~	+
l<i<n 1<i< j<n	l<i< j<k<n
+ ... + (-l)nN(ab...,an).
4.2.	Пусть некоторый объект из имеющихся N (см. зада-
чу 4.1) обладает ровно р свойствами. Сколько раз он будет
учтен в сумме
N (к ) =	У N (а : , а ; , а . ),
\	/	\ it ’	12 ’	5	I ь -1 1
1 < I] < i2 < ... < ц < п
еслир >к!
4.3.	1) Задача о числе беспорядков. Найти число переста-
новок й/йэ ... ап элементов множества {1, 2, ..., л} таких, что
<2i i, i = 1,2, ..., п.
2)	Обобщение задачи о числе беспорядков. Рассмот-
рим все и! перестановок п элементов. Сколько различных
упорядоченных наборов можно составить из т перестановок,
взятых изо всего множества перестановок? Сколько можно
составить таких наборов, состоящих лишь из беспорядков?
4.4.	Если IX I = п, IY I - т, то число сюръективных ото-
бражений множества X на множество Y, т.е. функций/: X —» Y
таких, что/(Х) = Y, равно
т-1
1=0
4.5.	Пусть N = (т) - число объектов, обладающих в точно-
сти т свойствами из возможных п свойств. Доказать, что
54
N=(m)=	(-l)k C™+kN(m + к), где
k=0
N(k) =	^N(ai}, ...,aik), k = l,n.
l<i, <i2<...<ik<n
4.6.	Пусть N> (m) - число объектов, обладающих не менее
чем т свойствами из п. Доказать, что
п—т
«г(И)= Y	.
к=0
4.7.	Показать, что
W) = £с>=(щ),
т=к
W) =
т=к
4.8.	Пусть А\,	А,,~ подмножества конечного множества
А. Для каждого подмножества Т множества {1, п} поло-
жим:
Ат = Q Af, А0 - А,
ieT
Sk = ^1 Ат I, для 0<к<п.
ГЛ=к
Доказать, что
Sk -	• • • +(-1)"к $п - 0, 0<к<п.
4.9.	1) Пусть а и п - целые положительные числа. Опреде-
лить количество тех из чисел 1, 2, п, которые делятся на
а.
2)	Пусть а, Ь, с, .... к, I - взаимно простые целые по-
ложительные числа. Сколько из чисел 1,2, ..., п не делится ни
на одно из этих чисел а, Ь, с, к, 17
55
3)	Пусть р, q, г, ... - различные простые делители
числа п. Чему равно число чисел, меньших п и взаимно про-
стых с ним?
4)	Найти количество целых чисел, не превосходящих N и
не делящихся ни на р, ни на q, ни на 5.
4.10.	Пусть а, Ь, с, ..., к, I- неотрицательные целые числа.
Доказать, что
тах(а, Ь, с, ..., к, I) -
= a + b + c + ...+k + l- min(a, b) - min(a, с) - ...
- min(i, Г) + min (a, b, с) + ... + min(a, b, с, ..., к, I).
4.11.	Пусть дано п элементов, занумерованных числами
1, 2, ..., п. Будем называть «узлом» наличие пары соседних
элементов (z, i + 1), i - 1, 2, ..., п - 1 в выборке объёма к из
этих п элементов. Рассмотрим fin, к, j) - число й-подмно-
жеств из n-множества с j узлами.
1)	Доказать, что
(Y-lYn-Zz+P
/(n, k,j) =	.	.	.
I j Л k~j J
2)	Пусть свойство п(-, 1 < i < п - 1 состоит в том, что к-
подмножество п-множества {1,2, ..., п} содержит узел
(z, i + 1). Доказать, что
4.12.	Пользуясь методом включений-исключений, дока-
зать, что

= Х(-1)
7=0
Y-iYrc-J
к j kk~j
4.13.	Доказать тождества:
56
4.14.	Задача мажордома. Сколькими способами можно
рассадить за круглым столом п пар враждующих рыцарей
так, чтобы никакие два врага не сидели рядом?
4.15.	Доказать, что
п!=
к=\
4.16.	Билеты маркируются шестизначным номером. Билет
является «счастливым», если сумма первых трех цифр
совпадает с суммой последних трех цифр. Подсчитать
количество «счастливых» билетов.
4.17.	Пользуясь методом включений-исключений,
получить формулу для числа перестановок из п элементов,
содержащих к циклов длины 2 (при этом характер и
количество циклов длины, отличной от 2, во внимание не
принимаются).
4.18.	Назовем две перестановки 2м-элементного
множества 5 = {ah а2, ..., ап, Ь}, ...,Ь„} эквивалентными, если
одна может быть получена из другой переменой мест
последовательных элементов вида аД или Например,
перестановка а2Ь3а3Ь2ахЬ\ эквивалентна самой себе и
перестановкам
ci2a2b3b2(2 \b\,
a2b3a3b2b}ar,
57
a2a3b2b2b\ai.
Сколько существует классов эквивалентности?
4.19.	Задача о супружеских парах. Сколькими способами
можно расположить за круглым столом п супружеских пар
так, чтобы мужчины и женщины чередовались и никакие
двое супругов не сидели рядом?
4.20.	Теорема Холла о различных представителях.
Подмножества 51, .S'2, •••> Sn имеют систему различных
представителей (с.р.п.) тогда и только тогда, когда среди
элементов любого конечного числа к множеств .S', имеется по
меньшей мере к различных элементов (иными словами, мно-
жество S: uS, u...uS: состоит не менее чем из к эле-
*1 Ч	1к
ментов для всех к = 1, 2, ..., п).
4.21.	Постройте с.р.п. или покажите, что такой системы не
существует для следующих наборов множеств:
а) {1,2}, {2,3}, {3,4}, {5,2}, {4, 6}, {1, 5};
б) {1,2,4}, {2,4}, {3,4,5}, {4,6}, {5, 2,3}, {1,3,5}.
4.22.	Два разбиения множества 5
5 = Ai'uA2'U...'uA„ и .S'--Bi'uB2'<J...'uBll
тогда и только тогда имеют систему общих представителей,
когда любые т из множеств В, содержатся не менее чем в т
из множеств А,, т<п.
4.23.	Пусть А -	- матрица инцидентности для
58
такова, что количество единиц в каждой строке и каждом
столбце равно фиксированному числу г (1 < г < т).
Доказать, что существует с.р.п. для M(S).
4.24.	Пусть А и В - два конечных множества, к > 1 -
натуральное число. Между А и В установлено такое
многозначное соответствие, что каждому элементу
множества А соответствует ровно к элементов множества В и
каждому элементу из В соответствует ровно к элементов из
А. Доказать, что между А и В можно, не добавляя новых
связей, установить взаимно однозначное соответствие.
4.25.	А =	|| - п X т матрица, тогда перманент матрицы
А есть выражение
per А = Уд|; а,. ... а . ,
'	Zu 1 Vi 2/2 nj„ ’
где суммирование производится по всем перестановкам
1, 2, ..., п, если т - п, и по всевозможным размещениям
объёма п из т различных элементов.
Пусть А = |ру||, 1=1, 2, ..., п; j = 1, 2, ..., т, п < т
есть матрица инцидентности множеств Хь Хг, Хп,
являющихся подмножествами множества X = {хь ..., хт}:
1,	х; e X*,
J
O,Xj £ Xj .
Тогда для числа R(Xi, Х„) систем различных
представителей семейства {Xz, 1 < i < п} имеет место
равенство
tf(Xj,..., Хп') = регА.
4.26.	Пусть семейство конечных множеств {Xz, г = 1, п}
таково, что |Xj|<|Х2|, и удовлетворяет условию
существования с.р.п. Тогда для числа с.р.п. справедлива
оценка
59
R(Xx,X2,...,Xn)> П	(|X7|-/ + 1).
0<y<min(n, |Xj|)
4.27.	Пусть d = |Xi| < |X2| < ... < |X„|.
Тогда число с.р.п. семейства {X„ 1 < i < п} оценивается
следующим образом:
dl, d < п ,
60
ГЛАВА 2
ЭЛЕМЕНТЫ АЛГЕБРЫ ЛОГИКИ
§ 1.	Функции алгебры логики и способы их задания
1.1.	Указать выражения всех элементарных булевых
функций, использующие только
а)	штрих Шеффера;
б)	стрелку Пирса.
1.2.	Пусть о и * некоторые из связок {&, v, I, ф}.
Выяснить, какие из соответствующих элементарных опера-
ций алгебры логики обладают свойствами:
- коммутативности, т.е.
х * у = у * х ;
- ассоциативности, т.е.
х * (у * z) = (х * у) * z;
- дистрибутивности (операции о относительно опера-
ции * ), т.е.
X о (у * Z) = (X о у) * (х о z).
Здесь х, у, z - логические переменные.
1.3.	Доказать справедливость простейших правил:
- де Моргана
х v у = х  у;
х  у = х v у;
- поглощения
х V ху - X.
1.4.	На основании каких тождеств алгебры логики можно
получить следующие теоремы теории множеств:
a)(Xu y)uZ = Xu(KuZ);
б)	(1иУ) = ХиУ;
61
в)	X - X ?
1.5.	Какие теоремы теории множеств можно получить из
тождеств алгебры логики:
а)	(х & (х v у)) —> у = 1;
б)	х & (xv у) = х;
B)(x&y)-^(xvy) = l?
1.6.	Указать существенные и несущественные (фиктив-
ные) переменные следующих функций:
1)Л(хьХ2,хз) = (00111100);
2)/2(хь х2, хД = (xi -> (xi v х2)) х3;
3)Л(х;, ..., Хп) = (X! V Х2) + ... + (хп-1 V Хп) + (хп V Х0 . .
1.7.	(Леммы о разложении функции алгебры логики по
первой переменной).
Пусть/(xi, хп) - функция алгебры логики от п перемен-
ных. Тогда
1)/хь ...,ХП) = Х1 /(1,х2, ...,Xn) v Xi ДО, х2, ...,хп);
2)ДХ1, ..., Хп) - (xi v/(0, х2, ..., Хп)) A (xj v/(l, х2, ..., Хп)).
1.8.	Пусть х, - булевы переменные, <т,е {0, 1}, i - 1, ..., п.
Доказать, что х/1... х°п =1 тогда и только тогда, когда
х,=<т„ ( = 1, ..., п.
1.9.	Пусть/(xi, ..., хп) - произвольная функция алгебры ло-
гики от п переменных. Справедливы следующие разложения
по к переменным:
1) в дизъюктивную нормальную форму
/(xb...,xn)= v xf'xj2 ...xakk f(px,...,ok,xk+x,...,xny,
(^,...,<7 J:
<7,6 {0,1}
2) в конъюнктивную нормальную форму
62
f(xl,...,xn) =
= v (xf1 v%22 v...vx^ V /(<?],..., (Ук,Хк+Ъ. ..,x„)).
<т,е{0,1}
1.10.	Доказать, что произвольная функция алгебры логики
от п переменных может быть представлена в
а)	совершенной дизъюнктивной нормальной форме:
/(х1,...,хи) = v хр-...-x^, где/(хь ...,х„) Ф 0;
/(<71.<т„>1
б)	совершенной конъюнктивной нормальной форме:
/(х1,...,хл) = л (xf1 vxj2 v...vx^), где
(O-J,...»а-„):
Яи, ...,х„) Ф 1 .
1.11.	Представить в виде д.н.ф. следующие функции:
1)	(Х1 + х2) = (хг(х2 -> XI ));
2)	(т, | х2) | (xi | х3);
3)	xi 1х2 =х3;
4)	(xi—> (х2 -»х3|х1 ))+х3;
5)	(х1 = (х2|хз))-»(х1+х2).
1.12.	Представить в виде д.н.ф. и к.н.ф. следующие функ-
ции:
а)	xi~>(х2—>(хз~>..>(хп-1—>х„))...);
b)	Х1 = (х2 = (xi = (х3 = (хз = х2)))).
1.13.	Записать в виде к.н.ф. функцию от п переменных,
принимающую значение «0» только на наборах из всех нулей
и всех единиц.
1.14.	Доказать, что
63
х„) = (х,	/(1, х2,..., х„))	(х, -> f(Q, х2,..., х„)).
1.15.	Доказать, что
хл) =	->	(<> ^(х22 —->
(<ть..., ст*):
<тге{0,1}
7(<Т1,...,<Т*,ХЛ+1,...,ХЛ )...).
1.16.	Найти дизъюнктивное, конъюнктивное и имплика-
тивное разложение по переменным хь х2 следующих функ-
ций:
1)	Xi—>(х3х2 =xi);
2)	х3 v (xj—^х2) VX3X4 ;
3)	(Х2+Х3) — (Х!Х2 V Xj х4).
1.17.	Показать, что
V (х; + Х;) = (х1 v х2 v...vx„)a(x1 vx2 v...vxn).
повеем
'*7
1.18.	Найти число элементарных конъюнкций от п пере-
менных.
1.19.	Определить число элементарных конъюнкций от п
переменных, обращающихся в единицу в точке с координа-
тами ai, ап.
1.20.	Найти к < п, при котором можно получить наиболь-
шее количество различных элементарных конъюнкций ранга
к от п переменных.
1.21.	Сколько элементарных конъюнкций от п перемен-
ных имеют длину I, ki< I < кг, klt кг - некоторые константы,
не превосходящие п, к\ < к2^
64
1.22.	Найти среднее число д.н.ф., реализующих одну
функцию алгебры логики.
1.23.	Обозначим через 7Г у(м) число элементарных конъ-
юнкций функциихп). Доказать, что
Зл
шах 7Г у (и) < с —= ,
f	у/п
где с — некоторая константа.
1.24.	Сколько имеется различных функций от п перемен-
ных, принимающих значение 1 на тех и только тех наборах, в
которых содержится ровно к единиц ?
1.25.	Сколько имеется различных функций от п перемен-
ных, принимающих значение 0 на наборах, в которых содер-
жится ровно к единиц ?
1.26.	Найти число функций от п переменных, имеющих к
единичных точек.
1.27.	Сколько имеется функций от п переменных, сохра-
няющих одновременно «1» и «О» ?
1.28.	Подсчитать число симметрических функций от п пе-
ременных.
1.29.	Определить количество функций от п переменных
..., хп), которые принимают значение «1», если
X] + Л'2 + ... + Хп = 1,
а в остальных случаях могут принимать произвольные значе-
ния.
1.30.	Дать оценку снизу для числа функций, существенно
зависящих от всех своих аргументов.
1.31.	Пусть 1// (и) - число функций, существенно завися-
щих от всех п переменных. Доказать, что
65
о n
22
1.32.	Подсчитать число различных функций/(xb х2,  • xn),
не зависящих существенно отхь
1.33.	Доказать, что функция, представленная полиномом
Жегалкина, существенно зависит от всех входящих в него
переменных.
1.34.	Построить структуру на множестве всех элементар-
ных конъюнкций от п переменных, в которой конъюнкции А
и В связаны отношением А > В (изображается стрелкой,
идущей от А к В), если
В = AC, С^О, С* 1.
Выделить в этой структуре слои, состоящие из конъюнкций
одинаковой длины, и найти количество элементов в слое
максимальной длины.
1.35.	1) Чему равно число всех вершин «-мерного единич-
ного куба В° ?
2) Чему равно число вершин куба Вп, содержащих
ровно к единиц ?
1.36.	Подсчитать число различных возрастающих путей на
6-мерном единичном кубе В6 от вершины (0, ..., 0) к вершине
(1,..., 1).
1.37.	Доказать, что n-мерный единичный куб Ва можно
представить в виде объединения С^"/2] попарно непересе-
кающихся возрастающих цепей.
1.38.	1) Доказать, что в n-мерном единичном кубе Вп
существует и! попарно различных возрастающих цепей дли-
ны и.
2) Показать, что число попарно различных возрас-
тающих цепей длины п, содержащих фиксированную верши-
ну (аь ..., лп) из n-мерного единичного куба такую, что
66
и
^а^к, равно к\(п-к)\ .
;=1
1.39.	Пусть (Oi, Ок) - заданный набор, о; е {0,1},
j=l, к. Множество всех наборов (аь ..., пп) из Вп, у
которых a- =<5j, j = l,...,k, называется гранью куба Вп.
число к - рангом этой грани, число п-к- размерностью этой
грани.
Доказать следующие утверждения:
1)
2)
3)
4)
5)
число всех граней ранга к куба В" равно
общее число граней куба Вп равно 3";
число граней размерности к, содержащих заданную
вершину (а1; ..., ап~), равно ;
число граней размерности к, содержащих заданную
грань размерности I, равно ;
\к~1,
число к - мерных граней, пересекающихся с данной
I - мерной гранью куба В", равно
min(/t, 0
7=0
' п-1У
к~ j
X
§ 2 Функционально замкнутые классы
2.1.	Доказать, что следующие системы функций являются
функционально замкнутыми классами:
1)	монотонные функции;
2)	линейные функции;
3)	самодвойственные функции;
4)	функции, сохраняющие единицу;
67
5)	функции, сохраняющие ноль;
6)	функции, сохраняющие ноль и единицу;
7)	функции от одной переменной.
2.2.	Пусть/(xi,	хп) - функция алгебры логики, <р(х) по-
лучена из f(xn) путем отождествления всех переменных:
ф(х) =/(х, ...,х).
Определить если
1)	/(Г)еТ0\Т1;
2)	/(Г)б$;
3)
2.3.	Указать, к каким классам Поста относятся следующие
элементарные функции алгебры логики:
х, х, Xj
Х2 , X] —> Х2 , Xj = Х2 , Xj + Х2 5 Xj I Х3 , 1, 0.
2.4.	Пусть даны нелинейная функция от двух переменных
и отрицание. Доказать, что суперпозициями из них можно
получить все нелинейные функции от двух переменных.
2.5.	Теорема о функции, двойственной к суперпозиции
функций. Пусть функция <р(хь ..., х„) получена как суперпо-
зиция функции /,/ь
<p(xj ,..., хп) — f (f[ (xj 1, ..., X|fJ| ),..., fm (xml, ..., xinnm )) •
Тогда
<р*(х1,...,х„) = /*(/Л-),...,/«()),
т.е. функция, двойственная к суперпозиции функций, есть
суперпозиция двойственных функций.
2.6.	Найти функции, двойственные следующим функциям:
а)	(X! +х2)-(х2 =хД;
б)	(Х!|х2)->х3.
68
2.7.	Найти конъюнктивную нормальную форму функций,
двойственных функциям
Xj v х2 v *3 >
И + х2 + х3 •
2.8.	Представить в виде конъюнктивной нормальной фор-
мы функцию, двойственную функции
Xj • Х2 • Х4 V Х2 • Х3 V Xj • Х2 V Х3 • Х4 V Х3 • Xj • Х2 .
2.9.	Пусть К - множество функций алгебры логики, К* -
множество всех тех функций, которые двойственны к функ-
циям из К. Доказать, что К является замкнутым классом то-
гда и только тогда, когда замкнут класс К .
2.10.	Доказать, что для монотонных функций справедливо
разложение
/(X],...,XW) = XW •/(-И>->-*и-1> I)v/(X],...,X„_], 0).
2.11.	Доказать, что достаточным условием монотонности
функции от п переменных является представление ее в виде
дизъюнктивной нормальной формы, не содержащей отрица-
ний.
2.12.	Выяснить монотонность следующих функций:
а)	Х]Х2 v Х]Х4 VX]X2 vx2X4X5 VX3XJX5;
б)	Х]Х3 VX2X3X4 VX1X4.
2.13.	Доказать, что функция, двойственная монотонной
функции, монотонна.
2.14.	Доказать что если формулы fn(p равносильны, то и
двойственные им формулы/* и (р* также равносильны.
2.15.	Привести определение функции, являющейся:
а)	немонотонной;
б)	нелинейной;
в)	несамодвойственной.
69
2.16.	Показать, что если функция/(хь .х„) удовлетворя-
ет любым двум из четырех условий:
1)	feS; 2) f&M-, 3) < А2 >; 4) <а2 >, - кроме ком-
бинаций условий (2,3) и (2,4), то она удовлетворяет и двум
другим условиям.
По определению функция /(хр х„) удовлетворяет ус-
ловию <Д2> (или <а2> ), если у любых двух наборов, на кото-
рых f принимает значение 0, существует общая единичная
(или нулевая) координата.
2.17.	Сколько функций от двух переменных являются
1)	монотонными;
2)	самодвойственными;
3)	линейными;
4)	сохраняют ноль;
5)	сохраняют единицу?
2.18.	Найти число следующих функций от п переменных:
1)	линейных;
2)	самодвойственных;
3)	сохраняющих ноль;
4)	сохраняющих единицу;
5)	дать нижнюю и верхнюю оценки числа монотон-
ных функций.
2.19.	Сколько имеется функций от п переменных, сохра-
няющих одновременно «1» и «О» и являющихся линейными?
2.20.	Сколько имеется монотонных функций, не принад-
лежащих
То ПТ)?
70
2.21.	Найти количество самодвойственных функций, не
принадлежащих одновременно ни одному другому классу
Поста.
2.22.	Сколько функций принадлежит только классу То и не
принадлежит ни одному другому классу Поста?
2.23.	Определить количество функций от п переменных,
принадлежащих
1)	Гп5пГ0 nTt ;
2)	Ln 5;
3)	L n T} ;
4)	LmM;
5)	Ln Го;
6)	5 m Tq ;
7)	S n Ti ;
8)	5 n To n Г, .
2.24.	Заполнить таблицу, указав в клетках количество
функций от п переменных, принадлежащих пересечению со-
ответствующих классов Поста.
То 71 L S М
Го |	|	|	|	|
тг
L
S
м
2.25.	Указать те классы Поста, которые полностью пере-
крываются объединением остальных классов.
71
2.26.	Найти все функции от п переменных, принадлежа-
щие одновременно всем классам Поста.
2.27.	Лемма о несамодвойственной функции.
Пусть /(Хр ..., xn)£S. Тогда из нее операциями суперпо-
зиции с функциями х и х можно получить константы 0 и 1.
2.28.	Лемма о немонотонной функции.
Пусть /(Хр..., xa)tM. Тогда из нее с помощью опера-
ций замены переменных и суперпозиции с константами 0 и 1
можно получить функцию х .
2.29.	Лемма о нелинейной функции.
Пусть f<£L, используя функции 0, 1, х с помощью опе-
рации суперпозиции можно получить функцию х  у.
2.30.	Основная лемма теоремы Поста.
Пусть система функции алгебры логики F содержит
функции: /о g То, Д g 7], Д-g 5, Д-g М. Тогда из функций
этой системы операциями суперпозиции и замены перемен-
ных можно получить константы и функцию х .
2.31.	Теорема Поста (критерий полноты).
Для того чтобы система функций F была полна в Р2, необ-
ходимо и достаточно, чтобы она не содержалась полностью
ни в одном из пяти замкнутых классов Д, Тх, L, S, М, иными
словами, чтобы для любого класса Д, Д, L, S, М среди
функций системы F нашлась хотя бы одна функция, ему не
принадлежащая.
2.32.	Определение. Множество К' функций алгебры логи-
ки, содержащееся в замкнутом классе К, называется пред-
полным классом в К, если
1)	К'не является полной системой в К-,
72
2)	для всякой feK \ К' справедливо
Доказать, что всякий предполный класс К' в замкнутом
классе К замкнут.
2.33.	Любой замкнутый класс функций алгебры логики в
Р2 обязательно содержится целиком хотя бы в одном из клас-
сов То, Ti, L, S, М.
2.34.	Доказать, что Тй,Т\, L, S, М - предполные клас-
сы в Р2.
2.35.	Среди замкнутых классов функций алгебры логики в
Р2 существует только пять предполных: То, Ть L, S, М.
2.36.	Из любой полной в Рг системы функций можно вы-
делить полную подсистему, содержащую не более четырех
функций.
2.37.	Определить, полна ли система функций:
1)	F = {x-^y, х->(у Z)};
2)	F = {x-y, x = yz}\
3)	F = {(01101001), (10001101), (00011100)};
4)	F = (SnM)u(L\M)u(T0\S);
5)	F = {0,1, x + у = z, xy}\
6)	F = {1, x + y, x v y};
7)	F = {0,1, x-(y = z) vx(y + z)};
8)	F = {0, x+y + z,(x-»y)|(y = z)};
9)	F = {x—> у, x + у + z};
10)	F = {x-> y,x + y + z};
11)	F = {x & у + z, (x —> y) + z};
12)	F = {(x-> y) >1 (y = z), (x|xy) -» z};
13)	F = {xy + z,(x + y) + z};
73
14)	F = {0, (х|ху) —> z};
15)	F = {x v (x + y) v z, (x = y) = z, xy + z}',
16)	F = {O, 1, x + у + z, xy v yz v xz};
17)	F = {x v (x + y) v z, (x = y) = z, xy + z};
18)	F = {(x v y) • (x v y),(x + y) = z,xy v xz v yz};
19)	F = {(x —> y) 4, (y s z),(x|xy) —> z}.
2.38.	Показать, что {x = у, x + у} не является полной сис-
темой. Перечислить все возможные способы расширения
этой системы до полной путем присоединения одной функ-
ции, зависящей не более чем от двух переменных.
2.39.	Определить, образуются ли функционально замкну-
тые классы в результате применения следующих теоретико-
множественных операций к функционально замкнутым клас-
сам:
1)	объединение;
2)	пересечение;
3)	дополнение;
4)	разность.
2.40.	Какое из отношений включения имеет место для
классов Кх, Кт-
а)	Кх =[xv(x + y)vz], К2 =[xv у, х + у];
б)	К\ = [ху, х + у], К2 = [х у, х = у] ?
2.41.	Выразить, если это возможно, основные элементар-
ные функции алгебры логики через суперпозиции:
1)	дизъюнкции и отрицания;
2)	конъюнкции и отрицания;
3)	импликации и отрицания.
74
2.42.	Привести пример полной системы, состоящей из од-
ной функции от п переменных (н > 2).
2.43.	Привести пример функции от четырех переменных,
образующей полную систему в То.
2.44.	Выразить следующие функции алгебры логики через
штрих Шеффера:
а)	(%! ~^x2Wx3;
б)	xj v(x2 +х3);
в)	xj х2 х3.
2.45.	Указать алгоритм построения обобщенных функций
Шеффера от двух и трех переменных.
2.46.	Определить количество обобщенных функций Шеф-
фера от п переменных. Как изменяется относительное число
этих функций с возрастанием п!
2А1. Пусть (и) - число штрихов Шеффера от п пере-
менных. Доказать, что
1,га ^=1
п—>°° 2 2"	4
2.48.	Из системы следующих функций алгебры логики
выделить все подсистемы, которые являются базисами:
хрх, vx2, X] &х2,х1|х2,х1 +х2,Х] -»х2, X] = х2.
2.49.	Определить верхнюю и нижнюю границы для коли-
чества функций, содержащихся в базисе класса монотонных
функций.
75
ГЛАВА 3
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
§ 1.	Основные понятия теории графов
1.1.	В конечном графе число вершин нечетной степени
четно.
1.2. Указать матрицу инциденций, матрицу смежности,
списки инцидентности для следующих графов:
1.3.	Пусть Gn - граф со множеством вершин V = { vb
vn}, в котором вершины v; и Vj смежны тогда и только
тогда, когда i и j взаимно просты. Изобразите графы G4 и G8
и найдите их матрицы смежности.
Покажите также, что если т < п, то Gm является подгра-
фом Gn,
1.4.	Покажите, что графы Gi и Gz изоморфны, а графы С?з
и G4 не изоморфны.
76
1.5.	Доказать, что с точностью до изоморфизма сущест-
вуют ровно 4 простых графа с тремя вершинами и одинна-
дцать - с четырьмя вершинами. Сколько можно построить
простых графов с 5 вершинами?
1.6.	Как определить понятие изоморфизма между ориен-
тированными i-рафами? Доказать, что существует 16 попарно
неизоморфных простых ориентированных графов с тремя
вершинами.
1.7.	Пусть А = II II - т х п - матрица инциденций про-
стого графа с п вершинами и т ребрами (я,; = 1, если
вершина v, инцидента ребру е„ в противном случае = 0).
Доказать, что сумма чисел, стоящих в любом из столбцов
матрицы, равна степени вершины, соответствующей этому
столбцу. Что можно сказать о сумме чисел, стоящих в любой
из строк?
1.8.	Пусть G - граф со множеством вершин {vb ..., vn] и
пусть/(G) - многочлен от переменных хь ...,х,„ определен-
ный формулой
/ (G) = х°' х^1... х°” П(х - х. )a,i.
i<j
В этом равенстве произведение берется по всем таким па-
рам I, j, что i < j; dy равно числу ребер, соединяющих v, и
Vj, а о, равно числу петель в вершине г,. Доказать, что мно-
гочлен ДС) определяет граф G с точностью до изоморфизма.
Каким графам соответствуют делители /(G)?
Определение 1. Реберным графом L (G) простого графа
G называется граф, вершины которого взаимно однозначно
сопоставлены ребрам графа G, причем две вершины в L (G)
смежны тогда и только тогда, когда соответствующие им
ребра смежны в G.
77
1.9.	Показать, что реберные графы графов, изображенных
на рисунке, изоморфны. Найти выражение для числа ре-
бер графа L (G) через степени вершин графа G.
Определение 2. Граф, у которого все вершины имеют од-
ну и ту же степень, называется регулярным графом. Плато-
новы графы - графы, образованные вершинами и ребрами
правильных многогранников - Платоновых тел: тетраэдра,
куба, октаэдра, додекаэдра и икосаэдра.
1.10.	Нарисовать платоновы графы. Показать, что Плато-
новы графы - регулярные графы.
Определение 3. Пусть множество вершин графа можно
разбить на два непересекающихся подмножества Vj и V2
так, что каждое ребро в G соединяет вершину из Г. с верши-
ной из У2, тогда граф G называют двудольным графом.
Определение 4. Пусть даны два графа Gi = (V1; Ej) и G2 =
= (V2, Е2), причем множества V] и V2 не пересекаются; тогда
объединением G, о G2 графов Gi и G2 называется граф со
множеством вершин V, о Г2 и семейством ребер
Е,	и Е2: G = Gi u G2 = (V, u V2, Et о Е2).
Определение 5. Можно образовать соединение G, + G2
графов Gj и G2, взяв их объединение и соединив ребрами
каждую вершину графа Gj с каждой вершиной графа G2.
1.11.	Проверить, что операции соединения и объединения
коммутативны и ассоциативны.
78
Определение 6. Дополнением G графа G - (V, Е) назы-
вается простой граф со множеством вершин V, в котором две
вершины смежны тогда и только тогда, когда они не смежны
bG.
1.12.	Доказать, что дополнение полного графа является
полностью несвязным графом и наоборот; дополнение регу-
лярного графа регулярно.
1.13.	Нарисовать все регулярные графы степени 3 с не бо-
лее чем 8 вершинами.
1.14.	Привести примеры (когда это возможно):
1)	двудольного регулярного графа;
2)	регулярного графа степени 3 с девятью вершинами;
3)	платонова двудольного графа;
4)	(для каждого и) простого графа с п вершинами и
(и - 1) (и - 2)/ 2 ребрами;
5)	простого графа, изоморфного своему реберному
графу;
6)	простого графа, чье дополнение изоморфно ребер-
ному графу;
7)	колеса, дополнение которого - циклический граф.
Определение 7. Циклический граф С„ - связный регуляр-
ный граф степени 2 с и вершинами; соединение графов
(полностью несвязный граф с 1 вершиной) и C„.,(n > 3)
называется колесом с п вершинами и обозначается W„;
8)	четырех связных графов, являющихся регулярны-
ми графами степени 4;
9)	платонова графа, являющегося реберным графом
другого платонова графа;
10)	связного графа, не представимого в виде соедине-
ния двух графов.
79
1.15.	Что можно сказать о
1)	соединении двух полных графов;
2)	дополнении полного двудольного графа;
3)	дополнениях графов: тетраэдра, куба, октаэдра;
4)	дополнении соединения двух простых графов?
1.16.	Пусть G, Н, К - простые графы; доказать или опро-
вергнуть следующие равенства:
Gu(H + K) = (GuH) + (Gu К),
G + (HuK)= (G + H)vj(G + К).
1.17.	Описать матрицу смежности полных графов, полно-
стью несвязных графов, двудольных графов и циклических
графов. Что можно сказать о матрицах смежности простого
графа и его дополнения?
1.18.	Пусть G - двудольный граф с наибольшей степенью
вершин р. Показать, что существует двудольный граф G1 =
= G1 (Vb V2), в котором Vi и V2 содержат одинаковое количе-
ство вершин, причем G является регулярным графом степени
р, содержащим G в качестве подграфа.
1.19.	Доказать, что реберный граф графа К„ - полного
графа с п вершинами имеет п (п - 1) / 2 вершин и является
регулярным степени 2и - 4; получить аналогичные результа-
ты для Кт,п - полного двудольного графа с | VJ = т, IV2I - п, в
котором каждая вершина из Vj соединена с каждой верши-
ной из V2.. Доказать также, что простой граф изоморфен сво-
ему реберному графу тогда и только тогда, когда он является
регулярным степени 2, и описать все такие графы.
1.20.	Простой граф, изоморфный своему дополнению, на-
зывается самодополнительным. Доказать, что число вершин
самодополнительного графа представимо в виде 4Л или
80
4-к + 1, где к - целое, и найти все само дополнительные гра-
фы с 4 или 5 вершинами.
1.21.	Доказать, что среди шестерых человек всегда най-
дутся трое, которые либо все знают друг друга, либо ни один
из них не знает других.
Определение 8. Пусть G не имеет петель; тогда G называ-
ется ^-раскрашиваемым, если каждую его вершину можно
окрасить одним из к цветов таким образом, чтобы никакие
две смежные вершины не оказались одного цвета. Если
граф G является ^-раскрашиваемым, но не является (к - 1)
- раскрашиваемым, то назовем его fc-хроматическим, а число
к назовем хроматическим числом графа G и обозначим /(G).
1.22.	Найти хроматические числа полного графа с п вер-
шинами и полностью несвязного графа с п вершинами.
1.23.	Доказать, что /(G) = 2 тогда и только тогда,
когда G - двудольный граф, отличный от полностью несвяз-
ного графа.
1.24.	Если G не является полностью несвязным графом, то
/(G) = 2 тогда и только тогда, когда G не содержит циклов
нечетной длины.
1.25.	Найти хроматические числа циклических графов с
нечетным числом вершин, колес с нечетным числом вершин,
графа Петерсена (см. задачу 2.9).
1.26.	Доказать, что если наибольшая из степеней вершин
графа G равна р, то этот граф (р + 1) - раскрашиваем.
1.27.	Найти хроматические числа платоновых графов.
81
1.28.	Что можно сказать о хроматических числах соедине-
ния и объединения двух графов?
1.29.	Пусть G - простой граф с п вершинами, являющий-
ся регулярным степени d; показать, что / (G) >п/ (n-d).
Определение 9. Граф называется критическим, если уда-
ление любой из его вершин (вместе с инцидентными ей реб-
рами) приводит к графу с меньшим хроматическим числом.
1.30.	Показать, что
1)	К п является критическим для всех п > 1;
2)	Сп является критическим тогда и только тогда, ко-
гда п нечетно.
1.31.	Показать, что если п нечетно, то соединение
Сп + Сп является критическим графом, хроматическое число
которого равно шести.
1.32.	Доказать, что всякий критический граф, являю-
щийся ^-хроматическим, обладает следующими свойствами:
1)	он связен;
2)	степень каждой его вершины не меньше к - 1;
3)	не существует вершины, удаление которой приво-
дит к несвязному графу.
1.33.	Доказать, что всякий /.-хроматический граф (к > 1)
содержит в качестве подграфа критический fc-xpoмагический
граф.
§ 2.	Пути и циклы в графе. Связность
2.1.	Если в конечном неориентированном простом графе G
равно две вершины имеют нечетную локальную степень, то
они связаны.
82
2.2.	1) Если неориентированный граф G с однократными
ребрами без петель имеет п вершин и к связных компонент,
то максимальное число ребер в G равно
N (п, к) = (п - к) (п - к +1).
2)	Неориентированный граф с п вершинами и с чис-
лом ребер большим, чем
N (п, 2) = 1 (и - 1) (п - 2),
связен.
Можно дать следующие два определения связного графа.
Определение 10. Граф G называется связным, если для
любых двух его вершин у и со существует простой путь из
у в со.
Определение 11. Граф называется связным, если его
нельзя представить в виде объединения двух графов.
2.3.	Доказать, что граф является связным в смысле опре-
деления 10 тогда и только тогда, когда он связен в смысле
определения 11.
2.4.	Доказать, что неориентированный связный граф оста-
ется связным после удаления некоторого ребра тогда и толь-
ко тогда, когда это ребро принадлежит какому-нибудь циклу.
2.5.	Доказать, что неориентированный связный граф с п
вершинами
1)	содержит по крайней мере п - 1 ребро;
2)	если содержит более чем п - 1 ребро, то имеет по
крайней мере один цикл.
83
2.6.	Показать, что в полном неориентированном графе Кп
каждое ребро принадлежит ровно п - 2 треугольникам (т.е.
циклам длины 3).
2.7.	Показать, что число сп простых связных графов с
вершинами V = {1, п} равно
(Л],...Д„):	<=1
Yiki=n
(Указание. Каждый граф индуцирует разбиение мно-
жества {1, ..., п}, причем блоки состоят из вершин, принад-
лежащих общей связной компоненте. Пусть/(П) - число гра-
фов, индуцирующих разбиение П. Тогда с =Д1)).
2.8,	Пусть G - простой граф с п вершинами и к компонен-
тами. Тогда число m его ребер удовлетворяет неравенствам
п - к < т < (п - к) (п - к + 1) /2.
Определение 12. Разделяющим множеством связного
графа G называется такое множество его ребер, удаление ко-
торого приводит к несвязному графу.
Определение 13. Разрезом называется такое разделяющее
множество, никакое собственное подмножество которого не
является разделяющим. Если разрез состоит из единственно-
го ребра е, то е называется мостом.
2.9.	В графе Петерсена (регулярный граф степени 3) найти
циклы длины 5, 6, 8, 9 и разрезы, содержащие три, четыре,
пять ребер.
84
2.10.	Обхватом графа называется длина его кратчайшего
цикла; найти обхваты графов:
1)	Кп - полного графа с п вершинами;
2)	Кт. п - двудольного полного графа с [VJ = т,
IV2I = п, в котором каждая вершина из множеств
V] соединена с каждой вершиной из V2;
3)	Сп - циклического графа (см. определение 7);
4)	Wn - колеса (см. определение 7);
5)	платоновых графов;
6)	графа Петерсена.
2.11.	Доказать, что ребро связного графа является мостом
(см. определение 13) в том и только том случае, когда оно не
содержится ни в одном из циклов.
2.12.	Доказать, что если G - простой граф, то
1.	G и G не могут быть одновременно несвязными;
2.	из того, что G связен, следует, что реберный граф L(G)
тоже связен.
2.13.	Показать, что если каждый из двух различных цик-
лов некоторого графа G проходит через ребро е, то в графе
существует цикл, не проходящий через е. Установить соот-
ветствующий результат, заменив слово «цикл» на слово
«разрез».
2.14.	Доказать, что граф является двудольным тогда и
только тогда, когда все его циклы имеют четную длину.
Можно ли сформулировать аналогичный результат для раз-
резов?
2.15.	Пусть в простом графе G выполняется нера-
венство р (у) > г (г > 2) для каждой вершины v; показать, что
тогда в G существует цикл, имеющий длину не меньше г + 1.
85
2.16.	Пусть G - простой граф с п вершинами, не содер-
жащий треугольников (циклов длины три). Индукцией по п
доказать, что G содержит не более и2 ребер, и привести при-
мер, когда эта верхняя граница достигается.
Определение 14. В связном графе расстояние d(y,co) меж-
ду v и со есть длина кратчайшего простого пути из v в со .
Диаметром 8 связного графа G называется максимально воз-
можное расстояние между любыми двумя его вершинами.
Центром графа G называется такая вершина v, что макси-
мальное расстояние между v и любой другой вершиной явля-
ется наименьшим из всех возможных; это расстояние называ-
ется радиусом г:
г - min (max d(v, w)).
V w
2.17.	1) Привести пример графа, у которого больше одного
центра.
2)	Найти диаметры и радиусы графов Кп, Сп, Wn и
графа Петерсена.
3)	Доказать, что г < 8 < 2г.
2.18.	Если степень каждой вершины конечного неориен-
тированного графа G не меньше двух, то G содержит цикл.
§ 3.	Эйлеровы и гамильтоновы пути и циклы
3.1.	Эйлеров путь в неориентированном графе существует
тогда и только тогда, когда граф связен и содержит не более
двух вершин нечетной степени.
3.2.	Конечный граф G = <V, Е> содержит эйлеров цикл то-
гда и только тогда, когда
a)	G - связен;
б)	все его локальные степени четны.
86
3.3.	Построить эйлеровы циклы для следующих графов:
3.4.	Связный граф обладает эйлеровым циклом тогда и
только тогда, когда семейство его ребер можно разбить на
непересекающиеся циклы.
3.5.	Для каких чисел т и п следующие графы обладают
эйлеровыми циклами (см. задачу 1.19 и определение 7):
l)Km.„, 2)Кп, 3)W„?
3.6.	Есть ли среди платоновых графов графы, обладающие
эйлеровыми циклами? Если да, то найти в них эйлеровы цик-
лы.
3.7.	Доказать, что если граф G связен и имеет к > 0 вершин
нечетной степени, то минимальное число не имеющих общих
ребер циклов, объединение которых содержит каждое ребро
графа G, равно к / 2. Что можно сказать в случае нечетного к?
3.8.	Можно ли ходом шахматного коня обойти шахматную
доску размером 8x8 так, чтобы каждый ход встречался ров-
но один раз (ход “встречался”, если конь переместился с од-
ной клетки на другую любым из двух возможных способов).
Тот же вопрос для короля и ладьи. Как изменятся ответы для
шахматной доски размером 7x7? Изложить решения в тер-
минах теории графов.
Определение 15. Граф, обладающий эйлеровым циклом,
назовем эйлеровым.
87
3.9.	Доказать, что реберный граф простого эйлерова графа
является эйлеровым. Если известно, что реберный граф
простого графа G является эйлеровым, то можно ли отсюда
вывести, что сам граф G эйлеров?
3.10.	Доказать, что граф К$ имеет 264 эйлеровых цикла.
3.11.	Дано множество, состоящее из пятнадцати костей
домино, от 0-0 до 4-4; сколькими различными способами их
можно уложить в цикл, соблюдая стандартные для этой игры
правила?
Определение 16. Граф, обладающий гамильтоновым
циклом, назовем гамильтоновым.
3.12.	Если в простом графе с п > 3 вершинами р (v) > п / 2
для любой вершины v, то граф G является гамильтоновым.
3.13.	Показать, что граф, вершины и ребра которого
соответствуют вершинам и ребрам и - мерного куба, имеет
гамильтонов цикл.
3.14.	Полный простой путь из а 0 в а / длины I имеет тип
цикла, если р (а 0) + р (а;) > I + 1, где р (а,) - локальная
степень вершины а,.
3.15.	Максимальный простой путь в связном графе может
иметь тип цикла только тогда, когда граф имеет гамильтонов
цикл.
3.16,	В связном графе либо имеется гамильтонов цикл,
либо длина I его максимальных простых путей
удовлетворяет неравенству
Z > р(а0) + р(а;).
88
3.17.	В графе без гамильтоновых циклов длина его макси-
мальных простых путей удовлетворяет неравенству
l>pt + p2,
где р ] и р2 - две наименьшие локальные степени.
3.18.	Если в графе Gen вершинами для любой пары вер-
шин а о и а р (а о) + р(а е) > п - 1, то G имеет гамильтонов
путь.
Если р(Оо') + р(аД > п, то G имеет гамильтонов цикл.
3.19.	Для каких чисел m и п следующие графы являются
гамильтоновыми: 1)	2) Кп; 3) Wn? Описать гамильтоновы
циклы в каждом из тех случаев, когда они существуют. Пока-
зать, что все платоновы графы являются гамильтоновыми, и
найти в каждом из них гамильтоновы циклы.
3.20.	Доказать, что граф Петерсена не является гамильто-
новым. Обладает ли этот граф гамильтоновым путем?
3.21.	Привести пример графа, являющегося эйлеровым, но
не гамильтоновым, а также графа, являющегося гамильтоно-
вым, но не эйлеровым. Что можно сказать о графах, являю-
щихся одновременно эйлеровыми и гамильтоновыми?
3.22.	Пусть Н - группа, порожденная двумя элементами а
и b, b5 - 1, ab2a = bab и ab2 а = Ь2. Доказать, что
Gxbcdx’a’b')2 - 1.
Какая связь между этой задачей и задачей нахождения
гамильтонова цикла в графе, соответствующем додекаэдру?
3.23.	(Дирак). Граф имеет гамильтонов цикл, если для ка-
ждои его вершины р(а) > —п .
89
3.24.	Привести контрпример, показывающий, что в доста-
точном для гамильтоновости условии Дирака неравенство
р (г) > п/2 нельзя заменить условием р (у) > п - 1.
3.25*	. Доказать, что реберные графы эйлерова простого
графа и гамильтонова простого графа являются гамильтоно-
выми.
3.26*	. Найти п гамильтоновых циклов в графе К2п+ъ обла-
дающих тем свойством, что никакие два из них не имеют
общих ребер.
3.27.	Найти кратчайшие пути от вершины 1 ко всем дру-
гим вершинам графа.
3.28.	Показать, что следующий алгоритм всегда позволяет
найти эйлеров цикл в неориентированном простом связном
графе, если он существует: начать с некоторой вершины Р и
каждый раз вычеркивать пройденное ребро; не проходить по
ребру, если удаление этого ребра приводит к разбиению гра-
фа на две несвязные компоненты (не считая изолированных
вершин).
3.29.	Написать алгоритм, основанный на описанном в
задаче 3.28 алгоритме и позволяющий найти все эйлеровы
циклы графа.
90
§ 4.	Деревья
4.1.	В дереве любые две вершины связаны единственным про-
стым путем.
4.2.	Любое нетривиальное конечное дерево имеет хотя бы две
концевые вершины и хотя бы одно концевое ребро.
4.3.	Любое дерево с п вершинами имеет п - 1 ребро.
4.4,	Пусть граф Т имеет п вершин. Тогда следующие утвер-
ждения эквивалентны:
1)	Т является деревом;
2)	Т нс содержит циклов и имеет п - 1 ребро;
3)	Т связен и имеет п-1 ребро;
4)	Т связен и каждое его ребро является мостом;
5)	Любые две вершины графа Т соединены ровно одним
простым путем;
6)	Т не содержит циклов, но добавляя к нему любое но-
вое ребро, мы получаем ровно один цикл.
4.5.	Доказать, что существует ровно шесть неизоморфных де-
ревьев с шестью вершинами и одиннадцать - с семью вершина-
ми.
4.6.	Доказать, что каждое дерево является двудольным гра-
фом; какие деревья являются полными двудольными графами?
Определение 17. Помеченным графом с п вершинами называ-
ется граф, каждой вершине которого приписана с помощью вза-
имно однозначного соответствия метка из множества {1, 2, ..., и}.
4.7.	Два помеченных графа изоморфны, если существует изо-
морфизм, сохраняющий распределение меток в этих графах.
4.8.	Существует ровно п"'" различных помеченных деревьев с
п вершинами.
91
4.9.	Доказать, что существует ровно 2'|(,,'1)/2 помеченных про-
стых графов с п вершинами; сколько из них имеет в точности т
ребер?
4.10.	Пусть R,. - число деревьев со множеством вершин V,
IV! = п и одной произвольно выбранной вершиной из Vb качестве
корня дерева, a Rn(m) - число таких деревьев, у которых корень -
вершина степени т.
1)
2)
Показать, что
Rn = nni.
Доказать:
ДД) = nR„.i;
п 1
Rn(2) = ~ Е
п-2 (
RJ
Rn-1-j 
3)	При Ro = 0 вышеприведенным результатам можно придать
вид
Rn(l) = п Rn'\	где/Г1 = Д,.1;
2! Д,(2) = n(R + R)n'\ где R7 = Д.
Показать, что
m! Rn(m) = n(R + ... + R)n'1, R7н Д, где в правой части т
слагаемых.
4)	Показать, что
m! Rn(m) = п
( /2“1 'I
где

kj ^0, j = 1,..., т, к\ + ... + кт = п - 1.
5)	Доказать:
m!Rn(m) = [н]от+! m(n-l)n-m-2
92

или, что эквивалентно,
( п-2
Rn(jri) = п\
I m — 1
6)	Пусть T - число деревьев с п вершинами. Доказать, что
Тп = n'Rn = пп~2.
7)	Величина Tn(m) - ri[Rn(m), очевидно, является числом раз-
личных деревьев с п различными вершинами, в которых
выделенная вершина (корень) является вершиной m-й сте-
пени.
Доказать, что для числа Тп различных деревьев справедливо
представление:
Tn = E Tn(m) = nn~2
m=l
4.11.	Пусть Рп - число ориентированных деревьев с п верши-
нами и произвольно выделенной вершиной-корнем, a Qn - число
ориентированных деревьев с п вершинами. Показать, что
Рп = 2пЛРп = {2Пул-
Qn = 2nA Tn = 2(2ri)n'2.
4.12.	Химические формулы парафинов представляют собой
корневые деревья с двумя разными типами вершин, отличных от
корня. Концевые вершины имеют степень «единица», а каждая из
внутренних вершин имеет степень «четыре». (На языке химии
речь идет об атомах водорода (Н) и кислорода (0) соответствен-
но).
Доказать, что для парафинового дерева с р вершинами, из ко-
торых р\ - концевые, а р4 - внутренние, и е ребрами имеют место
соотношения:
р\ + р^-р\
е = р - 1:
Pi + 4р4 = 2е = 2р - 2.
Следовательно,
pi =2р^+2.
93
4.13.	Доказать, что данный простой граф Gen вершинами
можно пометить в точности n\/g различными способами, где
g - количество различных графов, изоморфных графу G.
4.14.	Показать, что если р\, ..., р„- заданные положительные
целые числа, то помеченное дерево с п вершинами, в котором
степень vk равна рк (для каждого к), существует в том и только в
том случае, если Ърк - 2(п - 1).
4.15.	Доказать, что число реберно-помеченных деревьев с п
вершинами (в которых помечены не вершины, а ребра) равно
п"'3(п > 3).
4.16.	Доказать, что при больших п у дерева с п вершинами до-
ля концевых вершин приблизительно равна е1.
4.17*	. Пусть Т(п) - число помеченных деревьев с п вершина-
ми.
1)	Доказать (подсчетом числа способов соединения помечен-
ного дерева с к вершинами с помеченным деревом с п - к верши-
нами), что
п (п''
2(п - 1) Т(п) = X к(п - к)Т(к)Т(п - к)\
кЛк )
2)	Вывести тождество
Г*-’ = 2(и-1)ил~2
4.18,	Дерево с висячей вершиной - это корневое непомеченное
дерево, корень которого имеет степень 1. По определению Т рав-
но Т', если можно непрерывным преобразованием наложить Т на
Т'. Пусть кп - число деревьев с висячей вершиной, у которых п
ребер (п + 1 вершина), причем все вершины имеют степень 1 или
3. Доказать, что
94
^2п “°’ k2n+i -
(W
и!(и +1)!
4.19,	Методом поиска в ширину построить остовное дерево
следующего графа:
4.20.	Пусть (у, Т) - остовное дерево связного неориентиро-
ванного графа G = {V, Е), построенное методом поиска в вер-
шину. Тогда путь в {V, Т) из произвольной вершины v до корня
г является кратчайшим путем из v в г в графе G.
4.21.	Каждая вершина дерева независимо от остальных окра-
шивается в один из с цветов. Пусть q(n,c) - количество раскра-
шенных корневых деревьев с п вершинами.
Установить, что
с) = с;
д(2, с) = с + 2
q(3, с) = 2с +10
<?(4, с) = 4с + 44
4.22.	Пусть р(п, с) - количество корневых деревьев с п рас-
крашенными с помощью с красок вершинами, среди которых
нет двух смежных вершин одинаковой расцветки.
Проверить следующие значения:
р(1, с)= с;
95
Р&, с) =
Р(3,с) =
Р(4, с) =
4.23.	Пусть р*(п, с) - число корневых деревьев с п вершинами
и хроматической окраской ребер (каждое ребро независимо от
остальных окрашивается в один из цветов и все ребра каждого
дерева имеют различную окраску). Проверить, что
/?*(0, с) = 1;
р *(1, с) ~ с;
р*(2, с) =
р *(5, с) = 6
+ 279
3
§ 5.	Ориентированные графы
Определение 18. Граф, полученный из ориентированного
графа D «удалением стрелок» (т.е, заменой каждого ориентиро-
ванного ребра <иу> неориентированным ребром {u,v} называется
основанием D.
96
5.1,	Ориентированный граф D связен (или слабо связен), если
его основание связно.
5.2.	Показать, что ориентированный граф связен тогда и толь-
ко тогда, когда он нс может быть представлен в виде объедине-
ния двух различных ориентированных графов.
5.3.	Показать, что любой сильно связный ориентированный
граф связен.
5.4.	Привести пример связного ориентированного графа, нс
являющегося сильно связным.
5.5.	Пусть D -- простой ориентированный граф с п вершинами
и т ребрами; показать, что если D связен, во не сильно связен, то
п - 1 < ш < (п - 1) (/? - 2). а если D сильно связен, то п < т <
<11(П- 1).
Определение 19. Связный ориентированный граф называется
эйлеровым орграфом, сели в нем существует ориентированный
цикл, содержащий каждое его ребро в точности один раз.
Определение 20. Если для любых двух вершин г и ш ориенти-
рованного графа D существует простой ориентированный путь из
I’ в и1, то D называется сильно связным.
Определение 21. Граф G называется ориентируемым, если
каждое его ребро может быть ориентировано таким образом, что
полученный в результате ориентированный граф будет сильно
связен.
5.6.	Показать, что любой эйлеров граф ориентируем.
5.7.	Пусть G - связный граф. Доказать, что он ориентируем то-
гда н только тогда, когда каждое его ребро содержится по край-
ней мерс в одном цикле.
97
5.8.	Обратный к D ориентированный граф получается из D пе-
ременной направлений каждого ребра ориентированного графа D.
Привести пример ориентированного графа D, изоморфного сво-
ему обратному.
Определение 22. Если v - вершина ориентированного графа
D, то степень исхода v (обозначается р (v)) - число ребер графа
D, имеющих вид <v,u >; аналогично степенью захода v (обознача-
ется р (г)) называется число ребер из D вида <и, г>.
5.9.	Доказать, что для ориентированного графа D = <V, Е >
X ро) = £р(у)-
ve V	ve V
5.10.	Связный ориентированный граф является эйлеровым то-
гда и только тогда, когда р (v) = р (v) для каждой его вершины v.
Определение 23. Турниром называется ориентированный
граф, в котором любые две вершины связаны ровно одним реб-
ром.
5.11.	Доказать, что во всяком турнире существует гамильтонов
путь.
5.12.	Доказать, что всякий сильно связный турнир имеет га-
мильтонов цикл.
Определение 24. Вершина v ориентированного графа - источ-
ник, если p(v) = 0; стоком ориентированного графа D называет-
ся вершина v, у которой р (v) = 0.
5.13.	Показать, что ориентированный граф, имеющий эйлеров
цикл, не может иметь ни источников, ни стоков.
98
5.14.	Показать, что в турнире не может содержаться больше
одного источника и больше одного стока.
5.15.	В турнире, изображенном на рисунке, найти эйлеров
цикл и гамильтонов ориентированный цикл.
—/ «\
5.16.	Найти такую циклическую расстановку девяти единиц,
девяти двоек и девяти троек, в которой каждое из 27 трехзначных
чисел, составленное из цифр 1, 2, 3, встречается ровно один раз.
5.17.	Пусть Т - турнир с п вершинами; X - суммирование по
всем вершинам v из Г; доказать, что
d£p(v) = £p(v);
2)£(p(v))2 =£(p(v))2.
5.18.	Турнир Т называется несводимым, если множество его
вершин нельзя разбить на два непересекающихся подмножества
V! и Т2 так, чтобы каждое ребро турнира Т, соединяющее верши-
ны из разных множеств (V] и V2), было направлено из V\ в У2- До-
казать, что турнир несводим тогда и только тогда, когда он силь-
но связен.
5.19.	Турнир Т называется транзитивным, если существование
дуг <и, v> и <v, w> влечет существование дуги <и, w>. Доказать,
что
1)	транзитивный турнир, имеющий по крайней мере две вер-
шины, не может быть сильно связным;
2)	каждый транзитивный турнир обладает единственным ори-
ентированным гамильтоновым путем.
99
Учебное издание
СБОРНИК ЗАДАЧ
ПО ДИСКРЕТНОМУ АНАЛИЗУ
Комбинаторика. Элементы
алгебры логики. Теория графов
Журавлев Юрий Иванович
Флеров Юрий Арсеньевич
Федько Ольга Сергеевна
Дадашев Тахмасиб Мустафаевич
Редактор И.А. Волкова
Корректор О.П. Котова
Изд. лиц. № 040060 от 21.08.96. Подписано в печать 01.09.2000.
Формат 60 х 84 1/16. Бумага офсетная. Печать офсетная.
Усл. печ. л. 6,25. Уч.-изд. л. 5,9.! iip.ij .... Заказ №412.
Московский физико-технический институт
(государственный университет)
Отдел автоматизированных издательских систем
“ФИЗТЕХ-ПОЛИГРАФ”
141700, Московская обл., г. Долгопрудный, Институтский пер., 9