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

1.1. Вывод формулы. Пусть имеем N объектов и некий набор параметров а1, …, аn, которыми могут владеть эти объекты. Обозначим N(i) – число объектов, владеющих свойством аi, и вообщем N(i1, …, ik) – число объектов, владеющих сразу всеми качествами . Пусть N(0) – число объектов, не владеющих ни одним из параметров аi. Справедлива формула включения и исключения Принцип включения и исключения:

N(0) = N – + + …

+ (– 1)k + … + (–1)n N(1, 2, … , n). (3.1)

Знак 1 £ i1 < i2 <…< ik £ n под знаком суммы значит, что суммирование ведется по всем композициям i1, i2,…, ik так, чтоб производилось обозначенное соотношений. Подтверждение проведем при помощи индукции по n – число параметров.

10. n = 1. N(0) = N – N(1). Всего существует одно свойство. От Принцип включения и исключения общего числа объектов отнимем количество объектов, владеющих этим свойством – узнаем, сколько объектов этим свойством не владеют.

20. Пусть для n – 1 параметров справедлива формула

N(0) = N – + + …

+ (– 1)k + … + (–1)n N(1, 2, … , n – 1). (3.2)

Пусть сейчас имеем огромное количество, все элементы которого владеют свойством аn, и, может быть, владеют качествами а1, …, аn–1. Разумеется, для этого огромного Принцип включения и исключения количества формула (3.2) также верна и имеет вид:

N(0, n) = N(n) – + … +

+(–1)n–2 + (–1)n–1N(1, 2, … , n – 1, n). (3.3)

В (3.3) всюду в скобках дописано n, т.к. все элементы огромного количества свойством аn владеют. Вычтем (3.3) из (3.2):

N(0) – N(0, n) = N – + + … – (–1)n–1 N(1, 2, … , n – 1, n).

Отсюда

N(0) – N(0, n) = N – + +… + (–1)n N(1, 2,…,n Принцип включения и исключения).

Справа мы получили требуемую формулу. А что слева? N(0) – число частей, не владеющих качествами а1, …, аn–1, но, может быть, владеющих свойством аn. N(0, n) – число частей, не владеющих качествами а1, …, аn–1, но непременно владеющих свойством аn. Как следует, N(0) – N(0, n) – число частей, не владеющих ни одним из параметров а1, …, аn Принцип включения и исключения, т.е. требуемая величина. Формула подтверждена.

Пример 3.1. Предводитель класса подал последующие сведения о классе. Всего в классе 45 учеников, из их 25 мальчишек. 30 человек обучается без троек, из их – 16 мальчишек; 28 человек занимаются спортом, из их – 18 мальчишек и 17 хорошистов и отличников; 15 мальчишек обучаются без троек и сразу занимаются спортом. Потрясающий управляющий пристально поглядел Принцип включения и исключения перечень и произнес, что в сведениях есть ошибка. Как он это вызнал?

Решение. Обозначим a1 – свойство принадлежности к мужскому полу; a2 – отменная успеваемость; a3 – занятие спортом. Тогда N = 45, N(1) = 25, N(2) = 30, N(3) = 28, N(1, 2) = 16, N(1, 3) = 18, N(2, 3) = 17, N(1, 2, 3) = 15. Итого N(0) = 45 – 25 - 30 – 28 + 16 + 18 + 17 – 15 = – 2 – ошибка.

1.2. Модификации формулы включения и исключения

2.а. Формулу (2.1) можно обобщить для определения Принцип включения и исключения числа частей, владеющих в точности k качествами (0 £ k £ n):

N(k) = + …+ (– 1)s–k + …

+ (–1)n–k ×N(1, 2, … , n). (3.4)

Пример 3.2. В отделе НИИ каждый сотрудник обладает хотя бы одним зарубежным языком. Понятно, что английским языком обладают 6 человек, германским – 6, французским – 7, английским и германским – 4, германским и французским – 3, английским и французским – 2, все Принцип включения и исключения три языка знает 1 человек. Найти, сколько всего человек в отделе, сколько человек обладают только английским, только германским, только французским, и сколько человек знает только 1 зарубежный язык.

Решение. Согласно условиям задачки N(0) = 0, т.к. в отделе нет служащих, не обладающих зарубежными языками. Как следует, по формуле (3.1) получаем:

N = – + N(1, 2, 3) (3.5)

N = 6 + 6 + 7 – 4 – 3 – 2 + 1 = 11 человек Принцип включения и исключения всего в отделе.

Для вычисления других характеристик также воспользуемся формулой (3.5). Найдем, к примеру N(только А) – число человек, не обладающих никаким другим языком, не считая британского. Для этого формулу (3.5) нужно применить только к огромному количеству людей, обладающих английским языком. В данном случае n = 2. Тогда N = N(A), N(1) и N Принцип включения и исключения(2) – число людей, обладающих кроме британского еще германским и французским, соответственно, N(1, 2) – число людей, обладающих кроме британского еще сразу германским и французским. Отсюда

N(только A) = N(A) – N(А и Н) – N(А и Ф) + N(А и Н и Ф) =

6 – 4 – 2 + 1 = 1.

Аналогично

N(только Н) = N(Н) – N(А и Н) – N Принцип включения и исключения(Н и Ф) + N(А и Н и Ф) =

6 – 4 – 3 + 1 = 0.

N(только Ф) = N(Ф) – N(Ф и А) – N(Ф и Н) + N(А и Н и Ф) =

7 –2 – 3 + 1 = 3.

Вычислим сейчас N(1) – число людей, обладающих только 1 языком. Воспользуемся формулой (3.4) при k = 1.

N(1) = N(А) + N(Н) + N(Ф) + (–1)2–1× × [N(А Принцип включения и исключения и Н) + N(Н и Ф) + N(А и Ф)] + (–1)3–1× × N(А и Н и Ф) = 6 + 6 + 7 – 2×(4 + 3 + 2) + 3×1 = 4.

Таковой же итог получим, если сложим N(только A) + N(только Н) + N(только Ф).

2.б. Формулу (3.1) можно также интерпретировать, как подсчет мощностей пересечений разных множеств, т.е. дать теоретико-множественное представление Принцип включения и исключения принципа включения и исключения. Пусть имеем некое конечное огромное количество А и его подмножества Аj, j = 1,…, n. Тогда теоретико-множественный аналог формулы (3.1) будет иметь вид:

= |A| – + + …

+ (– 1)k + …+ (–1)n .

Формулы воззвания

2.1. Аксиома воззвания. Пусть имеем два семейства комбинаторных чисел {an,k} и {bn,k}, зависящих от целочисленных характеристик n Принцип включения и исключения, k, при этом 0 £ k £ n.

Аксиома 3.1.Пусть для всех n и k, 0 £ k £ n справедливы зависимости и пусть есть такие числа mn,k,i, что для всех k £ n и m £ n производятся равенства

Тогда для всех k £ n имеет место формула воззвания:

.

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

= = = bn,k,

что и требовалось обосновать Принцип включения и исключения.

2.2. Примеры использования формулы воззвания. Зависимость меж числами ln,k,i и mn,k,i, фигурирующая в критериях аксиомы 3.1, на самом деле значит, что эти числа образуют систему взаимно оборотных матриц, т.е. смысл аксиомы очень прост, если не сказать – банален. Для случайных чисел an,k и bn,k она Принцип включения и исключения не дает никакой ценной инфы, так как отыскать требуемые числа mn,k,i в общем случае настолько же тяжело, как и решить начальную систему уравнений относительно bn,k. Но, для многих особых случаев, а именно, комбинаторных чисел, удается отыскать mn,k,i в очевидном виде. В этом особенность данной формулы. Разглядим Принцип включения и исключения ее применение для воззвания биномиальных коэффициентов.

Лемма 3.1.

Подтверждение.Имеем:

= =

= = .

Как следует,

= = В.

Потому что при k n , то в приобретенном выражении можно суммировать не от i = 0, i = m. Другими словами

В = = .

Но при m < n имеем:

= = 0.

Последнее равенство следует из характеристики 5 чисел сочетания.

А при m = n имеем:

= = 1,

что и Принцип включения и исключения требовалось обосновать.

Аксиома 3.2.Если , то .

Подтверждение. Тут и . При k £ n, m £ n имеем:

= = = =

Это значит, что выполнены условия аксиомы 3.1, а, как следует, аксиома подтверждена.

Аксиома 3.3.Если , то .

Подтверждение аналогично.


princip-ekvivalentnosti-ejnshtejna.html
princip-folksvagena-dzhetta-vi-vozdejstvuete-na-pole-i-izvlekaete-iz-nego-to-chto-sootvetstvuet-vashim-ubezhdeniyam-i-ozhidaniyam.html
princip-funkcionirovaniya-elektrofiltrov.html