Русская Википедия:Комбинаторные принципы

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

Шаблон:Main Интуитивно правило сложения утверждает, что если событие A имеет <math>a</math> возможных исходов, а событие B имеет <math>b</math> возможных исходов, причём только одно из этих событий может произойти, то общее число возможных результатов равноШаблон:Sfn <math>a+b</math>.

На языке теории множеств это правило означает, что размер объединения двух непересекающихся множеств равен сумме размеров этих множеств: если <math>A\cap B = \varnothing</math>, то <math>|A\cup B| = |A| + |B|</math> (здесь и далее символ <math>|A|</math> обозначает число элементов конечного множества <math>|A|</math>).

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

<math>9n9, n=0,1,2,\dots,8.</math> Всего 9 вариантов.
<math>99n, n=0,1,2,\dots,8.</math> Всего 9 вариантов.
<math>n99, n=1,2,3,\dots,8.</math> Всего 8 вариантов.

Согласно правилу сложения, всего таких чисел будет <math>9+9+8=26.</math>

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

Шаблон:Main Правило умножения — ещё один интуитивный принцип, утверждающий, что если есть <math>a</math> способов сделать что-то и <math>b</math> способов независимо сделать что-то другое, то существует <math>ab</math> способов сделать и то, и другое[2].

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

<math>0+6; 1+5; 2+4; 3+3; 4+2; 5+1; 6+0.</math> Всего 7 вариантов.

Аналогично и независимо синие кубики дают 9 вариантов, зелёные — 11. По правилу умножения общее число вариантов равно <math>7\cdot 9 \cdot 11=693</math> способа.

Файл:Inclusion-exclusion.svg
Включение – исключение для трёх множеств

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

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

<math>|A \cup B| = |A| + |B| - |A \cap B|</math>

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

<math>|A\cup B\cup C| = |A| + |B| + |C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C| </math>

В общем случае принцип утверждает[3]: если <math>A_1 \dots A_n</math> — конечные множества, то:

<math>

\begin{align} \biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right| -\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| \\ & {}\qquad +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|. \end{align}</math>

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

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

Шаблон:Main Комбинаторное определение: если задача решается с помощью процедуры, которая может быть выполнена <math>n</math> способами, причём для каждого способа существуют <math>d-1</math> неразличимых с ним результата, то всего существуют <math>n/d</math> различных способов выполнить задачу.

На языке теории множеств: если конечное множество <math>A</math> является объединением <math>n</math> попарно непересекающихся подмножеств, каждое из которых содержит <math>d</math> элементов, то <math>n = | A | / d.</math>

На языке функций: если функция <math>f</math> отображает конечное множество <math>A</math> на конечное множество <math>B,</math> причём прообраз каждого значения <math>b \in B</math> содержит ровно <math>d</math> значений из A, то <math>|B| = |A| / d.</math>

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

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

Шаблон:Main Принцип Дирихле в комбинаторике в простейшей формулировке гласит, что если <math>a</math> объектов разместить в <math>b</math> ящиках, причём <math>a>b,</math> то по крайней мере один ящик будет содержать более одного объекта[5]. С помощью этого принципа и его обобщений можно, например, продемонстрировать существование в множестве элемента с некоторыми специфическими свойствами.

Пример. Часть компании из <math>N</math> людей <math>(N>1)</math> обменивается рукопожатиями. Доказать, что в компании найдутся по крайней мере два человека, совершившие одинаковое число рукопожатий[6]. Доказательство. Определим <math>N</math> «ящиков» <math>H_0, H_1 \dots H_{N-1}</math> и занесём в ящик <math>H_k</math> тех участников компании, которые совершили <math>k</math> рукопожатий. Если ящик <math>H_0</math> не пуст, то один или более участников компании не совершили ни одного рукопожатия, а, значит, ящик <math>H_{N-1}</math> тогда пуст, потому что число совершивших рукопожатия получается тогда меньше <math>N.</math> Отсюда следует, что непустых ящиков всегда меньше, чем <math>N,</math> и, следовательно, по крайней мере один ящик соответствует двум или более людям. Шаблон:ЧТД

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

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

Пример. Докажем один из вариантов правила Паскаля: <math>C_{n+1}^{k+1} = C_n^{k+1} + C_n^k,</math> где <math>0\leqslant k\leqslant n-1,</math> а биномиальный коэффициент <math>C_n^m</math> одновременно характеризует число <math>m</math>-элементных подмножеств натурального интервала <math>\mathbb{R_n} = \{1,2,\dots n\}</math>. Сопоставим каждому <math>(k+1)</math>элементному подмножеству интервала <math>\mathbb{R_{n+1}}</math> само это подмножество, если оно не содержит числа <math>n+1,</math> или его же за вычетом <math>n+1,</math> если содержит. Несложно показать, что для каждого <math>k</math> получается биекция <math>(k+1)</math>-элементных подмножеств <math>\mathbb{R_{n+1}},</math> с одной стороны, и подмножеств <math>\mathbb{R_n}</math> длины <math>k+1</math> и <math>k</math>, с другой стороны. Этот факт и отражает правило ПаскаляШаблон:Sfn.

Файл:Aples.svg
Умножение 5 на 3 даёт тот же результат, как и умножение 3 на 5

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

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

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

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

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

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

Шаблон:Main Производящая функция последовательности <math>\{a_1, a_2, a_3 \dots \}</math> — это степенной ряд, коэффициенты которых соответствуют членам заданной последовательности.

<math>G(a_n; x)=\sum_{n=0}^{\infty}a_nx^n.</math>

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

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

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

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

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:ВС

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
  2. ↑ Ошибка цитирования Неверный тег <ref>; для сносок OKU25 не указан текст
  3. ↑ Ошибка цитирования Неверный тег <ref>; для сносок OKU26 не указан текст
  4. ↑ Шаблон:Cite web
  5. ↑ Шаблон:Книга
  6. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Комбинаторные_принципы&oldid=10153294