Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200

• Название: Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
• Анкор: Дискретная Математика
• Дата: 15.09.2022
• Размер: 6.37 Mb.
• Имя файла: S_D_Shaporev_-_Diskretnaya_matematika_-_2004.pdf
• Тип: Учебное пособие; #679116
• страница: 8 из 26

Пример 1. Найти общий член последовательности
 
n
a
, удовлетворяющей рекуррентному соотношению
1
,
2
,
0 3
4 1
0 1
2







a
a
a
a
a
n
n
n
Перепишем исходное рекуррентное соотношение в виде
(2.10.3)
,...
2
,
1
,
0
,
3 4
1 1





n
a
a
a
n
n
n
Характеристический многочлен
 
t
L
имеет вид
 
2 3
4 1
t
t
t
L



Найдем
 
t
C
 
   















2 0
1 2
1 0
1 0
3 4
4 4
t
a
t
a
t
a
t
a
t
a
t
a
a
t
L
t
f
t
C
n
n
n
n
a


t
t
a
a
a
t
a
t
a
n
n
7 2
4 3
3 0
1 0
2 3
1










, так как
2 0

a
и
1 1

a
Тогда
 
 
   

t
B
t
A
t
t
t
t
L
t
C
t
f
a
3 1
1 3
1 1
7 2









Методом неопределенных коэффициентов получим

 



















5 0
,
5 2
7 3
,
2 7
2 3
B
A
B
A
B
A
t
B
A
B
A
 




















0 0
0 3
5 0
5 2
3 5
0 5
2 3
1 5
0 1
5 2
k
k
k
k
k
k
k
k
a
t
t
t
t
t
t
f
. Отметим, что этот пример может быть решен методом, изложенным в подразд. 2.9. Действительно, если
0 3
4 1
2





n
n
n
a
a
a
, то
















0 0
0 1
1 2
2 2
0 3
4 1
n
n
n
n
n
n
n
n
n
t
a
t
a
t
t
a
t
,












2 1
0 2
0 3
4 1
j
j
n
n
n
j
j
j
j
t
a
t
a
t
t
a
t
,
 


 


 
0 3
4 1
0 1
0 2






t
f
a
t
f
t
t
a
a
t
f
t
a
a
a
,
 
 
 
0 3
8 4
2 2






t
f
t
t
t
tf
t
t
f
a
a
a
,
 
 

t
t
t
t
t
t
t
f
a
3 1
1 7
2 3
4 1
7 2
2








, т. е. получен тот же самый результат.
Докажем теперь несколько положений, позволяющих находить общее решение рекуррентных соотношений.
Во-первых, очевидно, что возвратная последовательность (2.10.1) полностью определяется заданием ее первых k членов. Действительно, если
1 1
0
,...,
,

k
a
a
a
уже заданы, то
0 2
2 1
1
a
p
a
p
a
p
a
k
k
k
k







,
1 1
2 1
1
a
p
a
p
a
p
a
k
k
k
k







,…,
n
k
k
n
k
n
n
k
a
p
a
p
a
p
a










2 2
1 1
Во-вторых, если t является корнем характеристического многочлена (2.10.2), то последовательность
 
n
t
удовлетворяет соотношению
(2.10.1), т. е.
0 1
1







n
k
k
n
k
n
ct
p
ct
p
ct
. Но


0 1
1





k
k
k
n
p
t
p
t
ct
, ибо t есть корень многочлена
(2.10.2) и тогда
0 1
1





k
k
k
p
t
p
t
В-третьих, рассмотрим
k
t
t
t
,...,
,
2 1
простые (не кратные) корни характеристического многочлена (2.10.2). Тогда общее решение рекуррентного соотношения (2.10.1) имеет вид
n
k
k
n
n
n
t
c
t
c
t
c
a




2 2
1 1
, (2.10.6) где
k
c
c
c
,...,
,
2 1
- подходящие константы. В самом деле, то, что
n
k
k
n
n
n
t
c
t
c
t
c
a




2 2
1 1
удовлетворяет (2.10.1) следует из того, что
k
i
t
i
,
1
,

является корнем характеристического уравнения и, следовательно, удовлетворяет (2.10.1) и из того, что если последовательности
 
n
a и
 
n
b удовлетворяют (2.10.1), то и последовательность
 
n
n
n
n
b
a
d
d
β
α
,


ему удовлетворяет при любых
α и
β
Кроме того, любая последовательность
 
n
a
, удовлетворяющая (2.10.1) может быть представлена в виде (2.10.6). Эта последовательность полностью определяется своими

36 первыми членами
1 1
0
,...,
,

k
a
a
a
, тогда, если для любых
1 1
0
,...,
,

k
a
a
a
существует единственный набор чисел
k
c
c
c
,...,
,
2 1
таких, что






















,
,
,
1 1
1 2
2 1
1 1
1 2
2 1
1 0
2 1
k
k
k
k
k
k
k
k
k
a
t
c
t
c
t
c
a
t
c
t
c
t
c
a
c
c
c
(2.10.7) то
n
a может быть представлена в виде (2.10.6).
Определитель системы (2.10.7) есть определитель Вандермонда

. Он равен











k
j
i
j
i
k
k
k
k
k
t
t
t
t
t
t
t
t
1 1
1 2
1 1
2 1
1 1
1
и не равен нулю, если
j
i
t
t

при
j
i

, что в нашем случае выполняется. Таким образом, система линейных уравнений (2.10.7) имеет единственное решение относительно
k
c
c
c
,...,
,
2 1
Наконец, в-четвертых, можно показать, что если
i
t есть корень многочлена (2.10.2) кратности
i
α , то общее решение рекуррентного соотношения (2.10.1) имеет вид


n
i
r
i
i
i
i
n
t
n
c
n
c
c
a
i
i







1 1
α
α
,
2
,
1
,
, (2.10.8) где
i
j
i
j
r
i
c
α
,
1
,
,
1
,
,


произвольные константы,
r
- количество кратных корней.
Пример 2. Найдем общее решение для примера 1. Характеристический многочлен
 
3 4
2



t
t
t
P
имеет корни
3
,
1 2
1


t
t
. Тогда по формуле (2.10.6) получаем
n
n
n
n
c
c
t
c
t
c
a
3 2
1 2
2 1
1





Неоднородное линейное рекуррентное соотношение имеет вид
n
n
k
k
n
k
n
k
n
b
a
c
a
c
a
c
a










2 2
1 1
, (2.10.9) где
n
b есть функция от n . Как и в теории линейных дифференциальных уравнений общее решение соотношения (2.10.9) есть сумма любого частного его решения и общего решения уравнения (2.10.1). Общих способов определения частного решения нет, можно решить уравнение (2.10.9) лишь для некоторых специальных значений b .
Способ решения реконструирует производящую функцию последовательности
 
n
a
и похож на способ, изложенный в подразд. 2.9.
Пример
3.
Решить неоднородное рекуррентное соотношение
 
n
n
n
n
a
a
a
1 2
3 1
2






,
2
,
1 1
0


a
a
 


















0 0
0 0
1 2
1 2
3
n
n
n
n
t
n
n
n
n
n
n
n
t
t
a
t
a
t
a
,
 
















2 1
0 0
2 1
2 3
1
j
j
n
n
t
n
n
n
j
j
j
j
t
t
a
t
a
t
t
a
t
 


 


 
t
t
f
a
t
f
t
t
a
a
t
f
t
a
a
a







1 1
2 3
1 0
1 0
2
,
 
 


 
t
t
t
f
t
t
f
t
t
t
f
a
a
a







1 2
1 3
2 1
2 2
,
   


  

5 0
1 1
5 0
1 1
1 2
3 1
1 1
2














t
C
t
B
t
A
t
t
t
t
t
t
t
f
a
,




2 2
2 3
Bt
At
At
A

Александр Теофиль Вандермонд (1735 - 1796) – французский математик.

37























3 2
,
2 1
,
12 1
0 2
,
0 5
0 3
,
1 5
0 1
5 0
5 0
2
C
B
A
C
B
A
B
A
C
B
A
Ct
B
Bt
 
    

 




















0 0
0 2
3 4
2 1
1 12 1
5 0
3 2
1 2
1 1
12 1
n
n
n
n
n
n
n
n
a
t
t
t
t
t
t
t
f
 














0 2
3 2
2 1
1 12 1
n
n
n
n
t . Отсюда
 
12 2
6 1
4





n
n
n
a
2.11. Экспоненциальные производящие функции
Они соответствуют упорядоченным
 
r
n,
- выборкам или
 
r
n,
- перестановкам. Из определения упорядоченных и неупорядоченных
 
r
n,
- выборок ясно, что первых в !
r раз больше чем вторых. Поэтому производящая функция в этом случае записывается в виде


 




n
k
k
n
k
t
k
n
P
t
0
,
!
,
1
(2.11.1) где
 
r
n
P ,
- число
 
k
n,
- перестановок из n элементов, то есть
 
k
n
A
k
n
P

,
в принятых обозначениях.
В случаях, когда допускаются повторения элементов необходимо в левой части формулы (2.11.1) биномы


t

1
заменить на соответствующие многочлены вида
...,
!
3
!
2
!
1 1
3 2




t
t
t
если никакие ограничения на повторные появления не наложены, или многочлены вида




























!
!
1 1
!
!
1 1
!
!
1 1
2 2
2 1
1 1
2 1
l
k
l
l
k
k
k
t
t
k
t
t
k
t
t
l














l
j
j
k
j
j
k
t
t
j
1
!
!
1 1
, если соответствующий элемент допускает
l
k
k
k
,...,
,
2 1
повторений в выборках. Представление этого произведения в виде ряда по степеням t дает в качестве коэффициентов при
!
k
t
k
числа k - перестановок, допускающих указанные выше повторения.
Название экспоненциальная применяется в силу того, что производящая функция для
k - перестановок с неограниченным числом повторений из n элементов имеет вид
 
 



















0 0
2
!
!
!
2
!
1 1
k
k
k
k
k
nt
n
t
n
k
t
n
k
nt
e
e
t
t
(2.11.2)
Так как производящие функции (и простая и экспоненциальная) представляют собой степенной ряд, то в области его сходимости


R
R
,

этот ряд можно почленно дифференцировать и интегрировать и, следовательно, получать новые степенные ряды и новые производящие функции. Например, возьмем
1 1
1 0
2









k
k
t
t
t
t
Почленным интегрированием этого ряда в области
1

t
получаем выражение для производящей функции
 






1
,
1
ln
k
k
k
t
t
(2.11.3) то есть


1
ln
,...
1
,...,
3 1
,
2 1
,
1
t
k










38
2.12. О приложениях теории производящих функций к теории вероятностей
Исторически сложилось так, что прежде всего комбинаторные методы нашли применение в теории вероятностей и математической статистике. В современной аксиоматической теории вероятностей сами вероятности мыслятся лишь в связи с пространствами элементарных событий. Комбинаторные методы находят себе место в теории вероятностей именно в той ее части, когда пространства элементарных событий дискретны. Можно даже говорить о теоретико - вероятностных интерпретациях определенной части комбинаторного анализа.
В самом деле
 
r
n,
- выборки могут быть интерпретированы различными урновыми схемами. Случаи, когда допускаются повторения элементов в выборках, соответствуют урновым схемам с возвращением. Одна из простейших производящих функций в теории вероятностей связана с бросанием монеты и другими событиями с двумя исходами:
1
,



q
p
pt
q
Для n независимых испытаний с двумя исходами (схема Бернулли

) производящей функцией будет
  

1
,




q
p
pt
q
t
f
n
Производящая функция бросания одной шестигранной кости с равновероятными выпадениями очков имеет вид:
 


1 1
6 6
1 6
6 5
4 3
2
t
t
t
t
t
t
t
t
t
t
f










Комбинаторные задачи о размещениях в их теоретико - вероятностной трактовке приводят к введению различных моментов и функций накопления. Это также верно и для теоретико - числовых интерпретаций и для задач технической автоматики.