1.3   Принцип включения и исключения

Пусть М = {ті,..., тп} - некоторое множество, элементы которого мо­гут удовлетворять одному из следующих свойств: рі,...,Рк- Обозначим через Аі множество тех элементов М, которые удовлетворяют свойству Рі. Обозначим также через -1/,= Л/, Г) Л/, П • • • П Л/(..

Утверждение. Число элементов М, не удовлетворяющих ни одному из свойств равно

к

М(0) = гг - ^ |Л£| + ^2 \Ы - I] + • • • + (-1)*1^12...*|-

г=1 г<і і<і<к

ДОКАЗАТЕЛЬСТВО следует из равенства

к

\А1и---иАк\ = ^2 Ш - ^2     П Л^ + " ' + (-1)^1Иі П • • • П Лй|,

г=1 г<^'

которое, в свою очередь, доказывается индукцией по числу к. Если к = 2, то | Л і и Л2| = | Л11 + | Л->| — |Л| П Л2|. Предположим, что наше равенство истинно для к множеств. Докажем его для (к + 1) множеств. Имеем \AtU- ■ -иАкиАк+1\ = |Ліи• • -и Ак\ + \Ак+1\ - |(Ліи• • -иАк)П Ак+1\ =

= Е Ш-  Е Е И^|---- + (-і)^1Иі2...^|+

!</</-• 1<і<І<к 1<і<і<к

+ \Ак+1\- \(Аі П Ак+і) и • • • и (Ак П Лй+1)| =

=  ^  |Л/| —     ^     |Л/;-| + • • • + (— 1)ЛI - ^ і_11- Утверждение доказано.

/</.— і 1 </<:./'</,—1

Обозначим через М(г) число элементов М, удовлетворяющих точно г свойствам. Фиксируем свойства р\,... ,рг(г < к) и обозначим через

А = Л12...... Вг+і = Л Г) Лг+і,....     = Л П Л/,.

Число элементов М, удовлетворяющих точно свойствам р\,...,рг, равно А(0) = \А12...Г\-    £   \Вг\+   £ \BiHBj\-...

+(-1)»-г|д.+1 п • • • п вЛ| = |А12...Г| -  Е  И12...п| + (-1)"-г|А12...Л|.

г— !</</>•

Следовательно,

М(г) =     ^2     \Aiii2-irl ~ Е      Иг1г2...гг+11 +

г1< — <гг $1<---<$г+1

+ Ог+2      Е      |^-г1...гг+2 I — • • • + ( —1)^СГ+^      ^      | А^_^г+. | + . . . . г1<—<гг+2 11<---<г+^

Эта формула обобщает утверждение 1 (г = 0) и называется формулой (принципом) включения и исключения.

Применим доказанный принцип к решению задачи о встречах. Под­считаем число тех перестановок а\,...,ап чисел 1,2,... ,п, для которых щ ф г, г < га. Обозначим через А^..дг множество тех перестановок, для ко­торых а-,. = 1^,2 < г. Тогда (Л;,...^.) = (га — г)! Из утверждения 1 следует, что искомое число равно

п\-(п- 1)!га + (га - 2)\С2п - (га - 3)!С3 + • • • + (-1)»$ =

- п! _ п!   ,  . . .  ,  (_1)пп\ _    Ц! _ 1 + . . . +

— 2!      ЗМ        ^ V    -1/  те! ~~ 'И2!      ЗМ        ^    те!   / •

Пример. На одной из кафедр университета работают тринадцать чело­век, причем каждый из них знает хотя бы один иностранный язык. Девять человек знают английский, восемь - немецкий, пять - французский. Пяте­ро знают английский и немецкий, трое - английский и французский и двое немецкий и французский. Можем ли мы ответить на следующие вопросы:

1) Сколько человек знают все три языка?

2) Сколько человек знают ровно два языка?

3) Сколько человек знают только английский?

Обозначим через К множество сотрудников кафедры, через Кх - мно­жество сотрудников, знающих язык х. Тогда

13 = \Ка\ + \КН\ + \Кф\ — | -К"а,н | ~~ |-^а,ф| ~~ |-^н,ф| + |-Ка,н,ф| =

= 9 + 8 + 5 — 5 — 3 — 2+ |/\';ии.ф| = 12 + |/\';ии.ф|. Следовательно, только один человек знает все три языка.

Подсчитаем число людей, знающих только английский язык. Имеем, \Ка\ - \К^Н\ - |^а)ф| + |^а,н,ф| = 9- 5- 3 + 1 = 2. И, наконец, число сотрудников, знающих ровно 2 языка, равно сумме следующих чисел

К   1 —

| -^а,н,ф

-^а,ф|

| -^а,н,ф

-^н,ф|

| -^а,н,ф

+1=7.

 

ЗАДАЧИ

1). Доказать, что число целых чисел в сегменте [1, п] взаимно простых с п равно <р(п) = п • Д(1 — ^).

р\п

УКАЗАНИЕ. Число т не является взаимно простым с п = 1 ...р®* тогда и только тогда, когда существует простой делитель р;\п такой, что Рі\т. Пусть Л; = {т Є [1, п]:р;\т}. Тогда (р(п) - число элементов в разности

[1,п]\(А1иА2и---иА8),

т.е. (р(п) = п-'£\Аі\ + 1£\АіпАу\- £ \АпАуПАк\ + --- +

і=1 г<] і<і<к

-іу\А\ П • • • П А8\. Так как р,і ф р^ при і ф і, то А^П ■ ■ ■ П Л,-,

{т Є [1, //]; (/>,-, .. .рі()\т}. Заметим, наконец, что число элементов в [1, п

Е п

%<■}

Е ■ п

і<І<к

-сії

делящихся на (І((І < п) равно [|]. Поэтому (р(п) = п —

Еп__ Рі

РіР2-Рв

2). Сколько из п\ членов определителя

/ 0   о12 ... .

і=1

_ х

Р2

\

а21 О

\ О-п!

Рврано нулю?

ОТВЕТ: (п - 1)!п - С2п(п - 2)! + СЦп - 3)!----= гг!-| + ||-|| + -- - =

3) . Пусть дано гг объектов (гг > 1) и пусть свойством а обладают все, кроме первого, свойством (3 - все, кроме второго,..., свойством Л - все, кроме последнего. Определить число объектов, не обладающих ни одним из этих свойств.

ОТВЕТ: п(1 -(п-1)+ ("-Ц*"-2* ...) = п(1 - I)""1 = 0.

4) . Найти число целых положительных чисел, не превосходящих 1000 и не делящихся ни на одно из чисел 3, 5 и 7.

УКАЗАНИЕ. Искомое число равно 1000 - [™] - [™] - [™] + [^0і

-10001  і  Г10001      Г ЮООі

I г шит I ГШ] _ г

5) . При обследовании читательских вкусов студентов оказалось, что 6и/о студентов читает газету "Правда", 50% - газету "Алтайская Правда", 50% - газету "Комсомольская Правда", 30% - газеты "Правда" и "Алтайская Правда", 20% - газеты "Алтайская Правда" и "Комсомольская Правда", 40% - газеты "Правда" и "Комсомольская Правда", 10% - все газеты. Сколько процентов студентов

1) не читает ни одной из газет;

2) читает точно две газеты;

3) читает не менее двух газет?

6) . (Задача мажордома). К обеду за круглым столом приглашены п пар враждующих рыцарей (п > 2). Доказать, что существует ровно

к=0

способов рассаживания их так, чтобы никакие два врага не сидели рядом.