Комбинаторные принципы

При доказательстве комбинаторных теорем обычно признаются и используются несколько полезных комбинаторных правил, или комбинаторных принципов. Примеры:

Правило сложения

Интуитивно правило сложения утверждает, что если событие A имеет возможных исходов, а событие B имеет возможных исходов, причём только одно из этих событий может произойти, то общее число возможных результатов равно[1] .

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

Пример. Выясним, сколько трёхзначных чисел содержат (в десятичной записи) ровно две девятки. Возможны три формата таких чисел[2]:

Всего 9 вариантов.
Всего 9 вариантов.
Всего 8 вариантов.

Согласно правилу сложения, всего таких чисел будет

Правило умножения

Правило умножения — ещё один интуитивный принцип, утверждающий, что если есть способов сделать что-то и способов независимо сделать что-то другое, то существует способов сделать и то, и другое[1].

Пример[3]. Имеется 6 красных, 8 синих и 10 зеленых кубиков. Выясним, сколькими способами они могут быть разложены в два ящика. Красные кубики можно распределить по двум ящикам так:

Всего 7 вариантов.

Аналогично и независимо синие кубики дают 9 вариантов, зелёные — 11. По правилу умножения общее число вариантов равно способа.

Включение – исключение для трёх множеств

Принцип включения-исключения

Принцип включения-исключения связывает размер объединения нескольких множеств с размером каждого множества и размерами их возможных пересечений[4]. Простейший пример: если имеются два множества, то количество элементов в их объединении равно сумме количеств элементов во множествах за вычетом количества элементов в их пересечении:

Эта формула обобщает приведённое выше правило суммы. Вариант для трёх множеств:

В общем случае принцип утверждает[4]: если конечные множества, то:

Пример[5]. В группе 40 туристов. Из них 20 человек говорят по-английски, 15 — по-французски, 11 — по-испански. Английский и французский знают семь человек, английский и испанский — пятеро, французский и испанский — трое. Два туриста говорят на всех трёх языках. Сколько человек группы не знают ни одного из этих языков? Подсчитаем по формуле включений-исключений общее число туристов, знающих хотя бы один из упомянутых языков: Следовательно, ответ:

Правило деления

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

На языке теории множеств: если конечное множество является объединением попарно непересекающихся подмножеств, каждое из которых содержит элементов, то

На языке функций: если функция отображает конечное множество на конечное множество причём прообраз каждого значения содержит ровно значений из A, то

Пример. Сколько существует различных способов усадить четырёх человек за круглый стол? Способы считаются различными, если хотя бы у одного человека сосед слева или справа отличается. Решение: если отбросить условие, то существует способа, но каждый способ имеет 3 «двойника», отличающиеся поворотом вокруг стола, и по условию задачи все они считаются за один способ. В итоге имеем различных способа.

Принцип Дирихле

Принцип Дирихле в комбинаторике в простейшей формулировке гласит, что если объектов разместить в ящиках, причём то по крайней мере один ящик будет содержать более одного объекта[6]. С помощью этого принципа и его обобщений можно, например, продемонстрировать существование в множестве элемента с некоторыми специфическими свойствами.

Пример. Часть компании из людей обменивается рукопожатиями. Доказать, что в компании найдутся по крайней мере два человека, совершившие одинаковое число рукопожатий[7]. Доказательство. Определим «ящиков» и занесём в ящик тех участников компании, которые совершили рукопожатий. Если ящик не пуст, то один или более участников компании не совершили ни одного рукопожатия, а, значит, ящик тогда пуст, потому что число совершивших рукопожатия получается тогда меньше Отсюда следует, что непустых ящиков всегда меньше, чем и, следовательно, по крайней мере один ящик соответствует двум или более людям.

Биективное доказательство

Биективные доказательства используется для доказательства того, что два конечных множества имеют одинаковое число элементов; они особенно полезны в тех случаях, когда число элементов в одном множестве найти проще, чем в другом. В ходе доказательства строится биективная функция (взаимно однозначное соответствие) между этими множествами.

Пример. Докажем один из вариантов правила Паскаля: где а биномиальный коэффициент одновременно характеризует число -элементных подмножеств натурального интервала . Сопоставим каждому элементному подмножеству интервала само это подмножество, если оно не содержит числа или его же за вычетом если содержит. Несложно показать, что для каждого получается биекция -элементных подмножеств с одной стороны, и подмножеств длины и , с другой стороны. Этот факт и отражает правило Паскаля[8].

Умножение 5 на 3 даёт тот же результат, как и умножение 3 на 5

Метод двойного счёта

Двойной счет — это метод, который приравнивает два выражения для размера исследуемого множества, полученные двумя разными способами[9]. Данный метод чрезвычайно полезен, например, для получения комбинаторных тождеств.

Простейший пример (см. рисунок): подсчёт объектов в прямоугольной таблице по строкам и по столбцам приводит к одному и тому же результату, откуда следует коммутативность умножения.

Метод выделенного элемента

Метод выделенного элемента отмечает некоторый «выделенный элемент» множества для доказательства нужного результата.

Производящая функция

Производящая функция последовательности — это степенной ряд, коэффициенты которых соответствуют членам заданной последовательности.

Это представление часто позволяет применить к комбинаторным задачам мощные методы математического анализа[10].

Рекуррентное соотношение

Рекуррентное соотношение определяет каждый член последовательности, кроме начального, через предыдущие члены[11]. Пример: числа Фибоначчи.

Рекуррентное соотношение могут привести к ранее неизвестным свойствам последовательности, но обычно выражения в закрытой форме для членов последовательности более желательны.

Примечания

  1. Окулов, 2012, с. 25.
  2. Комбинаторика: правила суммы и произведения. Фоксфорд. Дата обращения: 21 ноября 2020.
  3. Окулов, 2012, с. 49, 285.
  4. Окулов, 2012, с. 26—28.
  5. Яковлев И. В. Формула включений и исключений. Дата обращения: 21 ноября 2020.
  6. Дирихле принцип, ящики // Математическая энциклопедия (в 5 томах). М.: Советская Энциклопедия, 1982. — Т. 2. — С. 182.
  7. Принцип Дирихле. Дата обращения: 30 марта 2020.
  8. Глибичук и др., 2016, с. 9—10.
  9. Глибичук и др., 2016, с. 18—20.
  10. Окулов, 2012, с. 90.
  11. Окулов, 2012, с. 76.

Литература

  • Глибичук А. А., Дайняк А. Б., Ильинский Д. Г., Купавский А. Б., Райгородский А. М., Скопенков А. Б., Чернов А. А. Элементы дискретной математики в задачах. М.: МЦНМО, 2016. — 174 с. — ISBN 978-5-4439-3024-4.
  • Окулов С. М. Дискретная математика. Теория и практика решения задач по информатике: учебное пособие. — 2-е изд. М.: БИНОМ. Лаборатория знаний, 2012. — 422 с. — (Педагогическое образование). — ISBN 978-5-9963-0893-4.
  • J. H. van Lint, R. M. Wilson (2001), A Course in Combinatorics (Paperback), 2nd edition, Cambridge University Press. ISBN 0-521-00601-5.

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.