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

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

2.6. Метод рекуррентных соотношений
В комбинаторном анализе существует целый ряд подходов для изучения комбинаторных объектов и чисел.
1)
Теоретико - множественный подход. Он связан с вычислениями мощностей конечных множеств. Для решения таких вопросов необходима дополнительная информация, т. е. надо заранее знать мощности некоторых подмножеств. К этому пункту относится, например, теорема и формула включения и исключения.
2)
Алгебраический
подход. Он основан на использовании вспомогательных просто получаемых комбинаторных тождеств для нахождения интересующих исследователя комбинаторных чисел. Пример - метод рекуррентных соотношений.
3)
Применение формул обращения. Формулы обращения связывают между собой различные комбинаторные числа. Эти формулы могут быть получены самыми различными способами.
4)
Метод производящих функций. Этот метод используется для перечисления комбинаторных чисел и установления комбинаторных тождеств.
Рассмотрим один пример алгебраического подхода - метод рекуррентных соотношений. Он состоит в том, что решение комбинаторной задачи с n предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным (recurrence - возвращение).
Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для

27 небольшого количества предметов (одного, двух) решение задачи обычно очевидно или легко находится.
В качестве примера получим число сочетаний из n по
r
с повторениями.
Соответствующая формула уже получена ранее, она имеет вид
ˆ
1
r
r
n
r
n
C
C



Получим ее теперь методом рекуррентных соотношений.
Докажем вначале вспомогательную формулу, выражающую одно из многочисленных свойств биномиальных коэффициентов:
1 1
1 3
1 2
1 1













r
r
r
n
r
n
r
n
r
n
C
C
C
C
C
(2.6.1)
Покажем, что справедливо равенство
1 1
1





r
n
r
n
r
n
C
C
C
Здесь
r
n
C
- общее число
 
r
n,
- выборок из множества
n
S с n элементами,
r
n
C
1

- число


r
n
,
1

- выборок, т. е. число выборок, не со- первый элемент держащих один (например, первый) элемент из множества
n
S с n элементами (см. рис. 2.2). В этом случае n - множество
n
S становится
1

n
- множе-
n - множество
r
- мно- ством, так как первый элемент не выбирается, он
n
S жество фиксирован.
1 1


r
n
C
- число
r
- выборок из n - множес- тва, содержащих первый элемент. Этот элемент в
r
множестве содержится всякий раз, т. е. фактически первый элемент выбираются из
1

r
элементов, кроме того первый элемент опять фиксирован и в множестве
n
S , как в
n - множество
r
- мно- предыдущем случае, и он не выбирается из n - мно-
n
S жество жемтва, которое становится
1

n
- множеством.
По правилу суммы
1 1
1





r
n
r
n
r
n
C
C
C
Приме- ним эту формулу последовательно
r
n

раз. Полу-
Рис. 2.2. чим
1 1
1





r
n
r
n
r
n
C
C
C
,
1 2
2 1






r
n
r
n
r
n
C
C
C
,
1 3
3 2






r
n
r
n
r
n
C
C
C
,...,
1 1




r
r
r
r
r
r
C
C
C
Но
1 1
1




r
r
r
r
C
C
, тогда окончательно
1 1
1 1
3 1
2 1
1















r
r
r
r
r
n
r
n
r
n
r
n
C
C
C
C
C
C
Вернемся к доказательству исходного соотношения
ˆ
1
r
r
n
r
n
C
C



Зададим начальные условия. Для этого рассмотрим число сочетаний с повторениями для малых значений индексов. Очевидно, что
n
C
n

1
ˆ
и
1
ˆ
1

r
C
Действительно,
1
ˆ
n
C - число 1 - сочетаний из
n элементов. Ясно, что из n элементов можно выбрать ровно n различных выборок, состоящих из одного элемента.
r
C
1
ˆ
- число
r
- сочетаний из одного элемента. Для любого
0

r
из одного элемента можно получить только одно
r
- сочетание, именно выборку, составленную из
r
одинаковых элементов. Элементы здесь могут быть одинаковыми, так как рассматриваются выборки с повторениями.
Для вывода общей формулы нам потребуется еще одно вспомогательное соотношение
ˆ
ˆ
ˆ
1 1




r
n
r
n
r
n
C
C
C
Иллюстрацией дальнейших рассуждений служит тот же рисунок 2.2, изображенный выше. Зафиксируем в
n
S некоторый элемент. Тогда при выборе каждое
r
- сочетание либо содержит этот элемент, либо не содержит его. Если
r
- сочетание не содержит этот элемент, то он не должен вообще попасть в
r
- сочетание, следовательно, его надо исключить из множества
n
S
, т. е. в
n
S остаются для выбора
1

n
элементов. Отсюда число
r
- сочетаний с повторениями из
1

n
элементов равно
ˆ
1
r
n
C

Если
r
- сочетание уже содержит этот элемент, тогда остальные
1

r
элементов этого сочетания можно выбрать из тех же n элементов множества
n
S
, так как допускаются любые повторения. Число способов такого выбора равно
ˆ
1

r
n
C

28
По правилу суммы
ˆ
ˆ
ˆ
1 1




r
n
r
n
r
n
C
C
C
Применим теперь эту формулу для получения доказываемого исходного соотношения
ˆ
1
r
r
n
r
n
C
C



Именно
1 2
2 1
2 2
1 2
2 3
2 2
1 1
2 2
2 1
1 2
1 2
ˆ
ˆ
ˆ
,...,
ˆ
ˆ
ˆ
,
ˆ
ˆ
ˆ
,
ˆ
ˆ
ˆ
C
C
C
C
C
C
C
C
C
C
C
C
n
n
n
n
n
n
n
n
n















Отсюда получим

 



2 1
1 2
2 1
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
2 1
1
,
2 1
1 2
1 2
1 1
1 2





















n
d
прогрессия
ская
арифметиче
n
n
n
n
C
n
n
n
n
n
C
C
C
C
C
C













Аналогично

















3 1
3 2
2 3
3 2
3 3
2 2
3 3
3 2
2 1
3 2
3 1
2 3
1 3
ˆ
ˆ
,
ˆ
ˆ
ˆ
,...,
ˆ
ˆ
ˆ
,
ˆ
ˆ
ˆ
,
ˆ
ˆ
ˆ
C
C
C
C
C
C
C
C
C
C
C
C
C
C
n
n
n
n
n
n
n
n
n
2 2
ˆ
C

. Отсюда можно получить формулу для
3
ˆ
n
C . Выполним аналогичные подстановки как в предыдущем случае, получим
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
3 1
2 2
2 2
2 1
2 3
C
C
C
C
C
C
n
n
n
n








В данном случае лучше не суммировать отрезок числового ряда, а воспользоваться только что полученной формулой для предыдущего индекса
ˆ
2 1
2


n
n
C
C
Тогда
ˆ
2 1
2 2
1 3






n
n
n
n
C
C
C
C
,
2 2
2 3
C
C


так как
2 2
3 1
1
ˆ
С
С


. Но
3 2
2 2
2 3
2 2
1







n
n
n
C
C
C
С
С
по выведенной формуле (2.6.1). Таким образом, получена очередная формула
3 2
3
ˆ


n
n
C
C
. Формулы для последующих индексов получаются совершенно аналогично. Видно, что доказательства с помощью рекуррентных соотношений весьма громоздкое и утомительное занятие.
2.7. Метод производящих функций
Этот метод не является элементарным, так как при его использовании приходится иметь дело с некоторыми понятиями теории функциональных рядов. Метод производящих функций является одним из самых развитых теоретических методов комбинаторного анализа и одним из самых сильных в приложениях. Главные идеи этого метода были высказаны в конце восемнадцатого века в работах Лапласа

по теории вероятностей. Для случаев с конечным числом исходов аппарат теории вероятностей чисто комбинаторный.
Рассмотрим произведение конечного числа линейных биномов








n
k
n
k
k
k
k
t
a
t
x
1 0
1
Коэффициенты
k
a в правой части равенства имеют вид
,
1
,...,
,
2 1
2 1
2 1









n
i
i
i
i
i
i
i
i
i
k
k
k
k
x
x
x
a
Это легко проверить, например, для случая малых
n .
Пусть
2

n
Тогда





1 1
1 2
1 2
1 1
1 2
2 1
,
2
,
1 2
2 1
1
нет как так нет,
,
1 2
нет
,
1 1
2 1



i
i
i
i
i
i
i
i
i
t
x
x
t
x
t
x
t
x
t
x












Для
2

n
проверяется аналогично. В частном случае, когда
n
k
x
k
,
1
,
1


в качестве коэффициентов
k
a получим числа k - сочетаний, т. е.






n
k
k
k
n
n
t
C
t
0 1
(2.7.1)
В выражении (2.7.1) функция
  

n
t
t
f


1
и числа
k
n
C
связаны взаимно однозначно.
Функцию
  

n
t
t
f


1
есть производящая функция последовательности
k
n
C
. Производящей функцией последовательности
 
k
a
называется сумма степенного ряда
 



n
k
k
k
a
t
a
t
f
0
Оперировать с такой функцией гораздо удобнее и проще, особенно когда ее можно представить в простой аналитической форме. В то же время эти операции доставляют
(производят) необходимую информацию о последовательности
r
- сочетаний. Идея применения метода производящих функций такова: необходимо вычислить все члены

Пьер Симон Лаплас (1749 - 1827) - французский математик, механик и астроном.

29 некоторой последовательности
 
k
a
. С помощью рекуррентного соотношения для
k
a или непосредственно из некоторых комбинаторных соображений вычисляют производящую функцию
 



n
k
k
k
a
t
a
t
f
0
Раскладывая затем
 
t
f
a
в ряд и находя коэффициенты при
k
t
, тем самым находят
k
a .
Пример 1. Из формулы бинома Ньютона
  






n
k
k
k
n
n
a
t
C
t
t
f
0 1
Таким образом, последовательность биномиальных коэффициентов имеет производящую функцию


n
t

1
, т. е.




1
,...,
,
,
2 1
0
n
n
n
n
n
n
t
C
C
C
C


(2.7.2)
Пример 2. Пусть
,...
1
,
0
,


k
a
a
k
k
Тогда













k
k
k
k
k
k
k
k
t
a
t
a
at
t
a
t
a
0 0
2 2
1
   
 
1 2







k
at
at
at
. Это бесконечно убывающая геометрическая прогрессия со знаменателем
at
q

Если
1


at
q
, то ряд сходится и его сумма
 
1 1
at
t
f
S
a



Итак,


1
при
1 1
,...
,...,
,
,
,
1 3
2



at
at
a
a
a
a
k
(2.7.3)
Пример 3. Рассмотрим формулу бинома Ньютона при действительном показателе
R


 




 

!
1
α
2
α
1
α
α
!
2 1
α
α
α
1 1
2
α












k
t
k
k
t
t
t
. Пусть
1
α
и




t
t
, тогда
...,
1 1
1 2







k
t
t
t
t
т. е.


1 1
,...
1
,...,
1
,
1
,
1
t


(2.7.4)
Если
,
α
и
n
t
t




то





 

!
1 1
!
2 1
1 1
1











k
n
t
k
k
n
n
n
t
n
n
nt
t
. Но



 

k
k
n
n
n
C
k
k
n
n
n
C
n
n
C
n
1 2
1 1
!
1 1
,
2 1
,










и так далее.
Тогда


1 1
1 1
3 3
2 2
2 1
1











k
k
k
n
n
n
n
n
t
C
t
C
t
C
t
C
t
, т. е.




1 1
,...
,...,
,
,
,
1 1
3 2
2 1
1
n
k
k
n
n
n
n
t
C
C
C
C






(2.7.5)
Пример 4. Пусть







,
,
0
,
0
r
k
C
r
k
a
r
k
k
Тогда
 


1 1



r
r
a
t
t
t
f
Действительно,
 



































0 0
0
,
0
,
,
k
r
k
r
k
i
i
i
i
r
r
i
r
r
k
k
r
k
i
r
i
r
r
i
r
r
i
r
k
r
k
k
k
k
k
a
C
C
C
C
t
C
t
t
C
i
r
k
i
r
k
t
C
t
a
t
a
t
f





























0 1
0 1
0 1
1 1
1
,
1 1
i
r
r
i
r
i
i
i
r
k
n
k
k
k
n
i
i
i
r
r
t
t
t
t
C
t
t
C
t
C
t
Итак, для такой числовой последовательности получена производящая функция.
В комбинаторном анализе чаще всего используют три вида производящих функций:
1) обычные степенные; 2) экспоненциальные; 3) функции Дирихле

. Обычные производящие функции, несколько примеров которых только что разобрано, представляемые в виде

Петер Густав Дирихле (1805 – 1859) – немецкий математик.

30
 



n
k
k
k
a
t
a
t
f
0
, соответствуют семействам последовательностей, элементы которых являются числами неупорядоченных
 
k
n,
- выборок или функциями от них.
Введем несколько операций в классе производящих функций:
 


t
f
a
- класс обычных производящих функций
 



n
k
k
k
a
t
a
t
f
0
Суммой последовательностей
  
   

,...
,
и
,...
,
1 0
1 0
b
b
b
a
a
a


называется последовательность
  
 
 

,...
,
,...
,
1 0
1 1
0 0
c
c
b
a
b
a
b
a
c






, а суммой производящих функций
 



n
k
k
k
a
t
a
t
f
0
и
 



n
k
k
k
b
t
b
t
f
0
производящую функцию
 
 
 






0
k
k
k
b
a
c
t
c
t
f
t
f
t
f
(2.7.6)
Произведением (или сверткой) последовательностей
   
b
a
и называется последовательность
  
 

,...
,
1 0
d
d
b
a
d



, у которой
,...
2
,
1
,
0
,
0 2
2 1
1 0








r
b
a
b
a
b
a
b
a
d
r
r
r
r
r
, (2.7.7) а произведением (сверткой) производящих функций
 
t
f
a
и
 
t
f
b
- производящую функцию
 
 
 






0
k
k
k
b
a
d
t
d
t
f
t
f
t
f
(2.7.8)
Формулы (2.7.7) нуждаются в пояснении. Эти коэффициенты получаются при перемножении рядов следующим образом


























,
,
,
,
2
,
,
1
,
,
0 0
1 1
1 1
0 0
2 1
1 2
0 2
0 1
1 0
1 0
0 0
b
a
b
a
b
a
b
a
d
k
r
b
a
b
a
b
a
d
r
b
a
b
a
d
r
b
a
d
r
k
k
k
k
k
(2.7.9)
Нуль в классе производящих функций
 


t
f
a
это
 
0 0

t
f
; ей соответствует нулевая последовательность


,...
0
,...,
0
,
0
,
0
Единица в классе производящих функций
 


t
f
a
это
 
1

t
f
e
; ей соответствует единичная последовательность


e

,...
0
,...,
0
,
0
,
1
Обратный относительно сложения (противоположный) элемент в классе производящих функций есть следующая функция
 
 










0
k
k
k
a
a
t
a
t
f
t
f
Этой функции соответствует последовательность


,...
,...,
,
1 0
k
a
a
a



Обратный элемент относительно умножения в классе производящих функций есть функция
 





0 1
,

k
k
k
a
t
a
t
f
ей соответствует последовательность
  

,
,...

,


1 0
a
a
a

причем
0
,




a
e
a
a
Так как
0
,




a
e
a
a
, то, учитывая формулы (2.7.9), получим систему

31






















,
0




,
0



,
0


,
1

0 2
2 1
1 0
2 0
1 1
0 2
1 0
0 1
0 0
k
k
k
k
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
Неизвестные здесь
,...

,...,

,

1 0
k
a
a
a
, количество неизвестных равно количеству уравнений.
Умножение производящей функции на действительное число

определяется по формуле
 







0
α
α
k
k
k
a
t
a
t
f
(2.7.10)