Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
1=0
4. Подсчет числа неизбыточных (тупиковых) покрытий множества А — (аь ..., а„} его подмножествами ^4i( • >.) Ah.
А =Л1и...иЛл.
Покрытие называется неизбыточным (тупиковым), если при выбрасывании любого из его подмножеств А{ система подмножеств Aif ..., Ai-U Ai+U ..., Ап не образует покрытия Л, т. е.
A+AlV'ttUAl-iVAHi\),t.UA„
Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ
195
Очевидно, что в тупиковом покрытии все подмножества попарно различны.
В дальнейшем мы будем рассматривать более широкий объект: упорядоченные покрытия (т. е. подмножества занумерованы и допускается повтореиие подмножеств).
Каждому такому покрытию соответствует булева матрица ?aJI порядка кХп: в ней столбцы соответствуют элементам множества А => (щ, ..an)t а строки — подмножествам Аи Ah,
I 1, если atf * | от если a-j <ф. А{.
Поскольку матрица Н«оП соответствует покрытию множества А, то она не содержит нулевых столбцов. При фиксированных к и п число таких матриц равно (2^ — 1) ”.
Обозначим через А(1Л, is) подмножество из указанных матриц таких, что в каждой из них, если удалить любую из строк tu ..i3, то получим матрицу, соответствующую покрытию множества^; через ..., г*)
обозначим подмножество множества А (iu ..„ ?s) таких матриц, в которых (в указанном смысле) невозможно удаление любой строки с номером, ОТЛИЧНЫМ ОТ ii, . . ,, Zs.
В силу определения матрицы из А (ц, ..is) не содержат столбцов, имеющих ровно одну единицу в строках Z,, .,ie. Поэтому
\A(h, ..., i.)l =(2k-s-l)\
Из формулы видно, что \A(iu ..is) I зависит от s, но не зависит от выбора строк. Эту величину обозначим далее через а",а. Аналогично IB(iu ..., гА | также не зависит от выбора строк, поэтому положим |-#(?ц ..?а)| — — hn
Пусть ilctijfl е А (г1} г?). Рассмотрим в ней все но-
мера строк, которые допускают удаление (сюда, в частности, войдут и номера ц, ..., is). Пусть iu < > •, ist i&+ll ' ’ • .:zг+Г — их номера п s + г = т. Тогда Hai3il ^ B(iu ..., zg,
is+Ь . . im) .
Отсюда
196 Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ
В силу формулы обращения (27)
ИЛИ
с - 2 (-1Г?(!";) (2й—1)п.
В частности, при 5 = 0
«.„=?; (— 1)т („) (г1*—т—О"*
1*1=0 \т /
Отсюда получаем для числа Ь^,о (неупорядоченных) тупиковых покрытий длины к выражение
гм-%"=й-2<-1)т(ю*)(2*-т-1 )*
т—о
и для числа Ь(п) всех тупиковых покрытий (&<7?)— выражение *)
к^О тп=0
Алгебраические соображения часто используются для построения рекуррентных формул... Эту ситуацию проиллюстрируем на примере получения рекуррентной формулы для чисел
<Мп)=» Г, + 2га + ... + и’\
Возьмем формулу бинома Ньютона (я + «- - „« + (;) »-> +(-)»«-*+...+(и2>+(:).
*} Это число совадает с числом тупиковых проверяющих тестов для универсальной таблицы 2" X Щ
Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ 197
С ее помощью имеем систему равенств
, . *\-т т , [пг\ т—1 . (пЛ т-2 , , ( »1 \ . [™\
(п+1) -в +(,)» +ув +...+(т__1]п+д, |(п-1)+1Г= (п - 1)" +^(„_1)’"-> + (™)(„_1)"-» + . . .
(2 + 1)” _2га+(“)2”-' +(^|2“-2+ . • ? +(„" 1)2 + (“), (I |. 1г =г+(';)г-’ +(2)о-г+...+(т=“,)1+(™).
НкЛПДМВаН их почленно, получаем рекурре нтную формулу
(Н Ь 1) = 1 + ^ щ _1 (п) + ^ С} | (п) 4" ? • *
•-- + (т™ 1) БЛп) -Ь- (^)5оИ,.
п , V С /,,\ И (п -Ь *)
еде *?,.(»),!= п, ДДН) = —2---?
Отсюда можно постепенно найти 5,„(?г). Н апример,
<« I I)’ I I (?)*» 1(2) С») +( 1 )^о- (")«
;1*| |):> — 1 _:!м.^_п = м^ии2п+1)
*-» ?л
д,(И)-я(" + <|6(2в + 1).
Метод производящих функций. Он исхшмьзуется для перечисления комбинаторных чисел и установления ком-Сипат<)р пы х тождеств.
Исходным пунктом являются последовать льность {аЛ комбинаторных чисел и последов ательност—ь функций
Ы*)) (г = 0,1, ...)?
1’ассматриваем далее ряд
се
21 й.ф* (*).
4=0
198 ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ
который, в случае, когда последовательность (щ) конечна, т. е. к, будет многочленом. При определенных
ограничениях даипый ряд будет сходящимся и тогда он в некоторой области будет задавать функцию Р{х)\
р{х) — 2
»=о
Эта функция называется производящей функцией.
Рассмотрим ряд примеров, относящихся к типичным случаям.
1. йг = ( " ) (? = 0, 1, и), ф4(а;) = ^. В этом слу-
чае мы уже имели
В качестве производящей функции здесь будет бином Ньютона (1 + ж)". С помощью производящей функции установим тождество
й-!(;)•?
Для этого возьмем тождество
(1 + х)гп =(1 + х)п (1 + х)п.
Оно эквивалентно тождеству
1й*ч,1(;и,1,ь)4
Сравнивая коэффициенты при я", получим
2. Рассмотрим пример на применение метода производящих функций, когда функция определяется степенным рядом.
Как известно, последовательность чисел /„, называемых числами Фибоначчи, задается рекуррентными соотношениями:
//1 3=1 /л—1 "р /и—2 и /о 1»
I
Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ 193
Возьмем срп(з:)=жп (га — 0, 1, ...). С этой последовательностью связан ряд
I
П=0
который В силу 1п<2п (поскольку 1п<2}п-1) сходится при ]х\ < 1/2 и определяет производящую функцию /'’(ж):
р м = 2 /Д
п~0
Так как
хР(х)~ 2
(*)= 2 /и-.*",
п=а
то
ос
xF {дг) -f x2F (я) = 2 (/»-і + /и—я) + 2 = А (г) — 1
Я=2
ИЛИ
(1-д:-д:г)^(д:)=1.
Отсюда находим явный вид производящей функции F(x):
