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