ФОРМУЛА ВКЛЮЧЕНИЙ-ИСКЛЮЧЕНИЙ

Пусть A и B - произвольные огромного количества. Тогда мощность их объединения может быть определена по формуле:

|A È B| = |A| + |B| -|A Ç B|. (1)

Если разглядеть объединение 3-х множеств A, B и С, то справедлива последующая формула:

|AÈBÈС|=|A|+|B|+|С|-|AÇB|-|AÇC|-|BÇC|+|AÇBÇC|. (2)

Справедливость каждой их приведенных формул просто может быть испытана при помощи диаграмм Венна для случайных 2-ух и 3-х множеств. Для этого довольно посчитать, сколько раз ФОРМУЛА ВКЛЮЧЕНИЙ-ИСКЛЮЧЕНИЙ учитывается в правой и левой части каждого равенства всякий элемент объединения.

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

Считается, что в общем случае объединения множеств устроены труднее, чем скрещения множеств. К примеру ФОРМУЛА ВКЛЮЧЕНИЙ-ИСКЛЮЧЕНИЙ, огромное количество AÈBÈС в общем случае может рассматриваться как более разнородное, чем каждое из входящих в него множеств A, B и С, так как содержать элементы владеющие и не владеющие качествами частей множеств A, B и С, в различных композициях, в каких довольно выполнимости только 1-го из параметров частей этих множеств.

Вправду, в A È B È С могут содержаться ФОРМУЛА ВКЛЮЧЕНИЙ-ИСКЛЮЧЕНИЙ элементы, владеющие только свойством частей огромного количества A. Там же могут содержаться элементы не из A, но владеющие качествами частей множеств B либо C.

Огромного количества, мощности которых употребляются в правых частях формул (1) и (2), образованы пересечениями отдельных множеств и потому более однородны, так как все их элементы владеют одним и этим же свойством ФОРМУЛА ВКЛЮЧЕНИЙ-ИСКЛЮЧЕНИЙ, представляемым конъюнкцией параметров частей множеств входящих в скрещение.

Приведенные формулы (1) и (2) могут быть обобщены на случай объединения случайного конечного числа множеств так, чтоб свести задачку нахождения мощности объединения множеств к серии задач, связанных с нахождением мощностей нескольких пересечений множеств.

Пусть заданы конечные огромного количества A1 , ... , Ak и такое число ФОРМУЛА ВКЛЮЧЕНИЙ-ИСКЛЮЧЕНИЙ i, что 0 £ i £ k. Обозначим как ni сумму мощностей всех вероятных пересечений по i таких множеств.

Заметим, что ni является суммой слагаемых, потому что существует ровно столько разных пересечений по i множеств из k.

Аксиома 2.1

| Ai | = n1 + ... + (-1)i-1ni + ... + (-1)k-1nk. (1)

Подтверждение

Пусть a - это случайный элемент, входящий в Ai .

Покажем, что в левой и правой частях равенства ФОРМУЛА ВКЛЮЧЕНИЙ-ИСКЛЮЧЕНИЙ (1) этот элемент огромного количества A учитывается ровно один раз.

Для левой части (1) разумеется, что это так.

Разглядим правую часть доказываемого равенства. Представим, что a содержится в r различных огромных количествах из множеств A1, ... , Ak. Тогда:

- в n1 элемент a учтен раз;

- в n2 элемент a учтен раз;

. . .

- в nr элемент a учтен раз.

В следующих слагаемых правой части (1) элемент a не ФОРМУЛА ВКЛЮЧЕНИЙ-ИСКЛЮЧЕНИЙ учитывается никогда.

Потому в выражении:

n1 +... + (-1)i-1 ni+ ...+(-1)k-1nk

элемент aучтен ровно

+ ... + (-1)i-1 + ... + (-1)r-1 раз.

Докажем равенство:

+ ... + (-1)i-1 + ... + (-1)r-1 = 1.(2)

Перенесем все члены этого равенства в правую часть и с учетом того, что = 1, получим:

0= - + ... + (-1)i + ... + (-1)r . (3)

Воспользуемся формулой двучлена Ньютона:

(1 - x)r = - x+... + (-1)i xi +...+(-1)r xr.

Разумеется, что формула (3) - личный случай двучлена Ньютона для x = 1.

Означает, равенство (2) является справедливым. Потому элемент ФОРМУЛА ВКЛЮЧЕНИЙ-ИСКЛЮЧЕНИЙ a учитывается в правой части формулы (1) ровно один раз.


fotofakti-v-aeroportu-tolmachyovo-startovala-blagotvoritelnaya-akciya-vramkah-moskovskoj-mezhdunarodnoj-knizhnoj-vistavki-yarmarki.html
fotograficheskaya-priroda-kino.html
fotografii-obekta-ocenki.html