Комбинаторно-логический аппарат, формула включений и исключений
08.05.2012 |Пусть имеем 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
