Теперь можно записать, что

4=0 4=0

= С]х + ±{CU *Cli)xk+1 = Ш* + ±(Cl+2 * Cl,)хк = ±dk.

4=0 к=2 4=0

Сравнивая коэффициенты при одинаковых степенях*, получим d0=0, d,=Cl dk=Cl1+C3k+2, к =2,3,....

Таким образом,

1 + 2 -к..+к 1 = S£ J ~t\ li-

+l)(k+l)k

<=o

Задача. Показать, что £С^+- =с;+А+1или

Заметим, что - - = £С*+Лх* является производящей Ц + х) * 4=о

функцией последовательности =С*<А Следовательно, иско-

к. к

мая сумма равна lCr+j = ai.

1=0 /=0

к

Раесмотрим последовательность Ък =ак. Так как Ък и ак свя-

/=о

ч 4[х) \

1-х (l-jc)r+r

(3.1.9) позволяет записать последнее выражение в следующем

-X *=о /-.о /=о

Задаад. Пусть 1и 7- целочисленные случайные величины и определены их ряды распределений. Характеристической функцией распределения случайной величины (св.) Xназывается

функция

8x(s) = ±P(X=k)sk и gy(S) = ]rP(Y=k)sk.

4=0 4=0

заны частичной суммой, то B(xf= = -- . .Разложение

3.2. Линейные рекуррентные соотношения

Таким образом, gx(s) - это производящая функция последовательности чисел Р(Х= к), где к= О, 1,.... Будем полагать Ха Гнеза-висимыми случайными величинами (св.). Рассмотрим св. Z = X+Y. Очевидно,что

P(Z=k) = P(X + Y =к)= 2Р(Х= i)P(Y =k -/).

Ввиду свойства свертки для производящих функций характеристическая функция с.в. Z может быть записана таким образом:

3.2. Линейные рекуррентные соотношения

Рассмотрим последовательность {ип}, п = О, 1, . Будем говорить, что задано однородное линейное рекуррентное соотношение с постоянными коэффициентами порядка г, если для членов последовательности {ип} выполняется равенство

Un+r =clu +r-l +c2Un+r-2+---+crun> (3-2.1)

где сь с2,..., сг - постоянные величины. Выражение (3.2.1) позволяет вычислить очередной член последовательности по предыдущим гчленам. Ясно, что, задав начальные значения м0, щ,..., иг ь можно последовательно определить все члены последовательности. Мы рассмотрим общий метод решения (т.е. поиска ип как функции от п) рекуррентного соотношения (3.2.1).

Для решения задачи достаточно найти производящую функцию

ВД = £иах* (3.2.2)

последовательности Введем обозначение для полинома

К(.Х) 1 - . j Л - CjX - ... - с

и рассмотрим произведение

U(x)K(x =

Непосредственным умножением можно убедиться, что С{х)-это полином, степень которого не превышает г - 1, так как коэффициенты при х +г (п = О, 1,...) в U(x)K(x)согласно уравнению (3.2.1), равны и„+,- (с^ип+г х + с2ип+г 2 +... + сги„)=0 .

Таким образом, {/(х является суммой функций вида

(l-axf ti k Г

Тогда выражение (3.2.4) примет вид

Цх) ,-=1л=1 А=01 / Данное разложение является производящей функцией

Щх = последовательности Для определения необ-

ходимо найти коэффициент при в разложении (3.2.5).

Задача. Найти члены последовательности удовлетворяющие рекуррентному соотношению = 5ulht { - 6ип, щ = и( = 1.

Решение. Щх) = 1 - 5х + бх2, K(x)U(x)= С(х).

Характеристическим полиномом соотношения назы-

F(x)=xr-clxr~l -c2xr-2-...-cr lx-cr. (3.2.3)

Выполним разложение Дх) на линейные множители ВД=(* -ауУЧх-а2)с'г...(х-аг)е',

гдее1+е2+-- +ег = г.

Сравнивая К(х) и F{x), запишем К(х)=хгЕ}- \ Отсюда

= (\-а.ухУ1(\-а2х)ег...<\-агх)г щ + е2 +... + ег = г.

Данное разложение на множители используем для представления

в виде суммы простых дробей:

F7~~v =Z-Z-(3.2.4)

3.3. Неоднородные линейные рекуррентные соотношения 51

Выполним данное умножение: (1-5х + бх2) + щх+ х2 + ...) = = и0 + ( ! - 5и0)х+ (и2 - 5 ! + 6и2)х2+... = НО + (и, -5и0)х= 1 - 4х.

Таким образом, С(х) = 1 - 4х.

Характеристическийполиномf[x) = х2 - 5х + 6 = (х - 2)(х - 3),

Отсюда Щх) = П^ = = А +--. Значениявели-

А{х) (1-2х)(1-Зх) 1-2.4 1-Зх

чин А и В находим методом неопределенных коэффициентов: А 2, В = - 1 Наконец, принимая во внимание (3.1.2),

и(х) = + -=2-±2кхк-±Зкхк=£<2к*1-1к>хк-

1-JJC JUO JtsO

С другой стороны, Щх)= УнА; . Поэтому, сравнивая коэффициенты при одинаковых степенях заключаем, что ы„ = 2я+1--3 .

3.3. Неоднородные линейные рекуррентные

соотношения

Неоднородное линейное рекуррентное соотношение имеет вид

u +r = clun+r l + c2un+r 2+...+cl.un + Ь„, (3.3.1)

где величина Ь„ в общем случае является функцией от п. Общее решение соотношения представляет собой сумму частного

решения неоднородного уравнения (3.3.1) (т.е. любого решения, которое ему удовлетворяет) и общего решения соответствующего ему однородного соотношения (3.2.1), которое находится рассмотренным способом. Общих способов определения частного решения нет, однако для специальньгх значений Ъ существуют стандартные приемы определения Рассмотрим на примере в некотором роде универсальную процедуру, которая позволяет сразу находить общее решение неоднородного уравнения

Задача. Найти {и„}, если известно, что = + (п + 1) и и0=1.

Умножив левую и правую части рекуррентного соотношения на получим

и„+]х = и^ + (п+ 1У.

Суммирование последнего уравнения для всех п дает

п=0 п 0 п=0

Свойства операций с производящими функциями позволяют данное выражение привести к виду

х (1-х)2

Учитывая, что = 1, запишем

и{х) = 1-£=<\-х+х2)%с12х =±ипх\

(1 -X п=0 л=0

Сравнивая коэффициенты при V, заключаем, что

-4+2 + 4---

Задача. Найти число замкнутых маршрутов длины п по ребрам треугольника ABC. Длину ребра принять равной единице. Нача-/ \ льная и конечная точка маршрутов - верши-

ли- С на А.

Решение. Введем обозначения: ап - число замкнутых маршрутов длины п из вершины А в вершину А; Ь„ - число маршрутов длины л из вершины^ в вершину В; сп - число маршрутов длины п из вершины А в вершину С.

Очевидно, что из условия симметрии задачи Ьп=сп. Величины же а„, Ъп, сп связаны системой рекуррентных соотношений:

an+i =Ь„ +сп,

, Ьп+\ =ап +Ь„, Сп+У =ап +СЛ,

С учетом последнего равенства = = О, 1, система приводится к виду

1А+1 = °я + V

Выражая из первого уравнения и подставляя во второе, получим однородное рекуррентное соотношение относительно последовательности {а„}. Запишем его в принятых обозначениях, полагая ип = ап:

= + 2и„, и0 = 1,щ = О, где = О, 1, .

Решение данного соотношения получим согласно изложенной выше теории.

К(х)= 1-х- 2Х2, Щх)К(х)= С(х) = 1 -х.

Характеристическийполином

F(x)= х2-х-2 = (х- 2)(х+ 1).

Отсюда Щх) = l~X = -+

(1-2jc)(1+x) \-2х 1+jc Перепишем в развернутом виде по степеням У:

вд=+£Г*Ч±12(-1) * =Гг Г -Ъ*.

Jn=0 Jn=0 л=0 /1=0

Сравнивая коэффициенты при У, заключаем, что число замкну-

2 +(-1) 2

тых маршрутов длины п равно ип =-1---.

3.4. Обобщенное правило произведения

Пусть Sh S2,..., Sn - произвольные множества. Q = {©j, а>2, ю3- } - множество весов, где под (Oj будем понимать любой из символов \,х, у, z, х~1, у 1, z~l и их произведения. В отличие от элементов, вес - это число либо переменная, которая может принимать любые числовые значения. Назначим каждому элементу* е$(/=1,2,...,п) вес ф)е Q. Во многих задачахтребуется определить количество элементов с определенными свойствами, а не их вес. В этом случае полагают со(i) = 1.

Пусть Сь - количество элементов множества Sj с весом <а, тогда A(Sj )= 2Ciata- сумма весов элементов множества Щ.

Рассмотрим прямое произведение множеств

S =SlxS2x...xS ={£=(sls2...sn)\sleSi,i=ln}.

Положим вес элемента множества равным

©(e) = ф{s2 s ) = ф{) a(s2 ) ф„) = Yla(si)еQ-

Пусть Еш - количество элементов г е S с весом ю, тогда A(S) = УЕЫ ш - сумма весов элементов множества .

Теорема. А( S) = A(Sl)A(S2)...A(S ). Доказательство.

и Z Z Zwi)to2) J=

Хш()=д^)д^2)...д^)-

А

Задача. Найти количество замкнутых маршрутов длины 2л по ребрам трехмерного куба. Начальное и конечное положение - вершина куба.

Решение. Исходное положение - вершина Каждый шаг движения по кубу - это выбор одного из трех ребер. Пусть 1 обозначает выбор ребра вдоль оси ОХ, 2 - вдоль оси OY, 3 - вдоль оси OZ. В соответствии с этим введем множества $2 такие, что

5*1 = S2 = ... = S2 = {1 2,Ъ). Тогда все маршруты длины составят множество x x ... х Например, маршрут означает, что из пошли вА5, затем вЛ6, вернулись в и поднялись в А2.

Назначим веса элементам множества: <о(3) = z. По правилу обобщенного произведения сумма весов всех маршрутов длины 2я равна A(S) = A(Sl)A(S2)...A(S )= (х + у + z)2n, т.к. A(S,) = x + у + z

После возведения в степень получим, что

A{S)=(x+y + z)ln =ZZZcV;cV*.* (3.4.1)

r j k

где vVj - вес маршрута, включающего шагов вдоль оси OX, j - вдоль OYuk - вдоль OZ(i +j + к = 2л), aijk- количество маршрутов с весом

Заметим, что только маршрут, заканчивающийся в Aq, имеет вес Л У< с четными степенями ij, к, т. к. в замкнутом маршруте, сделав шаг вдоль оси, необходимо вернуться по этой оси. Для выделения таких маршрутов положимл: =у2 = 7? = 1 (х, у, z - произвольные). Тогда выражение (3.4.1) примет вид

(х + у + z)2n = С0 + Cyz + C4xz + Cfjcy, (3.4.2)

где С0 - число маршрутов, заканчивающихся вА$; С2 - в А2; С4 - в Ац\ С6 - в А\.

Учитывая симметрию точек/1;>. Л4. А\ относительна можно заключить, что С2 СА = = С. Тогда из системы (3.4.2) следует, что

U + у + z)2 - С, + ( (;: + л:- + ху). (3.4.3)

Уравнение (3.4.3) содержит два неизвестных С0 и С при х2 = у2 = z = 1 Для их определения составим систему уравнений из выражения (3.4.3), полагая х =у =z = 1 и х =у = 1, Z-1. Это возможно, т.к. выполняется условиех2 =у2 = z2= 1. Получим систему

[(i+1+i)2* =с0 +c$ui+i) Г з2 =с0 +зс

[(Hl-l)2 =С0+С(-1+1+1) \1 = С0-С

З2 +3

Отсюда С а = - число искомых маршрутов.

Задача. Найти число решений р, q уравнения

2р + 3q п, где р, qe{0, 1,2,...}.

Решение. Введем множества: Si = Щ\Р = 0. U 2,...}, S2 = {3q\q = = 0, 1, 2,...}nS = SlxS2 = {(2p,3q)\p,q=Q, 1, 2,...}. Назначим веса элементам данных множеств следующим образом:

®(2р) - х?р, 0)(3(/) = x3f?, и

со(ё) = ш((2р, 3q)) = х~*й'~ = х^11 л-3 = со(2/>)ш(3).

Веса элементов определены таким образом, что выполняется правило обобщенного произведения A(S) =A(Sl)-A(S2)Легко заметить, что степень веса х23 любого элемента Е = (2р, Ъа) eS дает одно из решений исходного уравнения 2р + 3q = п.

Раскроем выражение A(S) = A(SiyA(S2):

HO + U\X + и2- + +U,/ + ... =

(X + X21 +X22 - ... + Xp + ...)(X3°+ X31 + A 3 2 - ... ...)

6 \- 1 1

=(l+x2+x4+...)(l+x3 +x6+...)= -

l-xzl-xJ

где u - число решений уравнения 2p + 3q = п. Фактически, сумма весов A(S) элементов множества Sявляется производящей

функцией числа решений уравнения 2р+ 3q = n. Таким образом, 1 I

A(S) =---- - -- у Разложим данное выражение на множители:

1(1-х)2 1-х 2 7

12 (1 + х (1-х)2 1-х3

з£(-1)*х* +22> + 1)-k*+(7-x+3x2>I>3* К£****

V /с=0 к=0 к=0 J jUQ

где и„ - число решений уравнения 2р + 3 q = п.

Сравнивая коэффициенты при одинаковых степенях , получим:

3-(-1)3 + 2-(Зл + 1) + 7 2Л + 3 + Н)3

12 4

3-i-V)3 +2-(3n + 2)-l 2n+l-(-l)w

з,1+1 - -4

3-(-1)3 +2+2-(Зл+3)+3 2л + 3 + (-1)3 зп+2---г-2- -4-

где я {0, 1, 2...}.

3.5. Принцип включения и исключения

Пусть S = {S[, s2, -Уз,.-} ~ произвольное множество элементов. £2 = 10)!, (о2, ш3,...} - множество весов, £2() - вес элемента eS. Ри Р2, Рь..., Р„ - свойства элементов или индикаторы свойств элементов.

р( s j 1, если элемент Обладает свойс твом Р. , к [О, если элемент sk не обладает свойством Р(.

W(F)= £ Р, (Sk) ra(.yfc )- сумма весов элементов со свойством Р,.

Sj.eS

W(Pj Р ...Pj ) - сумма весов элементов множества S, которые

обладают каждым из свойств Щ , Щ Щя .

W(m = суммирование выполняется по всем

сочетаниям (Z...) длины тиз п свойств, количество сочетаний равно С™.

Таким образом, в W(m суммируются веса только тех элементов, которые имеют как минимум т свойств. Пусть элемент s обладает к свойствами и к > т, тогда его вес сф) в Щт) войдет СТ раз.

Так, =

= п членов и И\>) ]!ГЩ Ph)=W(PlP2)+W(PlPi)+...+ ЩРп4Р„)

содержит С',; -/;( + 1)/2 членов.

Распространим определение W(m) на т = 0, положив [V (t)) V сф) - сумма весов элементов исходного множества S.

s е г

Данное определение выполнено корректно, так как сумма 0О)должна включать элементы, обладающие нуль свойствами и более. Действительно, любой из элементов множества £удовлетворяет этим условиям. Положим:

Е(т) - сумма весов элементов, обладающих ровно т свойствами; ДО) - сумма весов элементов, которые не имеют ни одного из

указанных свойств.

Теорема. Сумма весов элементов, обладающих точно т свойствами из п свойств Ру, Р2,..., /,.. равна

E(m) = W(m)-ClW(m+\)+...+(~\)n-mC{

или

п-т

Е(т) = £(-1) С+; w(m + ) (3.5.1)

Доказательство. Для доказательства достаточно показать, что вклад веса со (s] произвольного элемента s e S в правую и левую