Введение в прикладную комбинаторику, Кофман А. (984071), страница 10
Текст из файла (страница 10)
П А„, П А„) Сагд А — Сагг! А,— — Сагг(Аз —... — Сагб А„+ Сагг((А, ПА,)+ Сагг( (А, П А,) -1-... ... + Сагд(А„, П А„) — Сагг!(А, ПА,й А ) — ... ... — Сагд(А зйА„,ПА„)+ ... ... +( — 1)" Саго (А,ПАзй ... ПА„). (12.7) Действуем по индукции. Имеем Сагг!(А, П Азй ... П Ае) = = Саго (А, П Аз П . П А„,) — Сагг) (А, П Аз П ...
П А„), (12,8) ') По хорошо известной теореме де Моргана, 6! Предположим, что (12.7) выполняется для случая и — 1 подмножеств Ао р= 1, 2,..., и — 1: Сагг!(А, ПАзй ... П А„,) =-Сагг! А — Сагг! А, — ... ... — Сагг! А„, + Сагг! (А, П А,) +... + Сагб (А„, П А„,) -(-... ... +( — 1)" 'Сагг!(А, П Аз П ... й А„,). (12.9) Рассмотрим следующие подмножества множества А„: А1 П Ан~ ° Ав-1 П Ан А1 П Ав П Аа~ ° ° Ан-з П Ав-~ П Ав, ~ АгПАзП ° ° .
ПАн 1ПАл Применяя (12.9) с А=А„, имеем Сагг! (А, П А, П ... П А„, П А„) = = Сагд А„— Сагг! (А, й А„) — ... — Сагд (А„, П А„) + + Сагб (А1 П Аз П А„) + ... + Сагс1 (А„з П А„~ П А„) + ... + ( — 1)" ' С агс) (А, П А, П ... П А„, П А,). (12.10) Подставляя (12.10) и (!2.9) в (12.8), получаем (12.7). Таким образом, с учетом (12.2) формула (12.7) доказана по индукции. Эту формулу называют формулой включения и исключения. Часто представляют ее в таком виде: Сагг1 (А| й ..
й Аг й А»+1 П Аг+г П ... й А„) = Сагб (А, П ... П Аг)— — Сагб(А1 й ... й А«ПА»+,) — ... — Сагб(А, П... й А»ПА„)+ + Сагб (Аг П ... й Аг П Аг+~ П Аг+г) + ° ° ° ... + Сагд(А1П ° ° ° ПА»ПА„1П А«)+ ° ... -1- ( — 1)" г Сагб (А~ й ... П Аг й А»+1 й Аг+г й ° ° ° П Ал) (12.11) Формулы (12.7) и (12.11) играют основную роль в перечислении подмножеств, обладающих заданными свойствами.
Посмотрим на эти формулы с другой точки зрения. Пусть элементы Аг с: А обладают свойством Уо ! = 1, 2,..., и. Тогда мы скажем, что подмножество Ай П Аг, П ... й Аг обладает свойством Уг, Л Уг, Л ... Л У~г. Таким образом, если элементы А могут обладать и различными свойствами, то число элементов А, обладающих й указанными свойствами и не обладающих п — й остальными, дается формулой (12.11), Общий метод «просеивания» нли «пропускания через решето». Решето Сильва — Сильвестра. Формула (12.11) описывает последовательный процесс пересчета, называемый решетом Сильва — Сильвестра. Рассмотрим предварительно пример. П р и м е р.
Рассмотрим множество А= (0,1,2,..., 10) (! 2.12) и следующие свойства: У,: А«и А — четное число, Уг; АенА и А)6, (12.13) У»: АеиА и 2(А(8. Подсчитаем число элементов А, обладающих свойством: У,Л не У«Л не Уг, т. е. У1 ЛУ«ЛУз Обозначим подмножества, соответствующие свойствам Уь Уг, Уг, через Аь Аг, Аг. Тогда Сагб (А, й А, П Аг) = Сагб (А,) — Сагб (А, П А,) — Сагб (А, П А,) + + Сагб(А, П А,й А,). (12.14) «Просеиваем» сначала А через У,: Сагд А, =6. Затем просеиваем А, через Уг и У,: Сагб(А,ПАг)=2, Сагд(А,ПА,)=2. Просеиваем А,ПА, через У,: Сагд(А,ПА,ПА,) О. Итак, Сагд (А, й А, П А,) = 6 — 2 — 2+ 0 = 2. (12.15) Формула (12.11) не позволяет, однако, перечислить элементы искомого множества. Находим его, выписывая последовательно: А,=(0~2,4~6,8,!О), А,ПАз=(0 2 4 6) А~ПАзПАз (О 2).
(12.16) Разумеется, для множества с небольшим числом элементов проще выписать искомое подмножество, однако это трудно сделать при большой мощности множества. Случай не выделенных множеств. Иногда подмножества не выделяются, а фиксируется только число свойств, которыми обладают их элементы. Положим в (г) = ~ Сагс1 (Ай П Аз, П ... П Аг ), (12.17) где суммирование производится по всем неупорядоченным г-выборкам [Аз,, А~, ..., Аз 1 и в(0) = Сагб А.
(12.18) Обозначим через (г'(й) число элементов А, удовлетворяющих в точности й свойствам, не уточняя, каким именно, или, что то же самое, не удовлетворяющих в точности п — й свойствам. В силу (12.11) имеем (Р(й) =в(й) — С,'+,и (й+!)+ Сз,+,в(й+2) — ... ... + ( — 1)" С"„зв (и). (12.19) П р и м е р.
Рассмотрим предыдущий пример (см. (12.13)): в(0) =Сагб А 11, в(1) =Сагб А, + Сагг( Аз+ Сагд Аз 6+ 4+ 5 15, в(2) Сагб(А,ПА,)+Сагб(А,ПА,)+Сагб(АзПА,) = 2 + 2 + 1 = 5, в (3) = С агб (А, П А, П Аз) = О, В'(0)~11 — 15+5 — 0=1, М7(1)=в(1) — Сзв(2)+Сзв(3) =15 — 2 5+3 0=5, В'(2)=в(2) — Сзв(3)= = 5 — 3 0 5. (12.21) Таким образом, одно число А ~ А не удовлетворяет никакому из указанных свойств: А = 1; пять чисел А удовлетворяют в точности одному свойству: А 0 (только У,), А=2 (только У,), А=З (только У,), А=5 (только У,), А=9 (только У,); 6З В частности, если Й=О, т.
е. никакое свойство не выполняется, то !Р'(0)= и(0) — в(1)+в(2) — ... +( — 1)" в(п). (12.20) пять чисел А удовлетворяют в точности двум свойствам: А=4 (только У, и У,), А =6 (только У, и Уз), А =7 (только У, и У,), А = 8 (только У, и У,), А = 10 (только У, и Ув); ни одно из чисел А не удовлетворяет в точности трем сволсгвам. Общая формула включения и исключения. Пусть А — конечное множество. Каждому элементу а, ен А припишем вес') Х(а,) ен К. Пусть ч) — множество из и свойств У„У,...
„У„, которым могут удовлетворзьть элементы А. Обозначим через Л(У, ж.... ж,) (12.22) сумму весов элементов А, удовлегворяю;цнх свойствам У;,, У,...,, У,; полагаем Л(УО, У~, ..., У~ )=О, если ни один из элементов А не удовлетворяет ни одному из указанных свойств, Пусть и (г) = Х Л (УО Уз... Уе ), (12.23) где суммирование производится по всем г-элементным подмножествам множества (Ао А„..., А„), а я (О) — сумма весов всех элементов А. Далее, пусгь П(й) — сумма весов элементов А, удовлетворяю:цих в точности й свойствам из зр: П(й) =я(й) — Сьмв(й+ 1) +Сь+зп(й+2) — ... ... + ( — 1)" С„п(а).
(12.24) Если вес каждого элемента из А равен 1, то Л(Уз,, Уз,,..., Ую ) = Сагб (АО П Аз, () ... Д Аз,), (12.25) и (г) = гп (г), (12.26) П (г) = Чг (г). (12.27) Формула (12.24) сводится к (12.19), Докажем (12.24), следуя Р а й з е р у (35]. Пусть элемент а, ен А с весом Х(ае) обладает в точности з свойствами из т)). При з < й Х(ьн) не входит в правую часть (12.24). При з = й вклад ае в правую часть (12.24) равен Х(аз), а при з ) й равен '1С~ — СььыС + +Сь+зС ~ — ... +( — 1)" С,С,'11(аз). (12,28) Легко видеть, что Сгс! =С',С',, я(1<э.
(12.29) Подставляя (12.29) в (12.28), получаем С" [С~~:ь — С~:л ' + С~:,т — ... + ( — 1)' ' С;-е1ое( ~) (12 30) ') Вообще говоря, л(о ) — злеиеит произвольного поля. или Сз(С, з — С,' з+ Сз з — ... + ( — 1)' С,':»~Л(ас) (12 31) Но в силу (8.8) выражение в скобках равно нулю, т. е. при э ) й вклад аз в правую часть (12.24) равен нулю. Таким образом, член справа в (12.24) есть сумма весов элементов нз А, удовлетворяющих в точности й свойствам иэ зр. При В = 0 П(0)=п(0) — зз(1)+п(2) — ... +( — 1)" п(п), (12.32) что обобщает (12.20). П р имер.
Пусть элементы множества А = (О, 1, 2, ..., 9) удовлетворяют следующим свойствам: У,: быть кратным 2; У»: быть кратным 3; У,: быть больше 3; Уз: быть меньше 7. Этим свойствам соответствуют подмножества: А~=(0 2 4 6 8) А»=(0 3 6 9)* Аз=(4 5 6 7 8 9) А4 — — (О, 1, 2, 3, 4, 5, 6). (12.33) Зададим веса Х(аз) элементов аз ен А таблицей: 3 4 7 8 х (сч) Для вычисления по формуле (12.24) требуются следующие величины: я (0) = 2 + 5 + 6 — 1 + 0 + 2 + 5 — 3 + 6 -(- 7 = 29; Л(У)=Л(А ) =Л(0, 2, 4, 6, 8) =2+6+0+5+6=19, Л(У») =Л (Аз) = Л(0, 3, 6, 9) =2 — 1+ 5+ 7=13, Л (Уз) = Л (Аз) = Л (4 5 6~ 7~ 8 9) = 0 + 2 + 5 — 3 + 6 + 7 = 17з Л (Уз) = Л (Аз) = Л (О, 1, 2, 3, 4, 5, 6) = 2+ 5+6 — 1+0+2+ 5=19; и (1) = Л (У~) + Л (У») + Л (Уз) + Л (Уз) = 19+ 13+ 17+ 19 68' Л (У, Л У») = Л ( А, () А,) = Л (О, 6) = 2 + 5 = 7, Л(У~ Л Уз) =Л (А~ () Аз) =Л (4 6 8) =О+ 5+6 = 11 Л(У~ Л Уз)=Л (Аз() А4)=Л(0,2,4,6)=2+6+0+5=13, 12 34 Л(У»Л Уз) =Л (А»ЙАз) =Л(6,9) =5+7=12, Л (У» Л У4) = Л (А» П А4) = Л (О, 3, 6) = 2 — 1 + 5 = 6, Л (Уз Л У4) = Л (Аз () Аз) = Л (4, 5, 6) = 0 + 2 + 5 = 7; зз(2) =Л(У~ Л Уз)+А(Уз Л Уз)+ Л(Уз Л У4) + Л(Уз Л У,)+ + Л (Уз Л У4) + Л (Уз Л У4) = 7 + 11 + 13 + 12 + 6 + 7 = 56; Л(У~ Л Уз Л Уз) =Л(А,() Аз() Аз) =Л (6) =5, Л (Уз Л Уз Л У4) = Л (А, () Аз () А4) = Л (О, 6) = 2 + 5 = 7, Л (У Л Уз Л У4) = Л (А~ () Аз Д А4) = А (4 6) = 0 + 5 = 5 Л (Уз Л Уз Л У4) = Л (Аз () Аз () А4) = Л (6) = 5; зз(З) — А(У~ ЛУзЛУз)+А(Уз ЛУзЛУ4)+А(Уз ЛУзЛУз) + + Л(Уз Л Уз Л У4) =5+ 7+ 5+ 5=22; А (У1 Л Уз Л Уз Л У4) = Л ( А~ () Аз () Аз () Аз) = Л (6) = 5; зз (4) = Л (Уз Л Уз Л Уз Л Уз) = 5.
Сумма весов элементов, не удовлетворяющих нн одному из свойств, равна П (0) = н (0) — С~~зз (1) + Сзл (2) — Сзп (3) + Сззз (4) = = н (0) — зз (1) + зз (2) — зз (3) + я (4) = 29 — 68 + 56 — 22 + 5 = О. Отсюда еще не следует, что не существует элемента, не удовлетворяющего ни одному иэ указанных свойств, хотя в этом примере такого элемента нет. Сумма весов элементов, удовлетворяющих одному и только одному свойству, равна П (1) = л (1) — Сззз (2) + Сззз(3) — Сззз(4) = =зз(1) — 2п(2)+Зи(3) — 4зз(4)=68 — 2 56+3 22 — 4 5=2, Такими элементами являются: 1 (только У4): Х (1) = 5, 7 (только У,): Х(7) = — 3. Сумма их весов Х (1) + Х (7) = 5 — 3 = 2. Сумма весов элементов, удовлетворяющих в точности двум свойствам, равна П(2) = зз (2) — Сзи (3) + Сззз (4) = зз(2) — Зл(3)+ +6я(4)=56 — 3 22+6 5=20. Такими элементами являются: 2 (только У, Л У,): Х(2) =6, 3 (только Уз Л У4): Х(3) = — 1, 5 (только Уз Л У4): Х (5) = 2, 8 (только У, Л У,): Х(8) =6, 9 (только У, Л Уз): Х(9) =7.
Сумма их весов Х (2) + Х (3) + Х (5) + Л (8) + Л (9) = 6 — 1 + 2 + 6 + 7 = 20, 66 Сумма весов элементов, удовлетворяющих в точности трем свойствам, равна П (3) = л (3) — С4п (4) = я (3) — 4п (4) = 22 — 4 ° 5 = 2. Такими элементами являются: 0 (только У! Л Уэ Л У4)! Х (0) = 2, 4 (только У! Л Уз Л У!)! 1. (4) = О. Сумма их весов Х (0) + Х (4) = 2 + 0 = 2.
Сумма весов элементов, удовлетворяющих в точности четырем свойствам, равна !! в(2) = ~~ Сагд(А! () А!), 1, !=1 (12.36) а!(и) = Сагг((А, () АэД ... ДА„); з (О) ч!(О) и (!) 3! = (12.37) а! (а) 3 й= Яз — — — ) (Ж'(О) берется из (!2.20)). (12.38) 67 П (4) = я (4) = 5. Таким элементом является 6(У! Л Уг Л Уз Л Ух): Х(6) = 5.
Итак, множество А разбивается на подмножества, обладающие ни одним из свойств: 0 в точности одним свойством: (1,7) в точности двумя свойствами: (2,3,5,8,9) в точности тремя свойствами: (О, 4) в точности четырьмя свойствами: (6). Символическая запись формулы включения и исключения. Р и орда н (36) связал с принципом включения и исключения некоторые символические операции. Чтобы изложить это, нам потребуются результаты $ 10 (см. (10.62) — (10.88) ). Пусть подмножества А„А„..., А„, А, ~ А, ! = 1, 2, ..., и, обладают свойствами Уь У,, ...,,У„соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
