Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
fW=; * г-
1 — X — X
Решая уравнение
х2 + х-1 = 0,
находим его корни
-1 ±1/5 ^1.2 — 2
Найдем разложение А (я) на элементарные дроби:
1 a ь
І—-Х-Х2 хг-х ? х2-х Имеем
ах2 + Ьх ! — (а + &)л: = —1. Это справедливо, если
200 ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ
Далее, воспользовавшись формулой для суммы убываю-
щей геометрической прогрессии ^При <С 1^*), получим
1 = _1_ ( 1 1_\ ^
1-Х-Х2 Уь\х1~х Т2~Х)=‘
1/11 11
<1, 7
V 5 х2 4_±\
\ *1 *я/
JL.fi V (-V1 — IV (—У1'!
? «.ял**';“
. “ =п+1 _ Т1 + 1 “
?к« го (*лГ+1 Т/5,1“014 411
откуда
'-гЛ№Н-№)“]•
что дает явное выражение для чисел Фибоначчи.
3. В случае, если рост комбинаторных чисел достаточно велик, используются так называемые экспоненциальные производящие функции. Пусть а„ = Ф(и) и <рп (г) =* гп/п1 Рассмотрим ряд
2
т
Т<=0
ф (и) п
Ъ Ч
Теорема 7 (Белл). Имеет место следующее тождество
е‘г-' = У л
71=0
Доказательство. Очевидно, что
е«г- 1 „ ег+гУг1+... _ ег.ег^121 ^гп!п\
•) Соответствующие ряды также сходятся в окрестности
9 = О-
ТГ. II. КОМБИНАТОРНЫЙ АНАЛИЗ
201
где
/ = 1 +ТТ + 2Г+ ••• + у + ??•>
г212
?Т ? ?» ~Ь у Т- • I • I
/'2| -1+‘2 +
31 21 ^2!)2
_з _е
У (21)
а о
= 1 + +
31 21 (З!)5
и (30
.+ < ? Ы
Перемножая эти ряды и собирая члены с г”, находим, что коэффициент при г'1 равен
ЕЛИ, что то же самое,
1 ^ «!
п| <>1л±|*> ОУ--? У (Ю'чгц1*. •?(»!)'" п|
(последнее в силу теоремы 3). Теорема доказана.
Данное тождество может быть обобщено следующим образом:
х^-г) ^ ^ 1п Н **
где
п!
п=о
к (х) =• 2 ф (»1 к) х.
ь=о
Доказательство аналогично. Собирая в соответствующем произведении рядов члены с ?пхь и замечая, что ^ + ... . -. + С = к, находим, что коэффициент при %"хн равен
202 ч. И. КОМБИНАТОРНЫЙ АНАЛИЗ
Так как ?„(1) = Ф(гг), то как следствие имеем
оо
ee2-i _ ^ ф М2 (тождество Белла).
?4=0
Выполняя очевидные преобразования и пользуясь (29), получаем
ое оо
-« у кпа*_(. х ** \ у knxh
At к\ V1 1! 2! kl
fe=0 fe=0
2{kn {к-1)" (к- 2)n ^ „
Ui В (A-1)1 + 2! (ft —2)1
= 2 Ф(п, к) xh = 2 Ф (n> {2).
ft=0 fe=0
Полагая здесь x = 1, получаем
оо
Ф(п) = — 2(|| (тождество Добинского).
e fe=0
§ 4. Оценки и асимптотики
для комбинаторных чисел
Проблематика этого параграфа использует ряд понятий из математического анализа [8, 14, 26], которые позволяют сравнивать поведение функций в окрестности некоторой точки. Напомним некоторые из них.
Пусть /(я) и ??(:?)— действительные функции, определенные на некотором подмножестве & действительных чисел, и а — некоторое число (—1°° < а < ~Роо), Число о является предельной точкой для если в любой окрестности а содержится точка из множества отличная от а.
Положим f(x) — 0(g(x)) при х^а, если существует такая константа С, С>0, что в некоторой окрестности а, исключая, быть может, а,
!/(*) I <<%(*)!.
Примеры. 1. Пусть / (я) = х, ^(а) = х1 и а = +<». Тогда х = 0{х2) при х -> 4*°° (здесь х^х2> если
2. Пусть }{х) = 1п (1 + л:) — {х —уУ#(.г) = и а = 0.
М. II. JnU.TIiJlltLAiUI'IlIDIia АП А.'111.3
Тогда
1п (1 + х) — = О (я3) при X -? О,
Данное определение эквивалентно следующему: / (г)==* “С1 (?(#)) при ха, если существует функция ф(х) такая, что в некоторой окрестности а, исключая, быть может, а,
/(л:) == ф(ж)'я(л) и ]ф(х)|<С.
В случае, если в некоторой окрестности а (исклмочая, быть может, а) g{x)=fL0, то определение допускает видоизменение: 1{х)= 0(д{хс)) при х -*? а, если сущее-твует такая константа С, С > 0, что в некоторой окрестно -сти а, исключая, быть может, л,
/(*)
g (я)
<С.
Положим f{x)z=:g (х} яри х о, если при х -> а. имеют место одновременно /(г) = 0(g (х)) и g{x) = 0{р{х)). В этом случае функции /(х) и ?(я) имеют ОДИН ZH тот же порядок (при х->а), а их знаки в окрестности а друг с другом, вообще говоря, никак не связаны.
Полошим /(х)^3 o(g(x)) при х а, если существует функция ф(х) такая, что в некоторой окрестности а, исключая, быть может, «,
/(х) = ф(х)#(х) и ф(х)-»-0 при х -> а.
Примеры. 1. Пусть f{x) = х, g{x)~ хг и а = 4-с». Тогда х = о(х2) при х-*-4-°о. Здесь ф(х) = 1/х и ф(я:)-»“0 При X -*? 4-00.
2. Пусть /(х)’ —х", (е> О —малый пара-
метр) иа — О. Тогда /(x:) = o(g(x)) при х -*? 0.
Очевидно, что если в некоторой окрестности а (и склю-чая, быть может, a) g(х^О, то условие /{х) = о( ?(х)) при х -+? а эквивалентно условию
/ (х) п
L-~-{—^0 при х ->а.
six) Г
Для отношений «О» ж со» имеют место следующие свойства.
1. Свойство транзитивности. Если f{x)= 0(g(3K)) и g{x)=> 0(h(x)) при х^а, то /(х) = 0{h{x)) при _х-^а.
Если f(x) =»o(g(x)) и g(x)=o(h(x)) при х -> а, то /(х) = о(й(х)) црих-*- а,
«V'X i*r Jb VU*UUllim.l vr iiuxn лпллиа
2. Если fi(x)=^0(g(x)) и h{x) = 0(g(x)) при x~>a, то Л(ж)+ f2(x) = 0(g(x)) при a:->д.
Если /i(a;) = 0(g(z)) и h(x) = o(g(x))' при x-+a, to fi{x) +fz(x)= o(g(x)) при x -*? a.
3. Пусть ф(;г)—произвольная функция, определенная в окрестности а. Тогда
из условия f{x)*=0(g(x)) при х -? а вытекает, что /(ж)1]!{ж) = 0(^(ж)^(л:)) при х й\
из условия j(x) = o{g{x)) при х^-а вытекает, что /(ж)^{х) = о(^(ж)г^(гс)) при ж -»? я.
4. Из условия f(x)~ o(g(x)) при х -*? а следует, что / {х) ~ О (g (х)) при х а.
