Файл: Учебное пособие ульяновск 2018 msc2010 05 Combinatorics ббк 22. 176 Удк 519. 1 В313 Рецензенты.pdf

А.Б. ВЕРЁВКИН
КОМБИНАТОРИКА
УЧЕБНОЕ ПОСОБИЕ
Ульяновск
2018

MSC2010 05 Combinatorics
ББК 22.176
УДК 519.1
В313
Рецензенты:
Доктор физико-математических наук, профессор С.П. Мищенко;
Кандидат физико-математических наук, доцент Е.А. Михеева.
Верёвкин, Андрей Борисович
В313 Комбинаторика. Учебное пособие. /
А.Б. Верёвкин. – Ульяновск: Издатель Качалин
Александр Васильевич, 2018. – 134 с.
ISBN
978-5-6040503-6-1
Учебное пособие составлено на основе записей лек- ций, прочитанных автором в 1998–2017 годах в Улья- новском государственном университете студентам и ас- пирантам специальностей «Математика», «Фундамен- тальная и прикладная алгебра» и «Компьютерная без- опасность». В книге изложены некоторые разделы ком- бинаторики, в основном опирающиеся на теорию про- изводящих функций, востребованные в фундаментальной математике и теоретической информатике.
Пособие предназначено студентам математических и информационных специальностей, а также исследовате- лям, интересующимся комбинаторными методами.
MSC2010 05 Combinatorics
ББК 22.176
УДК 519.1
ISBN 978-5-6040503-6-1
© Верёвкин А.Б., 2018

1 1. ЧТО ТАКОЕ КОМБИНАТОРИКА?
Комбинаторика – сравнительно молодая математическая дис- циплина. Геометрия, арифметика и алгебра – старше не¨е, а математический анализ и теория вероятностей могут считать- ся е¨е сверстниками. Все разделы математики используют ком- бинаторные результаты. Труднообозримы замечательные ра- боты в этой области. И здесь найд¨
ется место для новых за- дач и методов. Советский математик И.М. Гельфанд заметил,
что все математические проблемы сводятся к комбинаторике.
Потенциально она охватывает всю науку. Поэтому нельзя ч¨ет- ко и навсегда очертить е¨е границы. Профессор Московско- го университета К.А. Рыбников написал о сво¨
ем понимании этой дисциплины в книге ([25]). Интересен взгляд на ком- бинаторику американского алгебраиста М. Холла:
”
Содержа- ние комбинаторного анализа нелегко определить. Его можно сравнить с теорией чисел в том отношении, что он возник из совокупности разнообразных задач, которые даже в наше время не охватываются никакой единой теорией или методом. Делая попытку дать определение, будем говорить, что в комбинатор- ном анализе рассматриваются задачи о расположениях элемен- тов в соответствии с точно определ¨енными правилами и вы- ясняется, сколькими путями такие расположения могут быть осуществлены.“ ([36, с. 7])
Одно из первых определений комбинаторики дал петер- бургский академик В.Я. Буняковский (цит. по [17, с. 122]):
”
Комбинаторный анализ – это особая отрасль математики, ко- торая занимается 1) исследованием различных образов изме- нения порядка и мест вещей, подлежащих или не подлежащих

2
определ¨енной зависимости, 2) разысканием законов, по кото- рым эти изменения или перемещения могут быть измерены и вычислены, наконец, 3) приложением выводимых таким обра- зом следствий к другим областям математики.“ (Лексикон чис- той и прикладной математики.– СПб, 1839, с. 204)
Московский математик Н.Б. Делоне написал в энцикло- педической заметке:
”
Комбинаторный анализ – математичес- кая теория, занимающаяся определением числа различных спо- собов распределения данных предметов в известном порядке;
имеет особенно важное значение в теории уравнений и в теории вероятностей. . . . “ (Энциклопедический словарь Брокгауза и
Ефрона, т. XVа (30).– СПб, 1895, с. 818)
Следующее определение дал академик А.Н. Колмогоров:
”
Комбинаторика (мат.), учение о числе способов, к-рыми мож- но переставить то или другое число предметов при тех или других дополнительных условиях. Начало К. теряется в глубо- кой древности. Например, Ксенократ (397–314 до хр. э.), уче- ник Платона, определял число слогов, к-рые можно составить из всех букв греч. алфавита. Основоположниками К. как мате- матич. дисциплины считаются Паскаль, Лейбниц, Валлис, Як.
Бернулли, Муавр. . . . К. имеет приложение в ряде отделов мате- матики, особенно в теории вероятностей.“ (Большая Советская
Энциклопедия, I изд., т. 33.– М.: ОГИЗ, 1938, с. 559-560)
Определение комбинаторики для советской “Математичес- кой Энциклопедии” написано криптографом, доктором физ.- мат. наук, заместителем начальника 8-го Главного управле- ния КГБ при Совете Министров СССР, генерал-майором В.Н.
Сачковым (сейчас он – вице-президент Академии криптогра-

3
фии России):
”
Комбинаторный анализ, комбинаторная мате- матика, комбинаторика – раздел математики, посвящ¨енный ре- шению задач выбора и расположения элементов некоторого,
обычно конечного, множества в соответствии с заданными пра- вилами. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, на- зываемой комбинаторной конфигурацией. Поэтому можно ска- зать, что целью К.А. является изучение комбинаторных конфи- гураций. . . .“ (МЭ, т. 2.– М.: Сов. Энц., 1979, с. 974)
Интересные сведения об истории предмета сообщил аме- риканский математик венгерского происхождения Д. Пойа.
Рождение комбинаторики (или этого термина) он связал с
Лейбницем:
”
Готтфрид Вильгельм Лейбниц был, кажется, пер- вым автором, который использовал термин “комбинаторный”
в том смысле, в каком мы употребляем его сегодня, говоря о комбинаторном анализе или о комбинаторной математике.
Лейбницу едва исполнилось двадцать лет, когда он написал свою “Dissertatio de Arte Combinatoria”, напечатанную в 1666 г.
Е¨е титульный лист обещал приложения во всех сферах науки и
“новый подход к логике изобретения”. Во вступлении провозгла- шалось приложение теории к замк´
ам, орг´
анам и силлогизмам,
к смешиванию цветов и к “протейскому” стиху, к логике геомет- рии, военному искусству, грамматике, юриспруденции, медицине и теологии.
На самом деле диссертация содержит, помимо блестящей де- монстрации схоластической эрудиции, некоторые математичес- кие результаты. Она объясняет и решает основные комбина- торные задачи, приводящие к биномиальным коэффициентам

4
и к факториалу, но почти ничего больше. Эти задачи в 1666
году не были так тривиальны, как в наше время, но многие из результатов Лейбница были известны до него. За матема- тическими предложениями следуют приложения, большинство которых представляются современному читателю бесплодными или фантастическими, что в некоторых случаях было ясно са- мому Лейбницу.
Эта “Диссертация о комбинаторном искусстве” была, однако,
только началом большой работы, которая всю жизнь занимала
Лейбница. Он часто упоминает об этой работе в своих письмах и в печатных трудах, и к ней относятся многие записи, найденные в его рукописях, оставшихся неопубликованными. Некоторые из этих заметок были посмертно напечатаны. Из них мы видим,
что Лейбниц планировал вс¨е новые и новые применения для своего комбинаторного искусства или “комбинаторики”: к коди- рованию и декодированию, к играм, к статистике смертности, к комбинации наблюдений. Он также вс¨е больше и больше расши- рял сферу применения комбинаторики. Иногда он рассматривал комбинаторику как половину общего Искусства Изобретения,
эта половина относится к синтезу, в то время как другая –
к анализу. Комбинаторика должна заниматься, говорит он в другом месте, одинаковым и различным, похожим и непохо- жим, абсолютным и относительным, в то время как обычная математика занимается большим и малым, единицей и многим,
целым и частью. Наконец, он приписывает комбинаторике ши- рочайшую сферу применения, рассматривая е¨е как почти или полностью совпадающей со своей “Characteristica Universalis”. Он проектировал “универсальную характеристику” как нечто вроде

5
обобщ¨енной математики, которая будет рассматривать вс¨е что угодно, и которая свед¨ет мышление к чему-то вроде вычисления с помощью соответствующих цифр и символов.
Были ли эти проекты Лейбница просто мечтами? В них был некоторый смысл, и, возможно, его мечты были пророчески- ми. Используя свою “Characteristica Universalis”, он намеревался свести понятия к символам, символы к числам и, наконец, с помощью цифр и символов подвергнуть понятия механическо- му вычислению. Этот проект казался абсурдным и фантастичес- ким многим, обычно здраво рассуждающим людям, но сегодня вычислительные машины реализуют часть этого фантастичес- кого плана. Лейбниц знал некоторые основы математической логики, важность которой он признал задолго до кого бы то ни было, а математическая логика лежит где-то на пути к “Char- acteristica Universalis”. Правда, применения его Ars Combinato- ria были фантастическими, тривиальными или бесплодными,
но он, конечно, предвидел громадное разнообразие приложений и расширяющуюся сферу применения комбинаторики, поэто- му имя Готтфрида Вильгельма Лейбница, великого математика,
философа и прожект¨ера с полным правом заслуживает упоми- нания во введении в настоящую книгу.“ ([20, с. 7-8])
Авторство Лейбница в изобретении “комбинаторного ис- кусства” не призна¨
ется столь однозначно. Некоторые авторы,
разделяя комбинаторику и комбинаторный анализ, полагают,
что последний начался в трудах Ж.Л. Лагранжа 1766-87 гг.
(см. [17, с. 123]). Другие исследователи, напротив, ищут у комбинаторики более древние истоки. Например, “Трактат об арифметическом треугольнике” Б. Паскаля 1665 г., древнеки-

6
тайские или арабские математические сочинения.
Возможно, лейбницева “Dissertatio de Arte Combinatoria”
1666 г. – первая книга, где комбинаторика упоминается в заглавии. Лейбниц не объясняет, что он называет комбинато- рикой. Скорее всего, этот термин уже был известен. Вскоре в
1669 г. уч¨
еный-иезуит А. Кирхер опубликовал сво¨е сочинение
“Ars Magna Sciendi, sive Combinatoria: in XII libros digesta”
(Великое Искусство Знания или Комбинаторика, изложенное в 12 книгах).
Слова комбинаторика и комбинаторный – новые. Клас- сической латыни они не ведомы. Но давно было слово com- bino (сочетать, связывать по два), происходящее от bini (по два) и bis (дважды). Тем самым, комбинаторика означает науку о сочетаниях и сч¨ете вообще. В комбинаторике раз- вивают методы исчисления и перечисления сконструирован- ных математических обьектов – конфигураций (лат. configo
– скреплять, figura – расположение). Компьютерные расч¨
е- ты требуют вычисления эффективности используемых опе- раций. К этим тр¨ем связанным задачам сводится современ- ная комбинаторика. М. Холл замечает:
”
Большинство задач о перечислении таковы, что для них вопрос о существовании и построении решений по существу тривиален. Однако следует оговориться, что тривиальные методы построений могут ока- заться чересчур трудо¨емкими. Как и следует ожидать, для от- ыскания менее громоздких методов необходимы дополнитель- ная теория и значительное мастерство. . . . “ ([36, с. 7-8])
Эта оценка опирается на возможность полного перебора конфигураций. Но если обратиться к задачам комбинатор-

7
ной топологии или алгебраической комбинаторики, с мнением
Холла трудно согласиться. Прояснение структуры конфигу- раций может представлять самостоятельную ценность.
Например, рассмотрим задачу о перестановках n различ- ных элементов. Здесь прост подсч¨ет количества перестано- вок. Но построение всех различных перестановок неочевидно.
Алгоритмы предложены в книгах Липского ([15, с. 19-29]) и
Кнута ([13, с. 369-396]). Метод Симса ([13, с. 378]) оказался удобен для вычисления кратностей неприводимых представ- лений симметрической группы S
n
([7]).
Для примера укажем биекцию между S
n и произведением циклических групп C
2
× C
3
× · · · × C
n порядков 2, 3, . . . , n,
соответственно.
1.1. Определение. Обозначим St (n) – подгруппу S
n
:
St (n) = {σ ∈ S
n
| σ(n) = n } ∼
= Symm{1, . . . , n−1} ∼
= S
n−1
и выберем c – циклическую перестановку длины n из S
n
1.2. Лемма. Пусть τ ∈ S
n
, тогда
1. подстановка τ однозначно представима в виде σ · c a
, где
σ ∈ St (n) и 0 ≤ a < n ;
2. для 1 < k ≤ n однозначно определены целые показатели
0 ≤ a k
< k , такие что:
τ = (12)
a
2
· (123)
a
3
· . . . · (12 . . . n)
a n
Доказательство: пусть σ · c a
= ς · c b
, где σ, ς ∈ St (n) и
0 ≤ a ≤ b < n . Тогда получим равенство:
c b − a
= ς
−1
· σ ∈ St (n) и 0 ≤ b − a < n ,

8
поэтому a = b и σ = ς . Таким образом, выражения вида
σ · c a
с разными сомножителями – различны. А их общее ко- личество n · (n − 1)! = n! равно порядку группы S
n
. Поэтому все элементы S
n однозначно представимы в виде σ · c a
. Что доказывает первое утверждение леммы. Второе утверждение следует из первого индукцией по n.
1.3. Замечание. Предыдущая лемма обеспечивает биекцию коммутативной группы C
2
× C
3
× · · · × C
n на S
n
:
f (a
2
, a
3
, . . . , a n
) = (12)
a
2
· (123)
a
3
· . . . · (12 . . . n)
a n
Что да¨
ет способ перечисления перестановок. Но отобра- жение f при n > 2 – негомоморфно. Связь между набора- ми чисел a
2
, a
3
, . . . , a n
и подстановками f (a
2
, a
3
, . . . , a n
) не- очевидная. Ясны ответы только на самые простые вопросы.
Например, – ч¨етность f (a
2
, a
3
, . . . , a n
) совпадает с ч¨етностью суммы a
2
+ a
4
+ a
6
+ . . . . А уже зависимость циклического типа подстановки от соответствующих наборов непонятна.
В книге обсуждены некоторые разделы комбинаторики, где применяются производящие функции. В этой искусственно ограниченной области уда¨ется показать многообразие работа- ющих при¨емов и перспективу существующих методов. При- ветствуется предварительное знакомство читателя с начала- ми математического анализа и высшей алгебры. В списке литературы ([8]–[37]) упомянуты монографии, полезные для более глубокого изучения тем. Авторские тексты ([1]–[7]) со- держат более подробный разбор рассмотренных примеров.

9 2. ПРОИЗВОДЯЩИЕ ФУНКЦИИ
Считают, что производящие функции были открыты Лап- ласом для решения вероятностных задач. Но они оказались полезными в математике для изучения последовательностей и, более общо, – бесконечных (бесконечномерных) объектов,
являющихся локально конечными. Хорошее введение в те- му да¨
ет первый отдел знаменитой книги Полиа и Сег¨е ([19]).
Разбер¨
ем идею метода.
2.1. Определение. Назов¨ем множество X взвешенным, если задана “взвешивающая” функция:
w
X
: X → N = {1, 2, . . . } с конечными X
n
= w
−1
X
(n).
Если X, Y – взвешены, то такое же и X ∪ Y . Можно задать
(тотальное) взвешивание произведения X × Y , полагая w
X× Y
(x, y) = w
X
(x) + w
Y
(y) , (X× Y )
n
=
n − 1
[
k = 1
X
k
× Y
n−k
Взвешенному X сопоставим производящую функцию (сим- волом ] обозначим мощность конечного множества):
X(t) =
X
n ≥ 1
] (X
n
) · t n
Тогда очевидны свойства:
(X ∪ Y )(t) = X(t) + Y (t) , (X× Y )(t) = X(t) · Y (t) .
2.2. Пример. Пользу данного определения проиллюстриру- ем подсч¨етом порождающих подмоноида Веронезе свободного ассоциативного моноида (см. [2]).