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

В математической области перечислительной комбинаторики тождества иногда устанавливаются с помощью аргументов, которые опираются на выделение одного «выдающегося элемента» множества.

Пусть будет семейством подмножеств множества и пусть будет выделенным элементом множества . Тогда предположим, что существует предикат , связывающий подмножество с . Обозначим как множество подмножеств из , для которого истинно, а как множество подмножеств из , для которого ложно, Тогда и являются непересекающимися множествами, поэтому по методу суммирования мощности являются аддитивными ^[1]${\displaystyle {\mathcal {A}}}$${\displaystyle А}$${\displaystyle x\in A}$${\displaystyle А}$ ${\displaystyle P(X,x)}$${\displaystyle X\subseteq A}$${\displaystyle x}$${\displaystyle {\mathcal {A}}(x)}$${\displaystyle X}$${\displaystyle {\mathcal {A}}}$${\displaystyle P(X,x)}$${\displaystyle {\mathcal {A}}-x}$${\displaystyle X}$${\displaystyle {\mathcal {A}}}$${\displaystyle P(X,x)}$${\displaystyle {\mathcal {A}}(x)}$${\displaystyle {\mathcal {A}}-x}$

${\displaystyle |{\mathcal {A}}|=|{\mathcal {A}}(x)|+|{\mathcal {A}}-x|}$

Таким образом, выделенный элемент допускает разложение по предикату, который является простой формой алгоритма «разделяй и властвуй» . В комбинаторике это позволяет строить рекуррентные отношения . Примеры приведены в следующем разделе.

• Биномиальный коэффициент — это число подмножеств размера k множества размера n . Базовое тождество — одним из следствий которого является то, что биномиальные коэффициенты — это в точности числа, появляющиеся в треугольнике Паскаля — гласит, что:${\displaystyle {n \выберите k}}$

${\displaystyle {n \выберите k-1}+{n \выберите k}={n+1 \выберите k}.}$

Доказательство: В наборе размера ( n  + 1) выберите один выделенный элемент. Набор всех подмножеств размера k содержит: (1) все подмножества размера k , которые содержат выделенный элемент, и (2) все подмножества размера k , которые не содержат выделенный элемент. Если подмножество размера k набора размера ( n  + 1) содержит выделенный элемент, то его другие k  − 1 элементов выбираются из числа других n элементов нашего набора размера ( n  + 1). Таким образом, число способов их выбора равно . Если подмножество размера k не содержит выделенного элемента, то все его k членов выбираются из числа других n «невыделенных» элементов. Таким образом, число способов их выбора равно .${\displaystyle {n \выберите k-1}}$${\displaystyle {n \выберите k}}$

• Число подмножеств любого множества размера n равно 2 ⁿ .

Доказательство: Мы используем математическую индукцию . Основой для индукции является истинность этого предложения в случае n  = 0. Пустое множество имеет 0 членов и 1 подмножество, и 2 ^{· 0}  = 1. Гипотеза индукции является предложением в случае n ; мы используем ее для доказательства случая n  + 1. В множестве размера ( n  + 1) выберите выделенный элемент. Каждое подмножество либо содержит выделенный элемент, либо нет. Если подмножество содержит выделенный элемент, то его оставшиеся элементы выбираются из числа других n элементов. По гипотезе индукции число способов сделать это равно 2 ⁿ . Если подмножество не содержит выделенного элемента, то оно является подмножеством множества всех невыделенных элементов. По гипотезе индукции число таких подмножеств равно 2 ⁿ . Наконец, весь список подмножеств нашего множества размера ( n  + 1) содержит 2 ⁿ  + 2 ⁿ  = 2 ^{n +1} элементов.

• Пусть B _n будет n-ым числом Белла , т. е. числом разделов набора из n элементов . Пусть C _n будет общим числом "частей" (или "блоков", как их часто называют комбинаторики) среди всех разделов этого набора. Например, разделы набора размера 3 { a ,  b ,  c } можно записать следующим образом:

${\displaystyle {\begin{matrix}abc\\a/bc\\b/ac\\c/ab\\a/b/c\end{matrix}}}$

Мы видим 5 разделов, содержащих 10 блоков, поэтому B ₃  = 5 и C ₃  = 10. Тождество гласит:

${\displaystyle B_{n}+C_{n}=B_{n+1}.}$

Доказательство: В наборе размера ( n  + 1) выберите выделенный элемент. В каждом разделе нашего набора размера ( n  + 1) выделенный элемент является «синглтоном», т. е. набор, содержащий только выделенный элемент, является одним из блоков, или выделенный элемент принадлежит большему блоку. Если выделенный элемент является синглтоном, то удаление выделенного элемента оставляет раздел набора, содержащий n невыделенных элементов. Есть B _n способов сделать это. Если выделенный элемент принадлежит большему блоку, то его удаление оставляет блок в разделе набора, содержащем n невыделенных элементов. Есть C _n таких блоков.

• Комбинаторные принципы
• Комбинаторное доказательство