Комбинаторно-логический аппарат, формула включений и исключений


Пусть имеем N объектов, которые могут обладать или не обладать n свойствами 1,2,..,n

Примем следующие обозначения:
N(0) [или N(⎤1,⎤2,..,⎤n)]-число объектов, не обладающих ни одним из свойств 1,2,..,n.
N(i1,i2,..,ir)-число объектов, обладающих свойствами i1,i2,..,ir (возможно и другими свойствами)
N=K — число объектов, обладающих в точности К свойствами.
N>=K — число объектов, обладающих не менее, чем К свойствами.

Найдём формулы для вычисления всех этих чисел.

Пример: пусть имеем 6 объектов, которые могут обладать или не обладать 5-ю свойствами.

Свойства
Объекты12345
111010
200000
311111
410100
500001
600001


N(1)=3 – число объектов, обладающих 1-ым свойством
N(2)=2; N(3)=2; N(4)=2; N(5)=3
N(1,2)=2
N(3,4)=1
N(1,3,5)=1
N(1,2,3,4)=1
N(1,3)=2
N(3,5)=1
N(1,4,5)=1
N(1,2,3,5)=1
N(1,4)=2
N(4,5)=1
N(2,3,4)=1
N(1,2,4,5)=1
N(1,5)=1
N(1,2,3)=1
N(2,3,5)=1
N(1,3,4,5)=1
N(2,3)=1
N(1,2,4)=2
N(2,4,5)=1
N(2,3,4,5)=1
N(2,4)=2
N(1,2,5)=1
N(3,4,5)=1
N(1,2,3,4,5)=1
N(2,5)=1
N(1,3,4)=1

Заметим: число объектов, не обладающих ни одним из свойств 1-4: N(⎤1,⎤2,⎤3,⎤4)=3;

Сюда включаются объекты, обладающие свойством 5 (объекты 5,6) и не обладающие свойством 5 (объект 2);
число объектов, не обладающих свойствами 1-4 и обладающих 5 :
N(⎤1,⎤2,⎤3,⎤4,5)=2;
число объектов, не обладающих ни одним из свойств 1-5 :
N(0)=N(⎤1,⎤2,⎤3,⎤4,⎤5)= N(⎤1,⎤2,⎤3,⎤4)- N(⎤1,⎤2,⎤3,⎤4,5)=3-2=1;
В общем случае
N(0)=N(⎤1,⎤2,⎤3,..,⎤n)=N(⎤1,⎤2,⎤3,…,⎤(n-1)) – N(⎤1,⎤2,⎤3,…,⎤(n-1),⎤n);

Теорема Справедлива следующая формула включений и исключений:
N(0) = N — ∑N(i) + ∑N(i1,i2) — … + (-1)r ∑N(i1, i2, …, ir) + … + (-1)nN(1,2,…,n)

Доказательство: Обозначим Sr = ∑N(i1, i2, …, ir)
Далее индукция по числу свойств n.

Базис: n=1

N(0)=N-N(1)-N-S1

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

Шаг индукции:
покажем, что формула включений и исключений справедлива для n свойств:
N(0)=N-S1+S2-…+(-1)rSr+…+(-1)nSn
По предположению индукции для свойств 1,2,…,n-1 имеем
N(¬1,¬2,…,¬(n-1))=N-S1+S2-…+(-1)n-1Sn-1= N — ∑N(i) + ∑N(i1, i2) — … + (-1)n-1N(1,2,…,n-1)
Эта формула справедлива и для n свойств при фиксировании последнего слова n:
N(¬1,¬2,¬3,…,¬(n-1),n)= N(n) — ∑N(i,n) + ∑N(i1,i2,n) — … + (-1)n-1N(1,2,..,n-1,n)
Вычтем последнюю формулу из предпоследней:
N(¬1,¬2,…,¬(n-1))-N(¬1,¬2,…,¬(n-1),n)=N(0)= ∑(-1)r∑N(i1, i2, …,ir)

Шаг индукции установлен. Теорема доказана.

Замечание:
1. Аналогично можем показать справедливость двух следующих формул (включения и исключения).
N=k= ∑(-1)jCk+jj ∑N(i1, i2, …,ik+j)
N≥k= ∑(-1)jCk-1+jk-1 ∑N(i1, i2, …,ik+j)
2. На практике таблицы распределения свойств по предметам, но есть значения для N(i1,i2,…,ir). Тогда применяют формулу включений и исключений.

Пример: найти число положительных натуральных чисел не больших 1000 и не делящихся на 3, 5, 7. Пусть имеем следующие свойства, пусть имеем следующие свойства, которыми могут обладать или не обладать числа:1, 2,…., 1000.
1) Число n делиться на 3.
2) Число n делиться на 5.
3) Число n делиться на 7.

СвойстваМножества чисел, обладающих этими свойствамиЧисло
1{ 3*k:k=1, 2,…., 333 }N(1)=333
2{ 5*k:k=1, 2,…., 200 }N(2)=200
3{ 7*k:k=1, 2,…., 142 }N(3)=142
1, 2{ 15*k:k=1, 2,…., 66 }N(1,2)=66
2, 3{ 35*k:k=1, 2,…., 28 }N(2,3)=28
2, 3{ 21*k:k=1, 2,…., 47 }N(1,3)=47
1, 2, 3{ 105*k:k=1, 2,…., 9 }N(1,2,3)=9


По формуле включений и исключений, число чисел, не обладающих ни одним из свойств 1, 2, 3, т.е. не делящихся ни на одно из чисел 3, 5, 7, есть
N(0) = 1000 — ∑N(i) + ∑N(i,j) — N(1,2,3) = 1000 — (333 + 200 +142) + (66 + 47 + 28) — 9 = 457
Приложения формулы включений и исключений.
Задача о беспорядках:
Пусть имеем множество М={1,2,…,n} из n элементов и подстановку (т.е. взаимнооднозначное соответствие) S:M→M.
Подстановка S обладает свойством i, если S(i)=i, т.е. подстановка S элемент i переводит в себя. Подстановка S есть беспорядок, если S(i)≠i, ∀ i∈M.

Замечание N(0) ≈ n! ∑(-1)r 1/r! ≈ n! ∑(-1)r 1/r! = n!/e-1, т.е. число беспорядков N(0) ≈ n!/e-1


Комментарии запрещены.




Статистика