Дискретная математика (998286), страница 26
Текст из файла (страница 26)
и! (тп — п)! п! (тп — и)! и! И и! С(и, т) С(т, т) — —. т! (п — т)! т!(т — т)! т! (т' — тп)! (и — т)1 и!(и — т)! т! (т — т)! (п — т)! (п — т)." 3.3. Биноыиальные коэффициенты л! (и — т).' т'. (и — т)! (1 — т) )(п — 1) ! = С(п, т)С(п — т,т — т). 5.3.2. Бином Ньютона ТЕОРЕМА (х+ у) ~~~ С(т, п)х"у~ " =О Доказатяльство По индукции. База, т = 1 (х+ у)1 = х+ у — 1х1уо+ 1хоу1 — С(1,0)х1уо+ С(1, Цхоу1 = К С(1,п)х у п=о Индукциоиный переход; тп-1 (х+у)(х+у) ' =(х+у) ') С(т — 1,п)хпу™ " ' п=о ти-1 пт — 1 хС(т — 1,п)х у'" 1+ ~Ч1 уС(т — 1,п)хпу"' п=о п=о пт-1 тп-1 С(т — 1,п)ха+ту " 1-1- ~~ С(т — 1,п)х"у"™ п=о п=о пт-1 (С(т — 1, и — 1) + С(т — 1, и)) хпу'" " -!- С(т — 1, тп 1)х~уу =О пт-1 тп С(т,п)х"у~ и+С(т,т)х™у~ ~ = ~ ~С(т,п)х"у~ ".
П (к+у)™ = п=о п=о СЛЕДСТВИЕ ~' С(пт и) — 2~ п=о Доказ атал ьство п тп 2 =(1+1)™ = ~ С(, )1п1™*-п= ~ С( п=е =О Числа сочетаний С(т,п) называются также биномиальными коэффициентами. Смысл этого названия устанавливается следующей теоремой, известной также как формула бинома Ньютона. 146 Вава 5.
Комбинаторика »т СЛЕДСТВИЕ ~ ( — 1) С(тн,и) = О. »=о ДОКАЗАТЕЛЬСТВО О=( — 1+1)™ = ~ С(т,тт)( — 1)"1 "= ~ (-1)"С(от,о). »=0 5.3.3. Свойства биномиальных коэФфициентов Биномиальные коэффициенты обладают целым рядом замечательных свойств. ТЕОРЕМА 1. ~ , 'ттС(тп, и) = та2 »=0 2. С(то+а,)с) = 2 С(т,т)С(тт,к — 1). т=в ДОКАЗАтвпьстВО 1. Рассмотрим следующую последовательность из чисел 1,...,пь.
Сначала все подмножества длины О, потом все подмножества длины 1 и т. д. Имеется С(т,о) подмножеств мощности о, и каждое из них имеет длину и, таким образом, всего в этой последовательности 2 ОС(т,тт) чисел. С другой сто- »=О роны, каждое число з входит в эту последовательность 2К'-" 111ь)~ = 2 раз, а всего чисел т. 2. С(п+ т, 1с) — это число способов выбрать й предметов из то+ и предметов. Предметы можно выбирать в два приема: сначала выбрать т предметов из первых пь предметов, а затем выбрать недостающие й — т предметов из оставшихся тт предметов. Отсюда общее число способов выбрать й предметов составляет С(т,т)С(о, Š— т). С) ЗАМЕЧАНИЕ Последнее свойство известно как тлождеслмо Конти.
5.3.4. Треугольник Паскаля Из второй формулы теоремы 5.3.1 вытекает эффективный способ реккурентного вычисления значений биномиальных коэффициентов, который можно представить в графической форме, известной как треугольник Паскаля~. т влек Паскаль (1623-1662) 152 Глава 5. Комбииаторива ~ 999: (5 * 7) = 28 делятся на 5 и на 7; ~ 999: 13 * 5 * 7) = 9 делятся на 3, на 5 и на 7. Имеем: 999 — 1333+ 199+ 142 — 66 — 47 — 28+ 9) = 457. 5.5.2. Принцип включения и исключения ТЕОРЕМА аа п ЦА; =~Ч~ !А;! — ~Ча !АПА,!+ ~~ !АПА,ПАь! —.. 1=1 1=1 1(а<1<аа 1йа<1(абаи +( — 1)" 1!Аггь ° пА«!. Доказательство Индукция по и.
Для 11 — 2, 3 теорема проверена в предыдущем подразделе. Пусть и-1 и-1 Ц Ав аи ~ !Ав!— !АгпАЗ!+" +(-'1)и '!А;и" пА« 1<а<1(и-1 /и-1 и-1 Заметим, что 1 О А;) пА« аи ! ) ГАвпА«), и по индукционному предположению а=1 а=1 и-1 и-1 ! Ц(АпА«))=~ ~!А;пА«! — ~ ч!А;пА,пА !+... 1=1 1=1 1<а<1Ф~-1 + ( — 1)и !А1 и п Аи пА«!. Тогда и — 1 « — 1 и-1 = (11ал.а. = Ца,,>а.>- (Цлд.а.! а=1 1=1 а=1 !А ! — Ч~ !А Г|А !+" +1 1) -г!41 П ПА 1! + «=1 1<а<а йи-1 /и-1 +!А ! — ~~!АГПА„! — ~ !А;ПАгПА«!+...
а=1 1<а<1(и-1 + (-1)" г!А1п ° пА„1 пА«! 0А1 Следующая формула, известная как при11цип включения и исключения, позволя- ет вычислить мощность объединения множеств, если известны их мощности и мощности всех пересечений. $4В Глава 5. Комбинаторика ОБОСНОВАНИЕ Заметим, что в искомой последовательности и-элементных подмножеств (каждое из которых является возрастающей последовательностью г1 чисел нз диапазона 1..т) вслед за последовательностью (аг,...,а ) следует последовательность (Ь1,..., Ь„) = (а1,..., ар 1, ар + 1, ар + 2,..., а + и - р+ 1), где р — максимальный индекс, для которого Ь„= ар+ п — р+ 1 < т. Другими словами, следующая последовательность получается из предыдущей заменой некоторого количества злементов в хвосте последовательности на идущие подряд целые числа, но так, итобы'последний элемент ие превосходил т, а первый изменяемый элемент был иа 1 больше, чем соответствующий элемент в предыдущей последовательности.
Гаким образом, индекс р, начиная с которого следует изменить вхвост последовагельности», определяется по значению элемента А(н]. Если А(гт] < т, то следует изменять только А(гг], и при этом р: = п. Если же уже А[я] = т, то нужно уменьшать индекс р: =р — 1, увеличивая длину изменяемого хвоста. СЗ Пример Последовательность и-элементных подмножеств т-элементного множества в аексикографическом порядке для гк = 3 и т = 4: (1, 2, 3), (1, 2, 4), (1, 3„4), (2, 3, 4). 5.4. Разбиения Разбиения не были рассмотрены среди типовых комбинаторных конфигураций в разделе 5.1, потому что получить для них явную формулу не так просто, как для эстальных.
В этом разделе исследуются основные свойства разбиений, а оконча- тельные формулы приведены в подразделе 5.6.3. 5.4.1. Определения ПУсть З = (В1,, В„) есть разбиение множества Х из та элементов на и подчножеств: /Вг Х В' ~е ВгПВ1 е при 1 т' 1=1 Вас Х, Подмножества В, называются блоками разбиения. Между разбиениями и отношениями эквивалентности существует взаимноодно- значное соответствие (см. подраздел 1.7.2).
Если Е1 и Еэ — два разбиения Х, го говоРЯт, что Разбиение Е1 есть измельчение РазбиениЯ Его если каждый блок Ез есть объединение блоков Е1. Измельчение является частичным порядком на чножестве разбиений. 5.4. Разбиения 5.4.2. Числа Стирлинга второго рода Число раэбиеиий т-элемеитиого множества па и блоков называется числоэг Стирлинга' второго рода, и обозначается Я(т, и).
По определению положим Я(т,О):=0 при т > О, Я(т,т):=1, Я(0,0): =1, Я(т, и)". = 0 при и > т. ТЕОРЕМА Я(та и) Я(т 1, и — 1) + иЯ(т — 1, и) доказательство Пусть 3 — множество. всех разбиений множества (1, т) иа и блоков. Положим 3,:=(Х Е 3 ~ ЗВ Е Х В = (т)) а Зз.=(Х Е 31-ЗВ Е Х В = (т)), то есть в З„входят разбиения, в которых элемент т образует отдельный блок, а в Зз — все вставание разбиения. Заметим, что Зз = (Х Е 3 ! т Е Х =г ~Х~ > 1) .
Тогда 3 = Зт и 39, 3, ПЗз = О. Имеем !Зд! = Я(т — 1, и — 1), Щ = п Я(т — 1, и), так как все разбиения Зз получаются следующим образом: берем все разбиения миожества (1,..., т-1) иа и блоков (их Я(т — 1, и)) и в каждый блок по очереди помещаем элемеит тп. Следовательно, Я(т, та) = )3( = (За ) +139 ~ =' В(т — 1, и — 1) + иЯ(т — 1, и).
на-а ТЕОРЕМА Я(т,и) = 1 С(тп — 1,1)Я(т',и — 1). а=н — 1 доказательство Пусть 3 — множество всех разбиений множества (1,...,т) иа и блоков. Рассмотрим семейство В: = )' В с 2О'- 1 ( тп Е В). Тогда 3= ~~Зв, Вев где Зв: = (Х ~ Х Е 3 Ьг В Е Х), причем Зв. ПЗв» = Я, если В' ф В >>. Пусть В Е В и 'Ь: = (В1. Тогда )Зв ~ = Я(т — Ь;п — 1). Заметим, что ! (В ЕЗ / )В~ = Ь) / = С(т — 1,Ь вЂ” 1).
джеймс Стирлинг (1699П 770) 150 Глава б. Комбинаторика Имеем, м-Ьв-1) Я(т,п) = )З~ = Ь=1 Ц ЗВ ВЕВ й )В)=Ь яъ-Ьн-1) С(т — 1, Ь вЂ” 1) Я(т — Ь, и — 1) = Ь=1 н-1 С(т — 1, т — т — 1) Я(т, п — 1) = 1=из-1 тн-1 — С(т — 1, т)Я(т', п — 1), Ь=и-1 где ь:=т — Ь. 5.4.3. Числа Стирлинга первого рода 5.4.4. Число Белла Число всех разбиений т-элементного множества называется числом Белла и обоЬначается В(тп). В(т): = ~~1 ' Я(т,и), В(0): =1. и=о ТЕОРЕМА В(та+1) = ') С(гп,г)В(1) Ь=О ДОКАЗАТЕЛЬСТВО Пусть З вЂ” множество всех разбиений множества 1..т+1. Рассмотрим множество подмножеств множества 1..т+ 1, содержащих элемент т + 1: В: = (В С 2О'"'~+~) ) т+ 1 Е В) . Число сюръективных функций, то есть число размещений т предметов по и ящикам, таких что все ящики заняты, называется числам Стирлинга первого рода и обозначается в(т, п). Каждое разбиение множества (1,..., тп) соответствует ядру сюръективной функции и обратно (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
