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

Пусть имеем 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-ю свойствами.

Свойства
Объекты 1 2 3 4 5
1 1 1 0 1 0
2 0 0 0 0 0
3 1 1 1 1 1
4 1 0 1 0 0
5 0 0 0 0 1
6 0 0 0 0 1


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


Оставить комментарий





Статистика

Рейтинг@Mail.ru