ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 8775
Скачиваний: 13
26
Отсюда
их
производящая
функция
имеет
вид
F(t) = 1 + t + 2t
2
+ 3t
3
+ 5t
4
+ 8t
5
+ 13t
6
+... +....
1.3.2 Производящие функции и рекуррентные соотношения
Рассмотрим
операцию
деления
многочленов
.
Пусть
f(x) = a
0
+ a
1
x +... + a
n
x
n
и
ϕ(x) = b
0
+ b
1
x +... + b
m
x
m
−
два
многочлена
,
причем
b
0
≠ 0.
Полагаем
также
,
что
n<m,
т
.
е
.,
что
алгебраическая
дробь
f(x)/
ϕ(x)
правильна
.
Мы
знаем
,
что
если
)
(
)
(
x
x
f
ϕ
= c
0
+ c
1
x +... + c
k
x
k
+..., (1.3.2.1)
то
a
0
+ a
1
x +... + a
n
x
n
= (b
0
+ b
1
x +... + b
m
x
m
) (c
0
+ c
1
x +... + c
k
x
k
+...).
Раскроем
в
правой
части
этого
равенства
скобки
и
сравним
коэффициенты
при
одинаковых
степенях
х
слева
и
справа
.
Сначала
мы
получим
m
соотношений
такого
вида
:
b
0
c
0
=a
0
,
b
0
c
1
+ b
1
c
0
= a
1
,
b
0
c
2
+ b
1
c
1
+ b
2
c
0
= a
2
, (1.3.2.2)
...................................
b
0
c
m
+ b
1
c
m–2
+... + b
m–1
c
0
= a
m–1
;
(
если
n<m–1,
то
мы
считаем
,
что
а
n+1
=... =a
m–1
= 0).
А
дальше
все
соотношения
имеют
один
и
тот
же
вид
:
b
0
c
m+k
+ b
1
c
m+k–1
+... + b
m
c
k
= 0 , k = 0,1,.... (1.3.2.3)
(
так
как
в
f(x)
нет
членов
,
содержащих
x
m
, x
m+1
и
т
.
д
.).
Таким
образом
,
коэффициенты
с
0
,
с
1
,...
с
к
,...
ряда
(1.3.2.1)
удовлетворяют
рекуррентному
соотношению
(1.3.2.3).
Коэффициенты
этого
соотношения
зависят
лишь
от
знаме
-
нателя
дроби
.
Числитель
нужен
для
нахождения
первых
членов
с
0
,
с
1
,...,
с
m–1
рекуррентной
последовательности
.
Обратно
,
если
рекуррентное
соотношение
(1.3.2.3)
и
заданы
члены
с
0
,
с
1
,...,
с
m–1,
то
мы
сначала
по
формулам
(1.3.2.2)
вычисля
-
ем
значения
а
0
,...,
а
m–1
.
А
тогда
производящей
функцией
для
по
-
27
следовательности
чисел
с
0
,
с
1
,...,
с
к
,...
является
алгебраическая
дробь
.
...
...
)
(
)
(
1
0
1
1
1
0
m
m
m
m
x
b
x
b
b
x
a
x
a
a
x
x
f
+
+
+
+
+
+
=
−
−
ϕ
(1.3.2.4)
На
первый
взгляд
кажется
,
что
мы
мало
выиграли
при
замене
рекуррентного
соотношения
производящей
функцией
.
Ведь
все
равно
придется
делить
числитель
на
знаменатель
,
а
это
приведет
к
тому
же
самому
рекуррентному
соотношению
(1.3.2.3).
Но
дело
в
том
,
что
над
дробью
можно
выполнять
некоторые
алгебраические
преобразования
,
а
это
облегчает
отыскание
чисел
с
к
.
Рассмотрим
,
как
с
помощью
алгебраических
преобразований
производящих
функций
можно
решать
рекуррентные
соотноше
-
ния
.
Предположим
,
что
знаменатель
дроби
(1.3.2.4)
разложен
на
множители
первой
степени
ϕ(
х
) = b
m
(x –
α
1
)
r
... (x –
α
k
)
s
.
Для
этого
надо
предварительно
решить
уравнение
b
0
+...
+ b
m
x
m
= 0,
т
.
е
.
характеристическое
уравнение
соотношения
(1.3.2.3).
Ясно
,
что
дробь
(1.3.2.4)
получилась
в
результате
приведе
-
ния
к
одному
знаменателю
следующих
элементарных
дробей
:
,
)
(
,...,
)
(
,
)
(
1
1
,
1
1
1
12
1
11
α
α
α
−
−
−
−
−
x
A
x
A
x
A
r
r
r
.
)
(
,...,
)
(
,
)
(
1
,
1
2
1
k
s
k
s
k
k
s
k
k
x
A
x
A
x
A
α
α
α
−
−
−
−
−
Другими
словами
:
...
)
(
...
)
(
...
)
(
)
...(
)
(
...
1
,
1
1
,
1
1
11
1
1
1
0
+
−
+
+
−
+
+
−
=
−
−
−
−
−
−
k
s
k
r
r
s
k
r
m
m
m
x
A
x
A
x
A
x
x
b
x
a
a
α
α
α
α
α
Здесь
нам
неизвестны
коэффициенты
А
11
,...,
А
k,s–1
.
Чтобы
найти
эти
коэффициенты
,
нужно
умножить
обе
части
равенства
на
знаменатель
(x –
α
1
)
r
... (x –
α
k
)
s
,
раскрыть
скобки
и
сравнить
коэффициенты
при
одинаковых
степенях
х
.
Из
полу
-
чившийся
системы
уравнений
мы
и
находим
искомые
коэффици
-
енты
.
Иногда
удается
обойтись
и
без
решений
системы
уравнений
.
Пусть
,
например
,
надо
разложить
дробь
28
4
5
1
6
2
2
4
2
3
+
+
+
+
−
x
x
x
x
x
.
Так
как
х
4
– 5
х
2
+ 4 = (
х
2
– 1)(
х
2
– 4) = (
х
– 1)(
х
+ 1)(
х
+ 2)(
х
– 2),
то
это
разложение
имеет
вид
:
)
2
(
)
2
(
)
1
(
)
1
(
)
2
)(
1
)(
2
)(
1
(
1
6
2
2
3
+
−
−
−
+
−
−
=
−
+
+
−
+
+
−
x
D
x
C
x
B
x
A
x
x
x
x
x
x
x
.
Приводя
к
одному
знаменателю
,
получаем
,
что
х
3
– 2
х
2
+ 6
х
+ 1 =
А
(
х
+ 1)(
х
– 2)(
х
+2) +
В
(
х
– 1)(
х
– 2)(
х
+2) +
С
(
х
– 1)(
х
+ 1)(
х
+ 2) + D(
х
– 1)(
х
– 2)(
х
+ 1).
Это
равенство
должно
выполнятся
при
всех
значениях
х
.
Но
при
х
= 1,
мы
получаем
−6
А
= 6.
Поэтому
А
=
−1.
Точно
так
же
,
полагая
х
=
−1,
х
= 2,
х
=
− 2,
находим
В
=
− 4/3, C = 13/12,
D = 9/4.
Таким
образом
,
)
2
(
4
9
)
2
(
12
13
)
1
(
3
4
)
1
(
1
4
5
1
6
2
2
4
2
3
+
−
−
−
+
−
−
=
+
+
+
+
−
x
x
x
x
x
x
x
x
x
.
Для
дробей
вида
А
/(
х
–
а
)
r
разложение
в
ряд
получается
по
формуле
Ньютона
.
Например
,
⎥
⎦
⎤
⎢
⎣
⎡
+
+
+
+
+
=
⎟
⎠
⎞
⎜
⎝
⎛ +
=
−
−
...
2
...
2
2
1
24
13
2
1
24
13
)
2
(
12
13
2
2
1
n
n
x
x
x
x
x
.
Применяя
такое
разложение
ко
всем
дробям
,
получаем
,
что
.
...
2
)
1
(
...
2
2
1
4
9
...
2
...
2
2
1
24
13
...)
)
1
(
...
1
(
3
4
...)
...
1
(
4
5
1
6
2
2
2
3
2
2
2
2
2
4
2
3
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
+
−
+
−
+
−
+
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
+
+
+
+
+
−
+
−
+
−
+
−
−
+
+
+
+
+
=
+
+
+
+
−
n
n
n
n
n
n
n
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Группируя
члены
с
одинаковыми
степенями
х
,
получаем
,
что
коэффициент
при
х
n
выражается
формулой
n
n
n
n
n
C
2
*
8
)
1
(
9
2
*
24
13
)
1
(
3
4
1
−
+
−
−
−
=
.
Ранее
мы
уже
отметили
,
что
задача
о
разложении
алгебраи
-
ческой
дроби
в
степенной
ряд
равносильна
задаче
о
решении
не
-
которого
рекуррентного
соотношения
при
заданных
начальных
условиях
.
Таким
образом
,
с
помощью
разложения
дробей
на
эле
-
29
ментарные
и
последующего
разложения
полученных
элементар
-
ных
дробей
в
степенные
ряды
можно
решать
линейные
рекур
-
рентные
соотношения
с
построенными
коэффициентами
.
Итак
,
если
задано
рекуррентное
соотношение
(1.3.2.3)
и
зна
-
чения
c
0
,..., c
m–1
,
то
сначала
надо
по
формулам
(1.3.2.2)
найти
зна
-
чение
a
0
,..., a
m–1
.
Они
дают
коэффициенты
многочлена
,
стоящего
в
числителе
дроби
...
...
)
(
)
(
1
0
+
+
+
+
=
k
k
x
c
x
c
c
x
x
f
ϕ
(1.3.2.5)
Знаменатель
этой
дроби
равен
b
0
+... + b
m
x
m
.
Найденную
дробь
)
(
)
(
x
x
f
ϕ
надо
разложить
на
элементарные
дроби
,
после
чего
каждую
элементарную
дробь
разложить
в
степенной
ряд
по
фор
-
муле
Ньютона
.
Коэффициент
при
х
к
в
полученном
ряде
и
дает
значение
с
к
.
В
качестве
примера
решим
рекуррентное
соотношение
с
к+2
−
− 5
с
к+1
+ 6
с
к
= 0
при
начальных
условиях
с
0
=1,
с
1
=
− 2.
Здесь
b
0
= 1, b
1
=
− 5, b
2
= 6.
Из
формулы
(1.3.2.2)
получаем
,
что
а
0
= b
0
c
0
=1; a
1
= b
0
c
1
+
+ b
1
c
0
=
− 7.
Поэтому
числитель
дроби
(1.3.2.5)
равен
1
− 7
х
.
Знаменатель
этой
дроби
получается
из
соотношения
(1.3.2.1).
Он
имеет
вид
х
2
− 5
х
+ 6.
Значит
,
для
отыскания
решения
нам
надо
разложить
в
степенной
ряд
дробь
,
6
5
7
1
2
+
−
−
x
x
x
но
х
2
– 5
х
+6 = (
х
– 2)(
х
– 3)
и
поэтому
)
3
(
)
2
(
6
5
7
1
2
−
+
−
=
+
−
−
x
B
x
A
x
x
x
.
Далее
, 1
− 7
х
=
А
(
х
− 3) +
В
(
х
− 2).
Отсюда
В
=
− 20,
А
= 13.
Значит
,
=
⎟
⎠
⎞
⎜
⎝
⎛ −
+
⎟
⎠
⎞
⎜
⎝
⎛ −
−
=
−
+
−
=
+
−
−
−
−
1
1
2
3
1
3
20
2
1
2
13
)
3
(
20
)
2
(
13
6
5
7
1
x
x
x
x
x
x
x
30
.
...
3
...
3
1
3
20
...
2
...
2
1
2
13
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
+
+
+
+
+
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
+
+
+
+
=
n
n
n
n
x
x
x
x
Поэтому
1
1
3
20
2
13
3
1
3
20
2
1
2
13
+
+
+
=
+
−
=
n
n
n
n
n
C
.
В заключении к разделу производящих функций следует от-
метить, что вид производящих функций зависел и зависит от кон-
кретных условий задач и построение их является делом искусст-
ва. Усложнение комбинаторных проблем и рассматриваемых в
них множеств в течение дополнительного времени не приводило
к открытию регулярного подхода к построению производящих
функций. Существенный шаг в этом направлении был сделан в
1937 году Пойа. Значение его работы состояло в нахождении
производящей функции для неэквивалентных комбинаторных
объектов весьма общего вида. Сложность решаемой задачи со-
стояла в том, что рассматривались элементы, которым были при-
даны веса, а понятие эквивалентности вводилось через группы
перестановок.
1.4
Метод
включения
и
исключения
Данный метод применяется к задаче разделения множеств
на подмножества в зависимости от того, обладают ли их элемен-
ты определенной совокупностью свойств или нет. Метод включе-
ния и исключения применяется широко и известен в различных
модификациях под названиями: метод решета, логический метод,
принцип перекрестной классификации, символический метод.
Пусть дано n-множество S некоторых элементов и N-
множество свойств: р
1
,р
2
,...,р
N,
которыми элементы множества S
могут как обладать, так и не обладать. Выделим какую-либо r-
выборку свойств (p
i1
,p
i2
,..., p
ir
). Число элементов s
∈ S, каждый из
которых обладает всеми r выбранными свойствами, обозначим
через n (p
i1
,p
i2
,..., p
ir
). Отсутствие у элементов какого-либо свойст-
ва, например p
i
, будем обозначать через
i
p . Таким образом, чис-
ло элементов, обладающих, скажем, свойствами р
1
,р
3
,р
5
и не об-
ладающих свойствами р
2
,р
4
,р
6
, запишется как n(p
1
,p
2
,p
3
,p
4
,p
5
,p
6
).
Рассмотрим два простых примера: