Элементы комбинаторики

Московский государственный технический университет
имени Н.Э. Баумана
А.Е. Жуков, Д.А. Жуков
Элементы комбинаторики
Рекомендовано Научно-методическим советом
МГТУ им. Н.Э. Баумана в качестве учебного пособия
Москва
Издательство МГТУ им. Н.Э. Баумана
2014

УДК 519.1
ББК 22.141
Ж85
Рецензенты: А.В. Чашкин, П.Г. Ключарев
Ж85
Жуков А. Е.
Элементы комбинаторики : учеб. пособие / А. Е. Жуков,
Д. А. Жуков. — М. : Изд-во МГТУ им. Н. Э. Баумана, 2014. —
99, [5] с. : ил.
ISBN 978-5-7038-3752-8
Изложены основные идеи и понятия, нашедшие применение в
области компьютерной криптографии. Приведены разные конструкции и методы работы с комбинаторными объектами, большое количество примеров и задач.
Для студентов, изучающих курсы «Информатика», «Дискретная математика», «Основы теории информации» и «Комбинаторика». Может быть полезно студентам и аспирантам для самостоятельного изучения.
УДК 519.1
ББК 22.141
ISBN 978-5-7038-3752-8
c
⃝МГТУ им. Н.Э. Баумана, 2014

ПРЕДИСЛОВИЕ
О значении математики для защиты информации в компьютерах и сетях связи сказано и написано довольно много. Знание
разработанных математических теорий, идей и методов позволяет находить новые оригинальные технические решения, в свою
очередь, практические задачи защиты информации ставят перед
математиками новые интересные проблемы. Важнейшими математическими объектами, используемыми в процессе разработки
и проектирования систем информационной безопасности и в информатике в целом, являются комбинаторные схемы и конфигурации. Комбинаторика — раздел математики, посвященный решению
задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с установленными правилами.
Каждое такое правило определяет способ построения некоторой
конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью
комбинаторного анализа является изучение комбинаторных схем и
конфигураций.
Работая над книгой, авторы ставили своей целью создание руководства по перечислительной комбинаторике, ориентированного
на прикладное применение. В основу пособия положено содержание курсов и семинаров, которые авторы на протяжении ряда лет
проводили в МГУ
, МГТУ
, МИФИ, ИКСИ.
В приложении содержатся строгие математические доказательства некоторых утверждений, включение которых в основной текст
сделало бы его чрезмерно громоздким и сложным для восприятия.
Кроме того, приведено интересное комбинаторное понятие — числа
Каталана, имеющие разнообразное применение.
Все разделы содержат примеры и задачи, полезные для самостоятельного изучения студентами и аспирантами. Освоение материала даст читателю необходимый инструментарий для теоретической и практической работы в области информационной безопасности.

Глава 1. ОСНОВНЫЕ КОМБИНАТОРНЫЕ ПОНЯТИЯ
И СХЕМЫ
Цель комбинаторного анализа — решение задач выбора и расположения элементов некоторого, обычно конечного, множества
в соответствии с установленными правилами (схемами). Каждое
такое правило определяет способ построения из элементов исходного множества некоторой конструкции, называемой комбинаторной конфигурацией. Задачей комбинаторики является изучение и
в первую очередь перечисление комбинаторных схем и конфигураций.
1.1. Основные перечислительные правила
Основные перечислительные правила комбинаторики очень
просты, естественны и понятны. При правильном их использовании можно решить очень большое количество самых разнообразных перечислительных задач, появляющихся в дискретной
математике.
Правило суммы: если первое событие может произойти n1 способами, а второе n2 способами и при этом они не могут произойти
одновременно, то или первое, или второе событие (но только одно
из них) может произойти n1 + n2 способами.
Правило произведения: если первое событие может произойти
n1 способами, а второе независимо от исхода первого события,
может произойти n2 способами, то совместная реализация двух
событий может произойти n1 × n2 способами.
Пример 1.1. В группе из 20 студентов и 15 студенток:
— выбор старосты возможен 20 + 15 = 35 способами (правило
суммы);
4

— выбор пары «студент — студентка» 20 × 15 = 300 способами
(правило произведения).
Пример 1.2. По правилу произведения выбирают:
— семизначные телефонные номера (107 вариантов);
— семизначные телефонные номера с неповторяющимися цифрами 10 · 9 · 8 · 7 · 6 · 5 · 4 вариантов;
— число перестановок из n элементов равно
n(n −1) (n −2) · . . . · 3 · 2 · 1 = n!;
— число двоичных наборов длины n равно 2n;
— число булевых функций от n переменных равно 22n.
1.2. Основные комбинаторные схемы
Важнейшими математическими объектами, используемыми не
только в дискретной математике, но и в информатике в целом,
являются различные комбинаторные схемы и конфигурации. Из
них более всего распространены схемы выборок, с которыми связаны, пожалуй, наиболее употребимые в математике (причем не
только дискретной) понятия размещения и сочетания. Доказательства в этом разделе даются по большей части схематично, так как
рассматриваемые величины, как правило, уже определялись и изучались в других математических дисциплинах.
1.2.1. Схемы выборок. Пусть имеется конечное множество
M, его мощность |M| = n. Рассмотрим выборки объема k, которые извлекаются из множества M. Существуют следующие типы
выборок.
I. Размещения (упорядоченные выборки без возвращения). Число размещений находят по правилу произведения:
Ak
n = n(n −1) . . . (n −k −1) = (n)k =
n!
(n −k)!.
Размещение называется перестановкой, если k = n, их число
An
n = n!.
II. Размещения с повторениями (упорядоченные выборки с возвращением). По правилу произведения число размещений с повторениями
¯
Ak
n = nk.
5

III. Сочетания (неупорядоченные выборки без возвращения).
Число сочетаний Ck
n получается группировкой различных размещений, состоящих из одних и тех же элементов, т. е. образующих
одно и то же сочетание:
Ck
n = Ak
n
Ak
k
=
n!
(n −k)! k!.
IV. Сочетания с повторениями (неупорядоченные выборки с
возвращением). Число сочетаний с повторениями ¯
Ck
n соответствует
числу способов деления n + k элементов, выстроенных в линию,
на n непустых зон:
¯
Ck
n = Cn−1
n+k−1 = Ck
n+k−1.
Пример 1.3. Интерпретация числа сочетаний Ck
n:
— коэффициенты в формуле бинома Ньютона (x + y)n =
=
k=0
Ck
nxkyn−k. Величины Ck
n называют также биномиальными
n

коэффициентами поскольку они появляются в формуле бинома
Ньютона.
— число разных подмножеств мощности k в множестве из n
элементов. Число всех подмножеств такого множества равно 2n;
— число последовательностей длины n, содержащих ровно k
единиц;
— число неубывающих путей длины n, соединяющих точки
(0,0) и (k, n −k) на прямоугольной решетке;
1.2.2. Свойства биномиальных коэффициентов.
Б´
oльшая
часть свойств биномиальных коэффициентов может быть получена
по меньшей мере двумя способами — из алгебраического выражения для величины Ck
n и из комбинаторных соображений, вытекающих из определения сочетания. Другие свойства могут быть легко
получены из формулы бинома Ньютона.
Свойство симметрии Ck
n = Cn−k
n
. Алгебраическое доказательство свойства симметрии очевидно из формулы для Ck
n. Комбинаторное доказательство состоит в том, что выбор подмножества
мощности k в множестве мощности n эквивалентен выбору в том
же множестве подмножества мощности n −k.
Рекуррентное соотношение Ck
n = Ck−1
n−1 + Ck
n−1. Написав выражения для биномиальных коэффициентов и проделав очевидные
6

преобразования, получаем алгебраическое доказательство приведенного тождества. Для комбинаторного доказательства рассмотрим множество M, состоящее из n элементов. Пусть один из
элементов этого множества отмечен. Тогда отмеченный элемент
либо входит в подмножество мощности k (таких подмножеств будет Ck−1
n−1) либо не входит (таких подмножеств будет Ck
n−1). Отсюда и следует указанное рекуррентное соотношение с очевидными
граничными условиями: C0
n = Cn
n = 1.
Сумма биномиальных коэффициентов:
k=0
Ck
n = 2n. Тождество
n

k=0
(−1)k Ck
n = 0 ⇒C0
n + C2
n + . . . = C1
n + C3
n + . . . = 2n−1. Тожлегко получаем из формулы бинома Ньютона, если в ней положить
x = y = 1.
n

k=1
k(−1)k Ck
n = 0. Это и следующее тождество получаем из
дество следует из формулы бинома Ньютона, если в ней положить
x = −1; y = 1.
n

k=r
(−1)k Cr
k Ck
n = 0.
формулы бинома Ньютона после ее однократного или соответственно r-кратного дифференцирования.
n

Ck−1
n
= (n)k−1
(k −1)! ⩽(n)k
k!
= Ck
n при k ⩽n −k + 1 ⇔k ⩽n + 1
2
.
Неравенство непосредственно выводят из алгебраической формулы для биномиальных коэффициентов.
Свертка Вандермонда
j=0
Cj
n Ck−j
m
= Ck
n+m.
n

Для доказательства можно воспользоваться
алгебраическим тождеством
(x + 1)n(x + 1)m = (x + 1)n+m
Рис. 1.1
или
комбинаторными
соображениями
(рис. 1.1).
Биномиальные коэффициенты Ck
n, рас7

положенные в виде прямоугольной таблицы (табл. 1.1), образуют так называемый треугольник Паскаля, наглядно показывающий свойство симметрии Ck
n = Cn−k
n
, рекуррентное соотношение
Ck
n = Ck−1
n−1 + Ck
n−1 и неравенство
Ck−1
n
= (n)k−1
(k −1)! ⩽(n)k
k!
= Ck
n при k ⩽n + 1
2
.
Таблица 1.1
n
k
0
1
2
3
4
5
6
. . .
0
1
1
1
1
2
1
2
1
3
1
3
3
1
4
1
4
6
4
1
5
1
5
10
10
5
1
6
1
6
15
20
15
6
1
. . .
1.2.3. Полиномиальные коэффициенты. Рассмотрим схему,
состоящую в «раскрашивании» k красками элементов множества
M, |M| = n. Обозначим через ni количество элементов, раскрашенных i-м цветом, причем ni ⩾0, n1 + n2 + . . . + nk = n. Найдем
число способов раскраски n элементов, при которой ni элементов
раскрашено i-й краской:
C (n; n1, . . . , nk) = Cn1
n Cn2
n−n1Cn3
n−n1−n2 · . . . · Cnk
n−n1−...−nk−1 =
=
n!
n1! (n −n1)!
(n −n1)!
n1! (n −n1 −n2)! · . . . · (n −n1 −n2 −. . . −nk−1)!
nk!0!
или
после
сокращения
C(n; n1, n2, . . . , nk) =
n!
n1!n2! · . . . · nk!.
Полученное выражение называется полиномиальным коэффициентом.
8

Теоретико-множественный смысл полиномиального коэффициента заключается в количестве способов разбиения n-элементного
множества на k различимых подмножеств (может быть и пустых).
Иными словами, полиномиальный коэффициент — число выборок,
для которых ni элементам присваивается метка i, причем n = n1 +
+ n2 + . . . + nk.
Полиномиальный коэффициент появляется как коэффициент
при соответствующем слагаемом в полиномиальном представлении выражения (x1 + x2 + . . . + xk)n:
(x1 + x2 + . . . + xk)n =
n1+n2+...+nk=n
C(n; n1, n2, . . . , nk) xn1
1 xn2
2 . . . xnk
k .
=

Заметим, что при k = 2 получаем уже известные биномиальные
коэффициенты: C(n; n1, n −n1) =
n!
n1!(n −n1)! = Cn1
n .
1.2.4. Разбиения чисел. Разбиением натурального числа n называют его представление в виде суммы натуральных слагаемых:
n1 + n2 + . . . + nk = n.
Если порядок слагаемых значения не имеет, то такое разбиение
называется неупорядоченным. Если не оговорено противное, то в
дальнейшем под разбиением будем понимать неупорядоченное разбиение натурального числа n. Разбиение обычно представляется в
стандартной форме, в которой слагаемые выписывают в невозрастающем порядке:
n1 ⩾n2 ⩾. . . ⩾nk.
Например, 9 = 3 + 2 + 2 + 1 + 1. Числа ni, образующие разбиение, называют его частями. Обозначим через Pk(n) число разбиений n на k частей.
Пример 1.4. P3(7) = 4, так как
7 = 5 + 1 + 1 = 4 + 2 + 1 = 3 + 3 + 1 = 3 + 2 + 2.
Иными словами Pk(n) — это число натуральных решений уравнения
x1 + x2 + . . . + xk = n;
x1 ⩾x2 ⩾. . . ⩾xk ⩾1.
9

Это уравнение можно преобразовать к виду
(x1 −1) + (x2 −1) + . . . + (xk −1) = n −k;
x1 ⩾x2 ⩾. . . ⩾xk ⩾1.
Отсюда, сделав замену yi = xi −1,
i = 1, . . . , k, получим
y1 + y2 + . . . + yk = n −k;
y1 ⩾y2 ⩾. . . ⩾yk ⩾0.
Однако если ys > 0, ys+1 = . . . = yk = 0, то предыдущая формула
дает разбиение n −k на s частей. Таким образом, число решений
этого уравнения равно числу разбиений n −k не более чем на
k частей, отсюда следует рекуррентное соотношение для числа
разбиений
Pk(n) = Pk(n −k) + Pk−1(n −k) + . . . + P1(n −k)
с очевидными граничными условиями P1(n)=Pn(n) = 1 и Pk(n) =
= 0 при n < k.
Применяя рекуррентное соотношение, получаем, в частности,
P2(n) = P2(n −2) + P1(n −2) = P2(n −2) + 1 =
= P2(n −4) + 2 = . . .
n
2
при n = 2k;
=
⎧
⎪
⎨
n −1
2
при n = 2k + 1.
⎪
⎩
Если теперь через P(n) обозначить количество всех неупорядоченных разбиений числа n, то ясно, что
P(n) = Pn(n) + Pn−1(n) + . . . + P2(n) + P1(n).
В то же время P(n) можно рассматривать как число неотрицательных целочисленных решений уравнения
x1 + x2 + . . . + xn = n;
x1 ⩾x2 ⩾. . . ⩾xn ⩾0.
Любое фиксированное разбиение числа n содержит λ1 слагаемых, равных 1; λ2 слагаемых, равных 2 и т. д. Таким образом, разбиение числа n можно однозначно описать набором λ1, λ2, . . . , λn.
10