Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1999/06/11.pdf Дата изменения: Fri Dec 23 19:25:32 2005 Дата индексирования: Tue Oct 2 00:09:37 2012 Кодировка: Windows-1251 Поисковые слова: ngc 6781

ЧТО

ТАКОЕ

КОМБИНАТОРИКА

11
учеников всевозможными комбинациями видов спорта, почему-то не знают, сколько же учеников занимается спортом, и обращаются за помощью к нам т.е. к формуле включений и исключений. Намного более интересное приложение будет рассмотрено в следующем разделе. Мы увлеклись обсуждением формулы (18) и едва не забыли про доказательство. С применением индукции оно оказывается довольно простым. Пусть формула уже доказана для m = 2 и m = m 1. Полагая A1 UK U Am-1 = В, находим

динения и пересечения например, независимость их от порядка A1 , ..., Am , а также свойства типа
A B U C U K U D = AB U AC U K U AD.

>

AA = A ,

Отсюда и название формулы. В общем случае она выглядит довольно устрашающе, и мы прелагаем ее лишь для читателей не робкого десятка:

C

A1 U A2 U K U Am = =
+

(Принимается, что пересечение связывает сильнее, чем объединение, т.е., например, = AB U AC = AB U AC .) Теперь мы можем так записать принцип сложения: если множества A1 , Am попарно не пересекаются (т.е. | Ai A j | = 0 при всех i j , 1 i , j m ), то


i

Ai -


i< j

Ai Aj +
m+1

> C> C

i < j


Ai Aj Ak - K + -1

>C

A1 A2 K Am

(18)

A1 U A2 U K U Am =


i =1

m

Ai . (16)

Конечно, этот факт очевиден, как его ни записывай. Но попарно пересекающиеся множества это очень частный (и очень простой) случай. Можно ли получить аналог формулы (16) для общего случая? Да, и в нескольких формах. Нас будет особо интересовать одна из них (не использующая дополнений к A1 , ..., Am ).

Слабонервных просят не читать (формула включений и исключений)
Случай m = 2, впрочем, рекомендуется всем, даже слабонервным. Действительно, при m = 2 формула, о которой идет речь, имеет вполне симпатичный вид
A1 U A2 = A1 + A2 - A1 - A2 . (17)

Ее и доказывать-то не надо, достаточно взглянуть на рисунок:

)

)

A1 U A2 количество точек (элементов) во всей заштрихованной области. Складывая A1 и A2 , мы дважды засчитываем точки из области с двойной штриховкой, т.е. из A1 A2 . Поэтому вычитание A1 A2 все ставит на свои места. Итак, элементы A1 A2 сначала 'включаются' в сумму избыточным образом, затем это исправляется соответствующим 'исключением'.
3

(все индексы суммирования меняются между 1 и m). При m = 2 получается, конечно, (17), где в правой части всего 3 слагаемых. Сколько же вообще слагаемых (того или иного знака) в 'сумме сумм', стоящей в правой части? Столько же, сколько непустых подмножеств у m-множества, m т.е. 2 1. Если, скажем, m = 30, то слагаемых уже больше миллиарда. А ведь чтобы найти каждое слагаемое, надо определить число элементов, общих для какого-то набора из множеств A1 , , Am . Неужели столь громоздкая уродливая формула может быть полезной? Вопрос, понятно, риторический. Для чего же еще мы стали бы ее приводить ради красоты, что ли? В задачниках часто можно найти примеры применения формулы (18) наподобие следующего. Задача 14. Ученики некоторого класса занимаются только тремя видами спорта бегом, плаванием и теннисом. Бегом всего занимается 10 человек, плаванием 13, теннисом 11, бегом и плаванием 4, бегом и теннисом 5, плаванием и теннисом 6, бегом, плаванием и теннисом 2. Сколько учеников данного класса занимается спортом? Для решения применим формулу (18). Если множество учеников, занимающихся бегом, обозначить через A1 , плаванием через A2 и теннисом через A3 , то искомая величина есть

A1 UK U Am = B U Am =
= B + Am - BAm = = B + Am - A1 Am UK U Am -1 Am = =


i< m

Ai + Am -




i < j


Ai Aj -

Ai Am + K = Ai -

i< m

= ...


i


i< j

Ai Aj + K

Полезная все-таки вещь индукция!

Число перестановок, имеющих неподвижные элементы
Рассмотрим 3! = 6 возможных перестановок чисел 1, 2, 3: 123, 132, 213, 231, 312, 321. В первой из них все три числа стоят на своих местах ('неподвижны'). Во второй есть один такой элемент (1); также по одному неподвижному элементу имеют третья (3) и шестая (2). В четвертой и пятой перестановках неподвижных элементов нет. Рассмотрим вопрос: сколько из m! перестановок чисел 1, 2, , m имеют неподвижные элементы? Для m = 3 ответ, как мы видели, 4 (для m = 2 такая перестановка, очевидно, одна). Вручную нетрудно решить задачу перебором для случая m = 4; при m = 5 возникает мысль о применении компьютера. В самом деле, даже при m порядка 10 12 (когда перебор вручную нереален) компьютерный перебор не занимает много времени. Но уже при m = 20 перебор 20! перестановок недоступен для компьютеров. Надо, стало быть, искать какие-то более действенные средства подсчета. Други-

A1 U A2 U A3 = A1 + A2 + A3 -
A1 A2 - A1 A3 - A2 A3 + A1 A2 A3 = = 10 + 13 + 11 - 4 - 5 - 6 + 2 = 21 . Все правильно, но в полезности формулы (18) подобные примеры не очень убеждают. Как-то трудно поверить, что лица, обладающие столь детальной информацией о занятости

*