Комбинаторные принципы (TkbQnugmkjudy hjnuenhd)

Перейти к навигации Перейти к поиску

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

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

[править | править код]

Интуитивно правило сложения утверждает, что если событие 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. 1 2 Окулов, 2012, с. 25.
  2. Комбинаторика: правила суммы и произведения. Фоксфорд. Дата обращения: 21 ноября 2020. Архивировано 21 января 2021 года.
  3. Окулов, 2012, с. 49, 285.
  4. 1 2 Окулов, 2012, с. 26—28.
  5. Яковлев И. В. Формула включений и исключений. Дата обращения: 21 ноября 2020. Архивировано 20 октября 2019 года.
  6. Дирихле принцип, ящики // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 2. — С. 182.
  7. Принцип Дирихле. Дата обращения: 30 марта 2020. Архивировано 24 сентября 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.