Введение в прикладную комбинаторику, Кофман А. (984071), страница 9
Текст из файла (страница 9)
(10.60) Отсюда Так как начальные значения 1(и, г) и Л'0" совпадают для всех п и рекуррентные соотношения, порождающие 1(п, г) и Л'0", также совпадают, то г(й(и, г) =Л'0". (10.61) аь =Е[7т'"! ~~'.~ п~р(п), й О, 1, 2, ... (!0.62) и 0 Рассмотрим производящую функцию для р(п): (! 0.63) Таким образом, таблицы 6.1 и 10.2 могут быть получены одна из другой. Основные свойства формул моментов. Числа Стирлинга первого и второго рода могут появиться при вычислении моментов вероятностного закона, определенного на множестве (О, 1, 2, 3, ...). В самом деле, пусть р(и) (п О, 1, 2, ...) — распределение вероятностей случайной величины Л'.
Моментом порядка Й случайной величины й! называется математическое ожидание )уь: Беря последовательные производные и" (г) по г и полагая затем г = 1, легко получаем ДГ Е[Л'(М вЂ” 1)(М вЂ” 2) ... ()У вЂ” г+ 1)]= —,а'(г) ~ . (10.64) Числа Е[)е'(М вЂ” 1)... (М вЂ” г+ 1)] дают возможность последовательно вычислить Е[МР], 1 = 1, 2, ..., г. Факториальным моментом порядка й случайной величины аг называется математическое ожидание Р» = Е [У (И вЂ” 1) (У вЂ” 2) ...
(йà — й+ 1)], У = й, й -]- 1, ...; (10.65) ~» = ~р и (и — 1) (п — 2) ... (и — й -[- 1) р (и), Следовательно, 1» р» = †„, а'(г)~ ог Ьр» (10.66) Между р» и а» имеет место символическое соотношение р» = а (а — 1)(а — 2) ... (а — й + 1), а' †' а„ г 1, 2, ..., й. (10.68) Таким образом, опять приходим к числам Стирлинга первого рода р»= ~рз(й, г)а', а' — а„г 1, 2, ..., й (10.69) т=р и второго рода и»=Хз(й г)рр р -'[1т г= 1, 2, ..., й. (10,70) т=1 Производящие функции моментов ам и» и у» связаны между собой следующими соотношениями. Предварительно обозначим а'(г) = Е [Ян] = Р (О) + р (1) г + р (2) г'-[- р (3) з'-[- ... (10.У1) ') Попутно заметим, что ир рр тр — П Можно определить также моменты третьего типа, биномиальные моменты ') у»=Е[С,"р]=~~~р~ С'„'р(п)= — „,, Ф=й й +1, ... (10.6у) Осуществим разложения а'(е) =Е(еог]=р(0)+ р(1) е'+ р(2) е" + р(3) е" + ...
= = р (О) + р (1) ) 1 + г + —, + з, + ...~ + + р(З) ~1+Зг+ —, + — + ...~+ ... = = р (О) + р (1) + р (2) + р (3) + ... ... + [р (1) + 2р (2) + Зр (3) + ...! г + 1 (р(1) 1 2гр(2),+Ззр(3)+ ] ~ + + (р (1) + 2зр (2) + Ззр (3) + ...) — + ... = зз зз тз з' =ао+аг+а,— +аз — Г + ... = г а„— = — е", =о а' — ' а„„г=1, 2, 3, ...; ао — !. (! 0.72) Итак, а"(е')=е'*, а' — а„г=1, 2, 3, ...; ао-!. (10.73) Рассмотрим разложение а' (г + 1) = р (О) + р (1) (1 + г) + р (2) (1 + г)з+ р (3) (1+ г)з+ = р (0) + р (1) + р (1) г + р (2) + 2р (2) г + р (2) гз + + р (3) + Зр(3) г + Зр (3) г'+ р (3) г'+ ...
= Сор (О) + С ~ р (1) + С ~ р (1) г + Сор (2) + Сор (2) г + Сор (2) г' + + Сор(3)+ Сзр(3)г+ С',р(3)г'+ Сор(3)г'+ ... = СоР(0) + С7р(1) + Созр(2) + Сор(3) + . „ ... +(С!р(1)+ Сор(2)+ Сзр(3)+ ...]г+ + !Сор (2) + Сзр (3) + Сор (4) + ...1 гз + + (Сзр(3)+ Сор(4) + Сззр(5) + ...]го+ ... = = Уо + У~ г + Узгз + тзгз + ... (10.74) Обозначим Г (г) = уз+ узг+ узгз+ узг~+ Сравнивая (10.74) и (10.75), получаем Г" (г) =а'(г+ 1), (10.75) (10.76) 57 Итак, а'(е') = е"*, Г" (г) = а" (г+ 1) = ее* еоо = 1" (е» вЂ” !) (10.79) (10.80) (10.81) что . ро ° где в некоторых из этих формул предполагается, а' — 'а„г= 1, 2,...; ао — '1, р' — 'р„г=1, 2, Из (10.80) вытекает Напомним, что а'(г) = еа'*-'~. (10.82) а" (г) = р (О) + р (1) г + р (2) го + ...
+ р (и) г" + ... (10,83) Представим правую часть (10.82) в следующем виде: рого рого рого вам и еа*е-а а-а[1+на+ — + — + ... + — + ...~ й! в! ' ' в! (0" †' ~о в 1, 2, ...; ~о †' 1). (10.84) Сравниваем (10.83) и (10.84) относительно гт о р(п)-е-а — „,, 8" — 8„, п-1,2, ...; Зо — !. (10.86) Разлагаем е-а: ро рй е в 1 — р+ — — — + +( — 1) + 2! 3! И вЂ” г=! 2, ° ..; ро — '1 (10.86) Подставляя (10.86) в (10.85), получаем из этого символического разложения СО р(п) = ~~~( — 1) — „",+", а=О, 1, 2, 3,... (10.87) о-о ба Выпишем символическое представление еа'. го э В" (г) = ео* = ро+ 8,г+ 11, 2! + "о з + 3 з! =р(0)+ р(1)+ р(2)+ р(3)+ ... ...
+ [1 ° р (1) + 2р (2) + Зр (3) + ...[ г + +[ 2 ° 1р(2)+3 ° 2р(3)+ ...[го/2!+ +[ 3.2.1р(3)+ )гз/3!+ = р (О) 1+ р (1) (1 + г) + р (2) (1 + 2г + г') + р (3) (1 + + Зг+ Зго+ го) + ... (Д' — ' Д„г = 1, 2, 3 . Зо ° 8о) (10.77) В'(г) = р (О) + р (1) (1 + г) + р (2)(1 + г)' + р (З)(1 + г)' + ... = 00 = ~о р(г) ° (г+ 1)" =а*(г+ 1). (10.78) о О Наконец, ввиду (10.67) имеем ОО р(п)= тз ( — 1)зСая+ау„+„и=О, 1, 2, 3, ... (10.88) Это — соотношение, обратное к (10.67). УПРАЖНЕНИЯ 10А.
Вычислить числа Стирлинга з(9, г), з(!О, г), й(9, г), з(10, г). 1ОБ. Рассмотрим зкспоненциальное «-преобразование зз(«, г) для по. следовательности з(л, г): « зг («, г) ~ з (и, г) — = з*г ( *, г), з (О, 0) = 1, г ~ и. я о В разложении з«з!о и члены з ( °, г)" заменяются иа з(и, г). Показать, что з'(«, г) удовлетворяют дифференциальному уравнению д ( ! + «) — зг («, г) = зг («, г — 1), й« решение которого есть !и (1 + «)' г! 10В.
Доказать, что л з(л+ 1, г) = ~ч'„С!з (1, г — 1). 1-0 10Г. Показать, что оператор («П)" (см. (6.26)) и оператор «"Гз» удовлетворяют уравнениям л и («1))" ~ й (л, г) «'0', «Ч>" ~яр~ з (и г) («!))'. г е г 0 1ОД. Вычислить злементы первых пяти строк и столбцов матриц (!зз!! и !!уз!! — числа Белла первого и второго рода порядка 2. 1ОЕ. Представить с помощью формулы Бруно р~з~ как функции от у!З1, й ~ (л, и и!з1, й ~ (и, для о = 6. 1ОЖ.
Вычислить а, й = 1, 2, 3, и а" (г) для следующих функций р(л): а) р()т', о) С" р" (! — р)~ ", 0<р<1, л О, 1, 2, ..., АЕ б) р(л) = Р( Р) <Р<1 ~~ 2 ° ) („) Сл О, о=О; Лаз-ь 0<р<1, л=о 1 2, ..., г+л~)2, г=1 2,...; г) р(п) — ~-, и = О, 1, 2, ..., Л ) О. 1ОЗ.
Вычислить факториальные моменты (!з и биномиальные моменты ум я=1, 2, 3, для функций из упражнения 10Ж. ГЛАВАП РАЗВИТИЕ МЕТОДОВ ПЕРЕСЧЕТА й 11. Введение Мы ознакомим теперь читателя с наиболее общим методом пересчета, который можно назвать «методом просеивания» нли «комбинаторным просеиванием». Принцип его прост: с любым свойством .У можно связать его расщепление на некогором множестве А, в соответствии с которым А разбивается на две части: подмножество Аь образованное элементами, обладающими свойством,У, и Ам образованное элементами, не обладающими свойством У, т.
е. обладающими свойством У. Выбирая свойства под. ходящим образом, можно последовательным просеиванием пересчитать подмножества с наложенными на них теми или иными ограничениями. Эти методы давно известны, их можно найти в работах математиков Бернулли (ХЧП1 век). Веком позже Сильва указал общие формулы просеивания (или пропускания через решето; в теории чисел этот метод известен под названием «решета Эратосфена»). Но только в работах выдающегося современного математика Пойа подобные методы оказались исключительно плодотворными. Принцип просеивания применим не только к пересчету, но также к перечислению и оптимизации.
Перечисление с помощью латинских прямоугольников — метод, который осуществляет исключение путем разделения. Оптимизация по методу «ветвления и ограничения» и принцип оптимальности Беллмана — Понтрягина также находятся в рамках этих понятий. В последующих главах общность этих методов проявится более четко.
$12. Формула включения и исключения Пусть А — конечное множество и А, с= А. Будем обозначать через А, дополнение А, по отношению к А, а через СагбА— число элементов в А. Тогда А,()А,=А=йСагдА,=СагбА — СагбА,. (12.1) 60 Если А, с: А и А,с: А, то (А~ () А ) () (А, () А ) = А Ф Сагг! (А, П А ) = Сагг! А— — Саго А, — Сагд А, + Сагг!(А,й А,), (12 2) В самом деле '), А, Ц Аз = А, П Аз (12.3) А ~ () Аз = А — А, () Азэ А, ПА,=А — А,()Аз (12.4) откуда (12.5) (12.6) Сагг((А~ () Аз) = Сагг! А, + Сагг! А, — Сагг((А, П А,), Покажем, что формула (12.2) обобщается на случай п подмножеств А, с: А, ! = 1, 2, ..., гм Сагй(А, П А, П ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
