С.В. Яблонский - Введение в дискретную математику (1060464), страница 29
Текст из файла (страница 29)
(22) «У Эта формула верна н нрн а ° $, что вытекает на краевых услозвй (ем. с, 184). Возьмем произвольное разбиение Е на Й яепустых подмножеств и выбросим одну из компонент (что возможно Й способами). Оставшаяся часть множества Е имеет мощность с (Й вЂ” 1 < У < и — 1) и разбнта на Й вЂ” 1 частей. Таким образом, разбиению Е на Й непустых подмножеств соответствует Й разбиений множеств мощности, меньшей или равной и — 1, на Й вЂ” 1 часть. С другой стороны, если взять произвольное собственное подмножество в Е и выбрать в нем любое раабиение на Й вЂ” 1 не- пустую часть, то оно может быть однозначно продолхсено до разбиения множества Е на Й непустых частей.
Отсюда «) ч. и. комвпнлтовпый Анллпэ 187 Заметим, что произвольное разбиение Е на Й непустых частей получается: а) либо из разбиения множества Е~а„ на й — ( не- пустую часть добавлением подмножества (а„); б) либо из разбиения множества Е~а„ на й непустык частей путем добавления к одной из них элемента а„ (й способов). Отсюда получаем тождество Ф(п, й)=Ф(п — (, й — 1)+ЕФ(п — (, й). (23) Оно позволяет построить таблицу для чисел Ф(п, к) (с линейной сложностью) и чисел Белла. Таблица 3 Опираясь на рекуррентные соотношения для чисел Ф(п, й), докажем следующий факт. Теорема 4. Последовательность (Ф(я, й)) при и!ипеированном и и Й=О, $, ..., и унимодальна; ерществует ч. и.
комвпнатОР11ый АПАлпз !88 такое я„, что Ф(п, О)( Ф(п, 1)( Ф(л, 2) <...( Ф(п, 1с„)Р~ > Ф(п, й„+ 1)»... Ф(и, п), и к„к„, или и„= к„, + 1. Доказательство. Ведем индукцией по п. При л = 2 утверждение очевидно (см. табл. 3). Индуктивный переход от п — 1 к п. а) Пусть 2 ~ А ~ 1с„ь Используя (23), имеем Ф(п, й) — Ф(и, й — 1) = (Ф(п — 1, й — 1)-Ф(п — 1, сс.-2))+ +й(Ф(я — 1, й)-Ф(п — 1, й — 1))+Ф(п — 1, А — 1)>0. б) Пусть Й„, + 2 ~ й ~ л.
Используя (2'!) и учитывая, что к, < )с.-, при с ~ л — 1, пмеем а-с с Ф(п,й) — Ф(л,1с — 1) = ~ ~" ) Х о=з Х (Ф (с, Ус — 1) — Ф (г', й — 2)) ( О. Сравним теперь велпчины Ф(п, 1'„,) и Ф(п, й„, + 1). Если Ф(л, 1'„-,) Ф(л, )с„, + 1), то полагаем )с„ )с„ь Если Ф(п, й„,)(Ф(л, 1'„,+1), то полагаем й. -1„,+ 1. Утвержденпе доказано. Уже первое знакомство с комбинаторными объектами показывает, что мы сталкиваемся с общими задачами: такими, как задача о построении комбинаторных объектов и чисел (задача о перечислении), как задача о построении комбинаторных тождеств, как задача об изучении свойств комбпнаторпых чисел (например, наличие унимодальности) и т.
п. в 3. Методы научения комбпнаторных объектов и чисел В комбинаторном анализе существует целый ряд подходов для изучения комбннаторных объектов и чисел. Теоретико-множественный подход. Он связан с вычислениями мощностей конечных подмпоясестз, ч.п, комвппхтогпын хпхлпз 189 Пусть А „..., А — система подмножеств конечного множества А. Обозначим через Н, (! О, ..., и) совокупность всех элементов из А, которые содержатся ровно в (множествах системы, и через С, (3 О, 1, ..., л)- совокупность всех элементов из А, которые принадлежат ие менее чем 1 множествам спстемы.
Очевидно, что А -Н»ОНА 0 ..0 И» и Н "Н~м" ° ° ° "Н ° Возникает вопрос, как найти !А, (!... 0 А„), а также как находить !А~(А,0...0А„)!, !Н,! и !6,! (! О, 1, ..., л). Для решения этого вопроса необходима дополнительная внформация, т. е. надо заранее знать мощности некоторых подмножеств. Например, если известны мощности множеств А' й А," й ... й А'„", где А ; прп а;=1, А~' А",А; прн о~ О, то (по аналогии с совершенной д. н. ф.) )А0 ° () А 1- Х )А'й" йА,"! (еь '»») (аг...,а„) ~ю,... л> Оказывается, что решение поставленных вопросов воз- можно также, если известны мощности множеств А~,й" йА,, для любых подмножеств чисел ((о..., Я (1 1, 3,...,я).
Теорема 5 (принцип включения-исключения), !А~(А,() ... () А„))=!А! — ~э !А,)+ г=т + Х 1А, й Аз~-" +( — 1)' Х ~А,й ьс[ <~„с» зс~,<...<цс» й А~з й " й Азу~+ ". +( — 1)"!Аг й Аз й " й А»!. Доказательство. Пусть аж А и а входит ровно в )г множеств ()с 1, ..., л). Тогда а ФА~(А, !)... ОА„).
1ЗО ч. 11. комсинАТОРный Анализ С другой стороны, элемент а учитывается в слагаемом»А! 1 раз, Ъ Х! А»! ( )раз, ~А;, П А»,~ (з) раз, Таким образом, его вклад в правую часть равен (,') — (',)+ ... +( — ц'(„")=о. Если элемент а не входит в (А, 0 ... 0 А.), то он учитывается один раз в левой и в правой частях равенства. Теорема докааана. РассмотРим пь1»вменение этой теоРемы. Пусть А Р, — множество всех булевых функций, зависящих от переменных х„..., л„; А» — множество всех булевых функций из А, которые существенно ве зависят от хь Очевидно, ! А», П ...
П А»»! 2' Подсчитаем число Я„функций из А, существенно зави- сящих от всех переменных х„..., л.. Мы имеем ф„!А~(А, О... Ц А„)! и в силу теоремы 5 .- "-(",)2"-'+(",) -"-*-...+( ).(") . Решение остальных вопросов, а также сам принцип включения-исключения могут быть получены из теоремы обращения, которая приводится ниже.
Алгебраический подход. Он основав ва использовании вспомогательных просто получаемых комбинаторных тождеств для нахождения интересующих нас комбиваторных чисел. Пусть имеются два семейства комбинаторных чисел (а„,,1 и (Ь.,„1, где п=О, 1, ...; »» =О, 1, ..., и. «02 ч. и. комв««НАТОРнып лналнз Формулы обращения имеют вид а„,ь 2', („1Ь„,«, Ь»,ь ~ ( — 1)« "(')а»л (26) Здесь п явно входит в пределы суммирования. ~» — й « — ь ~» — й 3. Пусть Л и»«- (, „),р»лл-( — 1) (.
„,) при «>Й и Л,ь< р,»,~ О при «<Й. Используя (13), име- ем при Ййпгг<п Х ...Л.л..-Х( — 1)' "(",,')(„",')- -А- — (:-)(: — )-(.".:::.;, Соответствующие формулы обращения имеют вид » » Применения формул обращения. 1. Подсчет числа Р.— булевых функций, зависящих существенно от дан- ных п переменпых. Очевидно, ( „) Р» + (» — «) Р~-«+ ° ° ° + ( о ) Ро Применяя формулу обращения (25), получаем Р.-("„)2'"-(„",)2'" '+ ...
+(-1)" ~о")2'-". (28) 2. Получение явной формулы для чисел Стнрлинга 2-го рода Ф(п, й). Формула (18) имеет внд Ь"-(,")Ф(,Ь)««+ +(„,) Ф(п, й — 1) (й — 1)! +... +(~~)Ф(п, О)О) Используя формулу обращения (25), получаем Ф(п.)"-(.) л-(. «)(Ь-1) + "+(-1)'(о) О или (ь)"'" ( «)«" "+" +' «)" (о~'о" Ф(п,й)— ч. и. комвинАТОРныи АнАлиэ Последнее выра!кение может быть преобразовано к виду Аи (Ус — 1)" (7с — 2! и Г! П (А — 1)! 22! !(А — 2) А-г 1" "+(-1) (А 1)!1Г Из выражений для Ф(п, )г) мол<но получить явпое выражение для чисел Велла Ф(п); и и и Ф (л) )' Ф (иа)г) —,)~,~'„( — 1)' —,, ()о — 1)" Ао Ао!о и и )' ( — 1)' А=О Рею Пусть ) Й вЂ” 1 и будем суммировать по параметрам 1 и 1 0 и Рас.
4 ()г (+)). Пределы суммирования легко усматриваются из рис. 4: и и — ! тт и-1 т и ! 1 Ф( ) - ~~,У', ( — 1)' — „,, -,')„' — '., Х ( — 1)'му=от о у=о 1 о 1 и-1 ... +(1--+--... +(-1) — — ) 1! 2! (и — 1)!у или Ф(п)= — + (1 — — + — (, +, ии ( 1 1 ((и — 2)" и! '( 1! 2! ) (и — 2)! (адесь коэффициент прн у"/)! — кусок ряда е ').
т Овеаеиие в аискретиуке математику Ч. ». КОЫБИНАТОРНЫА АНАЛИЗ 3. Вывод формулы включения-нсключеиия и ее обобщений иэ формул обращения. Обозначим !А! л Х)А1)-в1 ° ° Х )А11П 1 И1,<...<11Са П ° ° ° П А1А~ лз ° °, л.= !А1О...ОА.! и !н1! ь1 (1 О,...,в). Напомним, что э э )А! Х )Н1! Х Ь, и каждый элемент ажН< входит в («) множеств вида А1, П ... П А11 ($ < 11 (... ( !1 < я) .
поэтому уз=! 4! "(о)Ье+(о)Ь1+" +(о)" е1 Х)А1)=( )Ь,+ ... +( )Ь, йз ч~~ ~!А1, П ... П А1„!-( )Ь» . +(")Ь„, а -!А П "П А )-(„)Ь. Формулы обращения (2б) да1от и при Ь О имеем формулу включения-исключения: Ь,-.Х (-1)'ло 1 О 4. Подсчет числа неизбыточных (тупиковых) покрытий множества А — (а„..., а ) его подмножествами А„..., А11 А А1О...ОАЫ Покрытие навывается неизбыгочным (тупиковым), если при выбрасывании любого из его подмножеств А, система подмножеств А„..., А, „А<+„..., А. Ие образует покрытия А, т. е. А ч.
и. ИомвпнАТОРиый Анализ С ее помощью имеем систему равенств ( +1) -:+(;):-'+(",). -'+" +(„",).+(„) ((п — 1)+1) =(и — 1) +( )(и — 1) +( )(и 1) +... ° '( ) — () (2+ 1) 2 +( )2"' '+('")2" '+...+( ~ )2+( ),. (1+ 1)" 1-+(",)1" '+(,")1"-'+... +( "„)1~(„).
Складывая их почленно, получаем рекуррентную формулу (п + 1) 1 + ( ) Я~, (п) + ( ) Я„, (и) + . ° ° .. + („,) Я,(.) + (:) Я. ( ), и (и+ 1) где Я,(п) п, Я1(и) = Отсюда можно постепенно найти Я (и). Например, ( + 1)'=1+ (') Я ( ) + (') Я ( ) +(')Я (.) ЗЯ (п) (п + 1)' — 1 — 3 и " + — и = " (и или и (и + 1) 12и + 1) Я, (и) 6 Метод производящих функций. Он используется для перечисления комбинаторных чисел и установления комбипаторных тождеств. Исходным пунктом являются последовательность (а,) комбннаторных чисел и последовательность функций бр<(л)) (1=0, 1, ...). Рассматриваем далее ряд ч. и, комвинАтогный АнАлиз который, в случае, когда последовательность (а,) конечна, т.
е. 0<1~ и, будет многочленом. При определенных ограничениях данный ряд будет сходящимся и тогда он в некоторой области будет задавать функцию Р(х): 60 Р ( ) - Х о, р (х). Эта функция называется ироизводящей Яункцией. Рассмотрим ряд примеров, относящихся к типичным случаям. 1. о~ - (, ) (1 - О, 1, ..., и), ~р,(х) - х'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
