Комбинаторика

Задачи дискретной математики, к которым относится большинство олимпиадных задач по информатике, часто сводятся к перебору различных комбинаторных конфигураций объектов и выбору среди них наилучшего, с точки зрения условия той или иной задачи. Поэтому знание алгоритмов генерации наиболее распространенных комбинаторных конфигураций является необходимым условием успешного решения олимпиадных задач в целом. Важно также знать количество различных вариантов для каждого типа комбинаторных конфигураций, так как это позволяет реально оценить вычислительную трудоемкость выбранного алгоритма решения той или иной задачи на перебор вариантов и, соответственно, его приемлемость для решения рассматриваемой задачи, с учетом ее размерности. Кроме того, при решении задач полезным оказывается умение для каждой из комбинаторных конфигураций выполнять следующие операции: по имеющейся конфигурации получать следующую за ней в лексикографическом порядке; определять номер данной конфигурации в лексикографической нумерации всех конфигураций; и, наоборот, по порядковому номеру выписывать соответствующую ему конфигурацию.

Перечисленные подзадачи в программировании обычно рассматривают для следующих комбинаторных конфигураций:

1. перестановки элементов множества

2. подмножества множества

3. сочетания из n элементов множества по k элементов (k-элементные подмножества множества, состоящего из n k элементов)

4. размещения (упорядоченные подмножества множества, то есть отличающиеся не только составом элементов, но и порядком элементов в них)

5. разбиения множества (множество разбивается на подмножества произвольного размера так, что каждый элемент исходного множества содержится ровно в одном подмножестве)

Комбинаторика является древнейшей ветвью математики. Комбинаторика располагает столь многообразными методами, решает столь разнообразные задачи, что трудно чётко обозначить её границы. Элементарными комбинаторными конфигурациями являются сочетания, размещения, перестановки. Для подсчёта числа этих конфигураций используются правила суммы и произведения.

Правило суммы:

Если элемент A можно выбрать m способами, а элемент B можно выбрать k способами, то выбор элемента A или B можно осуществить m + k способами.

Правило произведения:

Если элемент A можно выбрать m способами, а после каждого выбора элемента A элемент B можно выбрать k способами, тогда, упорядоченную пару элементов (A, B) можно выбрать m*k способами.

Правило произведения можно распространить на выбор последовательности (x1, x2, …, xn) произвольной конечной длины n.

Перестановки.

Возьмём n различных элементов: a1 , a2 , a3 , …, an . Будем переставлять их всеми возможными способами, сохраняя их количество и меняя лишь порядок их расположения. Каждая из полученных таким образом комбинаций называется перестановкой. Общее количество перестановок из n элементов обозначается P_n . Это число равно произведению всех целых чисел от 1 до n :

Символ n! ( называется эн-факториал ) - сокращённая запись произведения:

1*2*3* … *( n – 1 )*n .

П р и м е р . Найти число перестановок из трёх элементов: a, b, c.

Р е ш е н и е . В соответствии с приведенной формулой: P₃ = 1*2*3=6.

Действительно, мы имеем 6 перестановок: abc, acb, bac, bca, cab, cba.

Размещения.

Будем составлять группы из m различных элементов, взятых из множества, состоящего из n элементов, располагая эти m взятых элементов в различном порядке. Полученные комбинации называются размещениями из n элементов по m .Их общее количество обозначается: и равно произведению:

П р и м е р . Найти число размещений из четырёх элементов a, b, c, d по два.

Р е ш е н и е . В соответствии с формулой получим:

Вот эти размещения: ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc.

Сочетания.

Будем составлять группы из m различных элементов, взятых из множества, состоящего из n элементов, не принимая во внимание порядок расположения этих m элементов. Тогда мы получим сочетания из n элементов по m .

Их общее количество обозначается и может быть вычислено по формуле:

Из этой формулы ясно, что

Заметим, что можно составить только одно сочетание из n элементов по n , которое содержит все n элементов. Формула числа сочетаний даёт это значение, если только принять, что 0! = 1, что является определением 0! .

В соответствии с этим определением получим:

Общее число сочетаний можно вычислить, пользуясь и другим выражением:

П р и м е р . Найти число сочетаний из пяти элементов: a, b, c, d, e по три.

Р е ш е н и е :

Эти сочетания: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.

Бином Ньютона.

Это формула, представляющая выражение ( a + b )ⁿ при положительном целом n в виде многочлена:

Заметим, что сумма показателей степеней для a и b постоянна и равна n.

Пример 1.

Формула суммы кубов двух чисел .

Числа называются биномиальными коэффициентами.

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

Первая строка в этой таблице содержит биномиальные коэффициенты для n = 1; вторая - для n = 2; третья - для n = 3 и т.д. Поэтому, если необходимо, например, разложить выражение:

( a + b )⁷ , мы можем получить результат моментально, используя таблицу:

Свойства биномиальных коэффициентов.

1. Сумма коэффициентов разложения (a+b)ⁿ равна 2ⁿ .

Для доказательства достаточно положить a = b = 1. Тогда в правой части разложения бинома Ньютона мы будем иметь сумму биномиальных коэффициентов, а слева:

2. Коэффициенты членов, равноудалённых от концов разложения, равны.

Это свойство следует из соотношения:

3. Сумма коэффициентов чётных членов разложения равна сумме коэффициентов нечётных членов разложения; каждая из них равна

Для доказательства воспользуемся биномом: Здесь чётные члены имеют знак « + » , а нечётные - « - ». Так как в результате разложения получается 0, то следовательно, суммы их биномиальных коэффициентов равны между собой, поэтому каждая из них равна: что и требовалось доказать.

Рассмотрим несколько комбинаторных задач.

Задача 1

Есть 10 книг и 8 журналов. Требуется составить из них посылку, в которой было бы 3 книги и 5 журналов. Сколькими способами это можно сделать?

Решение задачи 1

Очевидно, что выбрать 3 книги из имеющихся 10 можно числом способов С₁₀³. Точно так же выбрать 5 журналов из 8 можно числом способом С₈⁵. Используя общий принцип подсчета числа комбинаций, получаем, что посылку можно составить С₁₀³ х С₈⁵=6 720 способами.

Задача 2

Сколько существует трехзначных чисел?

Решение задачи 2

При составлении трехзначного числа первую цифру можно выбрать 9 способами (она должна быть отличной от 0), вторую - 10 способами, третью - также 10 способами. По правилу произведения получим, что всего можно составить 9х10х10=900 различных трехзначных чисел.

Задача 3

Сколькими способами можно разделить колоду из 36 карт на две равные части, чтобы в каждой из них было бы по 2 туза?

Решение задачи 3

Ясно, что каждое такое разбиение колоды мы можем осуществить следующим образом: сначала выбрать 16 нетузов из 32 нетузов (это можно сделать числом способов С₃₂¹⁶), а затем выбрать 2 туза из 4 (это можно сделать С₄² =6 способами). По правилу произведения всего получаем С₃₂¹⁶ х С₄² способов.

Задача 4

Даны 12 точек, из которых 4 лежат на одной прямой. Больше никакие три точки не лежат на одной прямой. Сколько различных прямых можно провести, соединяя все эти точки попарно?

Решение задачи 4

Упомянутые в условии 4 точки, лежащие на одной прямой, назовем для краткости особыми. Тогда в число рассматриваемых прямых войдут следующие прямые: 1) соединяющие неособую точку с неособой, их будет С₈² =28, 2) соединяющие особую точку с неособой, их будет 4х8=32 и 3) одна прямая, на которой лежат особые точки. Таким образом, всего можно провести 61 прямую.

Задача 5

Имеется 3 черных, 1 белый, 1 синий и 1 красный шар. Сколько различных рядов по четыре шара можно из них составить?

Решение задачи 5

Ряды по четыре шара могут быть трех видов: содержащие один, два или три черных шара. В каждом ряду первого вида все шары различны, так что таких рядов будет Р₄=24. Подсчитаем число рядов второго вида. Чтобы получить такой ряд, надо прежде всего выбрать два места, на которых будут стоять черные шары, - это можно сделать С₄²=6 способами. Затем два оставшиеся места нужно заполнить двумя из трех оставшихся шаров - это можно сделать А₃²=6 способами. Всего рядов второго вида по правилу произведения будет 6х6=36. Точно так же подсчитывается число рядов третьего вида.

Оно равно С₄³ х А₃¹=4х3=12. Следовательно, всего можно составить 72 ряда.

Задача 6

Сколько можно составить четырехзначных чисел, у которых две цифры четные, а две нечетные?

Решение задачи 6

Рассмотрим два случая: когда число начинается с нечетной цифры и когда число начинается с четной цифры. В первом случае цифру, начинающую число, можно выбрать пятью способами. Затем тремя способами можно указать место для второй нечетной цифры и на это место поставить нечетную цифру, выбранную пятью способами. Каждое из двух оставшихся мест можно заполнить пятью способами, поставив на них любую четную цифру. По правилу произведения всего будем иметь 5х3х5х5х5=3х5⁴ чисел первого вида. Аналогично рассуждаем и во втором случае: только первую цифру на этот раз можно выбрать лишь четырьмя способами, так как она должна быть отличной от нуля. Во втором случае получим 4х3х5х5х5=12х5³ чисел. Следовательно, всего

3х5⁴ + 12х5³=27х5³ чисел.

Задача 7

Сколько существует шестизначных чисел, у которых сумма цифр нечетная?

Решение задачи 7

Ясно, что если к числу, оканчивающемуся на 9, прибавить 1, то четность суммы его цифр изменится. Поэтому, разбив все шестизначные числа на десятки: от 100 000 до 100 009, от 100 010 до 100 019 и т.д., - мы получим, что в каждом десятке будет равное количество чисел с четной и с нечетной суммой цифр. Так как всего шестизначных чисел

900 000, то чисел с нечетной суммой цифр будет 450 000.

Рассмотрим способы получения комбинаторных объектов и несколько олимпиадных задач.

1. Генерация всех подмножеств данного множества

2. Получение всех сочетаний из m по n

3. Алгоритм генерации перестановок в лексикографическом порядке

4. Генерация перестановок с использованием множества и рекурсии

5. Максимальная сумма

6. Выбор подмножества

7. Кратчайший путь

8. Японская полоска