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

Этот раздел посвящен важному комбинаторному методу - принципу включений-исключений, известному также под названиями: символический метод, принцип перекрестной классификации, метод решета. Логическое тождество, на котором основаны все эти методы, известны давно. Еще в 1713 году Монмор эффективно использовал упомянутый метод в решении знаменитой задачи о встречах (о числе перестановок из n элементов, в которых ни один элемент не сохраняет своей позиции).

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

Принцип включений-исключений в перечислительной комбинаторике есть метод определения мощности множества S, который начинает с большего множества и каким-либо путем вычитает или аннулирует нежелательные элементы. Сначала дается приблизительный ответ, содержащий большее число элементов, затем вычитается число элементов, большее чем ошибка, полученная на первом шаге, пока мы не придем к правильному ответу. Это комбинаторная сущность принципа включения-исключения.

Для примера рассмотрим принцип включений- исключений в теоретико множественной форме.

Пусть даны два конечных множества A и B.

Тогда

çAÇBç= çAç + çBç - çAÈBç.

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

Совершенно аналогичные рассуждения позволяют выписать формулу для количества элементов в объединении трех множеств A, B, и C:

çAÇBÇСç= çAç + çBç +çСç - çAÈBç - çAÈСç - çBÈCç + çAÈBÈCç.

Вычитая дважды учтенные элементы попарных пересечений, мы трижды вычли элементы, принадлежащие пересечению всех трех множеств. Добавление мощности пересечения AÈBÈC приводит к нужному результату.

Пусть имеется N объектов и n различных свойств a₁, a₂,..., a_n. Каждый из объектов может обладать любым из этих свойств (в любом наборе), т.е. обладать любым набором этих свойств, или не обладать никаким из свойств.

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

В общем случае пусть N - число объектов, обладающих свойствами (и, быть может, некоторыми другими).

Пусть N₀- число предметов, не обладающих ни одним из свойств a₁,..., a_n.

Пусть - число объектов, не обладающих свойством a₁. Чертой над символом свойства будем указывать, что речь идет об объектах, не обладающих таким свойством. Тогда в принятом обозначении N₀= = .

Теорема 1.13. ( Формула включений - исключений).

. (1.16)

Прежде, чем переходить к доказательству, вернемся к ранее рассмотренному примеру с тремя множествами A, B, C. Пусть свойством a₁обладают все элементы множества A, свойством a₂обладают все элементы множества B, свойством a₃- все элементы, принадлежащие множеству C. Тогда очевидно, что количество элементов, не обладающих ни одним из свойств a₁ , a₂ , a₃ , равно 0 (каждый элемент принадлежит хотя бы одному из множеств), и в соответствии с формулой (1.16) имеем

Доказательство. Доказательство проводится индукцией по n - числу свойств. При одном свойстве a формула очевидна. Каждый объект либо обладает этим свойством, либо не обладает им. Поэтому N₀= N - N(a).

Предположим теперь, что для случая, когда число свойств равно n-1, формула доказана:

N₀= N - N(a₁) - ... - N(a_n-1) + N(a₁,a₂) + ... + N(a_n-2, a_n-1) + + (-1)^n-1 N(a₁, a₂ ,..., a_n-1). (1.17)

Отметим очевидное соотношение:

(1.18)

Формула (1.17) по предположению справедлива для любой совокупности объектов. В частности она верна для совокупности элементов, обладающих свойством a_n. Применим индуктивное предположение к совокупности N(a_n) для вычисления :

(1.19)

Вычтем равенство (1.19) из (1.17). В правой части получим то, что нужно - правую часть формулы включения-исключения, а в левой части получим разность (1.18). Тем самым формула (1.16) доказана. ð

Для того, чтобы облегчить всестороннее использование этой формулы, сделаем следующие замечания. Во-первых, лучше всего она запоминается в следующей “символической записи”:

Сначала вычисляется содержимое квадратных скобок, а затем знак функции N применяется к слагаемым:

N[a+b]= N(a)+N(b),

N[-a]=-N(a),

N[1]=N,

N[(1-a)(1-b)]=N(1-a-b+ab)=N-N(a)-N(b)+N(a,b).

Далее, как видно из доказательства формулы включений - исключений, совокупности объектов, к которым применима теорема, не обязана быть совокупностью N всех объектов. Поэтому

N(a_{1 2}a_{3 4})=N[a₁(1-a₂)a₃(1-a₄)]=N(a₁a₃) - N(a₁a₂a₃) -

-N(a₁a₃a₄) + N(a₁a₂a₃a₄).

Вообще, если n различных свойств a₁,...,a_nобъектов из совокупности N объектов обозначить , то

.ð

Рассмотрим принцип включений- исключений в несколько более общей форме. Пусть S - множество свойств, которыми элементы данного множества A могут обладать, а могут не обладать. Для любого подмножества T множества S, TÍS, пусть N₌(T) - число объектов множества A, которые обладают в точности свойствами из T (так что они не обладают никакими другими свойствами из ). Пусть N_³(T) - число объектов множества A, обладающих по меньшей мере свойствами из T (и, возможно, какими-то другими свойствами). Ясно, что тогда

, (1.20)

, (1.21)

,

где Y пробегает все подмножества множества S.

В типичных приложениях принципа включений-исключений относительно легко вычислить N_³(Y) для YÍS, так что нами получена окончательная формула для N₌ (T).

Распространенным частным случаем принципа включения-исключения является выполнение условия N₌(T) = N₌(T^¢), как только êT ê= ê T^¢ ê. В рассматриваемом частном случае количество объектов, обладающих в точности заданным множеством свойств, зависит не от конкретного набора свойств, а только от числа рассматриваемых свойств. таким образом, N_³(T) зависит также только от çT ç и мы полагаем

a(n - i) = N₌(T) (1.22)

и

b(n - i) = N_³(T), (1.23)

если êT ê= i.

Из формул (1.20) и (1.21) получаем, что формулы

, (1.24)

и

, (1.25)

эквивалентны. Это еще одно отражение комбинаторных соотношений взаимности.

Не нашли, что искали? Воспользуйтесь поиском по сайту: