Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
А -=//„и Я» и ...и Нп
и
с,-//,ил<+1и ...ия*.
Возникает вопрос, как панти \А, и... II Ап\, а также как находить И\(Л, и ... и Ап) 1, |Я<| и IС, 1 {? = 0, 1, ..л). Для решения этого вопроса необходима дополнительная информация, т. е. надо заранее звать мощности некоторых подмножеств.
Например, если известны мощности множеств
41 п 42п ...
где
^ [ А1 при а* = 1*
1 1 при — 04
то (по аналогии с совершенной д. п. ф.)
Iи ... {] а„\= 2 14* п ... п 4П|.
(°х..с»)
Оказывается, что решение поставленных вопросов возможно также, если известны мощности множеств
П ... П Лч
ДЛЯ любых подмножеств чисел ..., и) (I = 1, 2,..п). Теорема 5 (принцип включения-исключения),
|Л\(Ли ... и Ап)\=\А\~ 2 [Л,| +
1=1
+ 2 И,, П ^Л-... +(-1)‘ 2 \\п
П П ... П Агг | + .. - + (— 1)”| АУ П А2 П . . . П Аг|.
Доказательство. Пусть де4 и а входит ровно в к множеств (&—1, п). Тогда ... и Аа\.
-(00 ч. И. КОМБТТНЛТОГНЫЙ АНАЛИЗ
С другой стороны, элемент а учитывается в слагаемом М1 1 раз,
> 2И|| (1) раз>
> 2 \А<гГ\ Ак\ (М раз,
Таким образом, его вклад в правую часть равен
Если элемент а не входит в {Л1 и ... и А*), то он учитывается один раз в левой и в правой частях равенства. Теорема доказана.
Рассмотрим применение этой теоремы.
Пусть А = Рд — множество всех булевых функций, зависящих от переменных х1л ..., х„; Ai—множество всех булевых функций из А, которые существенно не зависят от я,. Очевидпо,
|^П ... П Аи\ = 2а”‘г.
Подсчитаем число рп функций из А, существенно зависящих ОТ всех переменных #!, ..., х„. Мы имеем
р„=и\(Л1и...иН.)|
в в силу теоремы 5
- 2‘" - ( ; ) 2*"-‘ + (\) 22"~г _...+(_!)•(;) 2.
Решение остальных вопросов, а также сам принцип включения-исключения могут быть получены из теоремы обращения, которая приводится ниже.
Алгебраический подход. Он основан на использовании вспомогательных просто получаемых комбинаторных тождеств для нахождения интересующих нас комбинаторных чисел.
Пусть имеются два семейства комбинаторных чисел {ап,ь} и {ЬП'к}, где п = 0, 1, ...; к = 0, 1, ..., п.
Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ 191
Теорема 6 (теорема обращения). Если для любых п и к<п
П
ап,к = 2 {=0
и при к < П, Г < П
21 ( 1 при г = кг
= {о щигФК (24>
то при к ^ п
ьп,к =* 2
і^о
Доказательство. Используя (24), имеем
п п п
2 Ртг.М^/і.і ™ 2 Р?г,Ь,і 2 ^иЛ,г^п,г =? і~0 і=0 г=О
п/п \
2 [ 2 М'пДЛ^'пД,?' 1 кп,т — &п,Ь" »•=0 \ і—О /
Примеры. 1. Пусть Лп.й,! = (— 1)* *(*)?
Тогда в силу (12) при к ^ я, г ^ я.
- ?<- ?>*-(:)(:) -»-их
Формулы обращения здесь имеют вид
«».*- 2 (Я6»." *ч»-2(-1)*_1(?)<ч., (25;
1=0 V 1 * 1=0 \ 1 /
число п является параметром.
2. ПустьК.ъл ет ( & )»1Чм = (— 1)*-ь ( I )• Тогда, используя (12), имеем при к^п, г < п
2|1“.,л.л.-2(~ч>,"‘и) (О"
192 ч- И. КОМБИНАТОРНЫЙ АНАЛИЗ
Формулы обраще ния имеют вид
при
одесь п явно входит в пределы суммирования.
3. Пусть К,ь.,-= (*!*), (Чм - (-1Г * ("Г»)
к и А„, *. ^*= Цп. л. * — 0 при ? < к. Используя (13), имеем при к < п, г ^ п
-?(-1г ')-
_ V Г_ и'-» (п- «V» - _ / 1 при г “ *'
йл и — г) \п — 1} [о при г ф к.
Соответствующие формулы обратцепия имеют вид
в.*-2 (?!*)*>..Ь Ь,а- 2 (-^‘(."гЛ(27)
i=f>Ль л '
Применения формул обращения. 1. Подсчет числа рп — булевых функций, зависящих существенно от данных п переменных. Очевидно,
2 = ( п ) рп + (п __ Рп—1 + ... + ^ п = 1,2,.,,
Применяя формулу обращения (25), получаем
«’‘(о)2- <28)
2. Получепие явной формулы для чисел Стирлинга 2-го рода Ф(н, А). Формула (18) имеет вид
Г = (*)ф(п,А-)*1 +
+Ц,)ф(«А-1)№-1)! +... +(*)ф(п,0)01
Используя формулу обращения (25), получаем
ф (». к) а - (*) г - (кЦ,) (к -1)” +... +{_!)'(\) .о-
или
Ф (паА) =
к\
Ч. И. КОМБИНАТОРНЫЙ АНАЛИЗ 193
Последнее выражение может быть преобразовано к виду ™ кП ? (*-2)"
11 (& — 1)1 21 (А— 2)!
? * ? + (* _ 1)1 и- (29)
Из выражений для Ф(ге, /г) можно получить явное выражение для чисел Белла Ф(п):
п п Ь ( ^ ^
ф («)=2 фк*)= 2 2 (- - *г -
к~0 й=0 i=0
л А
22<-1>‘^
..(к — ?)Г
Л—0 1=0
Пусть / = к — ? и будем суммировать по параметрам 1 и /
(& = ? + ;). Пределы суммирования легко усматриваются из рис. 4:
Т1 п—^ п п п—1
фм = 22(-е^«2^2(-1)‘^ 2~ 0 1=0
з=о^ І==t>
4. (?] 1 У" -+ (\ _ 1 + М(ге~2)П 1
л! + Г 1! Дл — 1)! \ 11 + 21/ (л —2)! + * ’*
... + (1 - -... + 1)"-1 (я4тя)
я
/ ч . Л 1 . 1 \ (л-2)я ,
(п)_М + 11_ТГ + 2г)^-2)Г + •••
... + (1 - А +1 _ 1 + ... + 1)п-1 -1 1): ) (30)
(здесь коэффициент при }п/][ — кусок ряда «-1)>
13 С. В. ЯОлонскиЙ
или
ф
194 Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ
3. Вывод формулы включения-исключения и ее обобщений из формул обращения.
Обозначим UI « ?0, S Mi 1 “ ?и • • ? • 2 I At fl
п * * ? П ^ifc| = gkt •. gn = Ul n ... n Aj и Ifffl = hi
(i = 0, .n).
Напомним, что
i=o 1=0
и каждый элемент а «s II t входит в ( * ) множеств вида лн п ? • • П Aik (1< ii < ... с [\ ^ и). Поэтому
?о = М I = ( о ) й-о + ( о ) ? + ( (I ) ^«1
" 2 Мг I= (I) + * * • + (1)
gn = \Al П ... П 4>|-(*)*»?
Формулы обращения (26) дают
Afi = |(-ir*(-)gi
и при к — 0 имеем формулу включения-исключения:
А0 ” 2 (— l)1 gi'
