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

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

Определение

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

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

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

Примеры

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

{n \choose k-1}+{n \choose k}={n+1 \choose k}.

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

{n \choose k-1}

. размера k Если подмножество не содержит выделенного элемента, то все его k членов выбираются из числа других n «невыделенных» элементов. Следовательно, число способов их выбора равно

{n \choose k}

.

Количество подмножеств любого размера n равно 2. набора ^н.

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

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

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

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

B_{n}+C_{n}=B_{n+1}.

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

См. также

Ссылки

^ Петковшек, Марко; Томаж Писанский (ноябрь 2002 г.). «Комбинаторная интерпретация беззнаковых чисел Стирлинга и Лаха» (PDF) . Серия препринтов Люблянского университета . 40 (837): 1–6 . Проверено 12 июля 2013 г.

[Petkovsek2002-1] Петковшек, Марко; Томаж Писанский (ноябрь 2002 г.). «Комбинаторная интерпретация беззнаковых чисел Стирлинга и Лаха» (PDF) . Серия препринтов Люблянского университета . 40 (837): 1–6 . Проверено 12 июля 2013 г.

[1]