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

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

2.8. Производящие функции для некоторых схем выбора
Производящая функция для
 
r
n,
- сочетаний с ограниченным числом
повторений. В этом случае для получения производящей функции нельзя воспользоваться произведением биномов вида
t
x
k

1
, то есть формулой








n
k
n
k
k
k
k
t
a
t
x
1 0
1
, поскольку всякий такой бином отражает лишь две возможности: элемент
k
x множества либо не появляется в
r
- сочетании, либо появляется ровно один раз.
Пусть элемент
k
x появляется в
r
- сочетаниях с повторениями
j
,...,
2
,
1
,
0
раз, тогда точно
i
появлениям элемента
k
x будет соответствовать одночлен
i
i
k
t
x
, а по правилу суммы появления элемента
k
x либо 0, либо 1,..., либо
j раз должен соответствовать многочлен
1 3
3 2
2
j
j
k
k
k
k
t
x
t
x
t
x
t
x





Тогда производящая функция будет иметь вид
 









n
k
j
j
k
k
k
t
x
t
x
t
x
t
f
1 2
2 1
(2.8.1)
Если нужно найти лишь число
r
a соответствующих
 
r
n,
- сочетаний, то необходимо положить
1 2
1




j
x
x
x
и
 










l
k
k
k
n
j
t
a
t
t
t
t
f
1 2
1
(2.2.2)
Коэффициенты
k
a будут здесь равны числу сочетаний из n элементов по k с j повторениями.
Пример 1. Рассмотрим сочетания из трех предметов 1, 2, 3; причем 1 и 2 могут встречаться не более двух раз, а 3 - не более одного раза.
Составим производящую функцию по формуле (2.8.1). Она будет равна
 








 
 

1 1
1 1
5 3
2 2
2 1
4 3
2 2
1 3
2 2
1 2
2 2
1 3
3 2
2 3
2 1
2 2
1 3
2 1
2 2
1 2
2 2
3 2
3 1
2 1
2 1
3 2
1 3
2 2
2 2
2 2
1 1
t
x
x
x
t
x
x
x
x
x
x
x
x
t
x
x
x
x
x
x
x
x
x
x
x
t
x
x
x
x
x
x
x
x
t
x
x
x
t
x
t
x
t
x
t
x
t
x
t
f

























Если положить
1 3
2 1



x
x
x
, то получим
 
3 5
5 3
1 5
4 3
2
t
t
t
t
t
t
f






Здесь коэффициент
1
a равен числу сочетаний из трех по одному элементу не более чем с двумя повторениями,
2
a - из трех элементов по два не более чем с двумя повторениями,
3
a - из трех по три элемента с ограничениями, что первый и второй элемент могут встречаться не более двух раз, а третий не более одного раза. Если же не приравнивать
1 3
2 1



x
x
x
, то, например, коэффициент при
3
t
равный
3 2
2 3
2 1
2 2
1 3
2 1
2 2
1
x
x
x
x
x
x
x
x
x
x
x




показывает
«качественный» состав
r
- сочетаний с указанными повторениями: 112, 113, 122, 123, 223.

32
Аналогично коэффициент при
5
t
- число
r
- сочетаний из трех элементов по пять, но с повторениями, тогда такое возможно. Именно,
11223
:
3 2
2 2
1 5
x
x
x
a

Производящая функция для
 
r
n,
- сочетаний с неограниченным числом
повторений. Найдем производящую функцию для
 
r
n,
- сочетаний с условием, что хотя бы один элемент каждого вида появится в выборке. Очевидно, что
 
t
f
a
в этом случае будет иметь вид
 




























0 1
1 2
1 1
k
k
k
k
n
n
n
n
n
k
n
k
a
t
C
t
t
t
t
t
t
t
t
t
t
f
(2.8.3)
Упростим полученную формулу, сделав в ней замену индекса суммирования
r
k
n


, получим
 
  





































0 1
1 1
1 1
1 1
1
как так
k
n
r
n
r
n
r
n
k
k
n
k
r
n
r
r
n
r
r
r
r
n
n
r
n
r
n
r
r
k
n
k
k
n
a
t
C
t
C
t
C
C
C
t
C
t
C
t
f
Здесь






1 0
1 1
0
n
k
k
n
k
t
C
Следовательно, число искомых
r
- сочетаний равно нулю при
n
r

и при
1 1
n
r
C
n
r



Подобным же образом в производящей функции можно учесть и другие требования, налагаемые на
 
r
n,
- выборки.
2.9. Применение производящих функций для получения комбинаторных чисел
Применим теорию производящих функций и получим явные выражения чисел
Фибоначчи

. Числа Фибоначчи
n
B есть число способов расположить n знаков, из которых каждый нуль или единица, в последовательность, не содержащую двух нулей подряд. Эта последовательность задается рекуррентной формулой










2
,
,
2
,
1 2
1 1
0
n
B
B
B
B
B
n
n
n
(2.9.1)
Рассмотрим производящую функцию последовательности чисел Фибоначчи
 







0 1
0
,...
,...,
,
k
k
k
k
B
B
B
B
t
B
t
f
Умножим рекуррентное уравнение в формуле (2.9.1) на
k
t
и просуммируем полученное выражение от двух до бесконечности. Два числа
0
B и
1
B известны из начальных данных, поэтому необходимо отбросить индексы
0

k
и
1

k
В результате получим уравнение




























2 2
2 2
2 1
1 2
2 2
2 1
2
или
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
t
B
t
t
B
t
t
B
t
B
t
B
t
B
Так как
 
2 2
1 0
0










k
k
k
k
k
B
t
B
t
B
t
B
B
t
B
t
f
, то
 
 
2 1
1 0
2
t
t
f
t
B
B
t
f
t
B
B
B
k
k
k









 
 


















2 1
0 1
1 1
1
,
2
,
1
k
n
B
B
n
n
k
k
t
f
B
t
f
t
B
n
k
n
k
t
B
Аналогично






2 2
2
k
k
k
t
B
 










0 0
,
2
,
2
n
B
n
n
t
f
t
B
n
k
n
k
Тогда
 
 


 
t
f
t
t
f
t
t
t
f
B
B
B
2 1
2 1





или
 


1 2
1 1
2
t
t
t
t
t
t
f
B







Окончательно производящая функция последовательности чисел Фибоначчи равна
 
1 1
2
t
t
t
t
f
B




(2.9.2)
Так как обычный степенной ряд, представляющий производящую функцию, есть ряд

Леонардо Фибоначчи Пизанский (1180 – 1240) – итальянский математик.

33
Тейлора

в окрестности точки
0

t
, то полученное выражение можно разложить по общему правилу в ряд Тейлора и получить формулу общего члена
k
B При этом выгоднее использовать замены переменных и уже существующие разложения функций в степенные ряды. Поступим именно таким образом. Разложим дробь
2 1
1
t
t


на простые слагаемые, для чего найдем сначала корни знаменателя.
2 5
1
,
2 5
1
,
2 5
1 1
4 1
2 1
,
0 1
2 1
2
,
1 2
















t
t
t
t
t
Тогда



1 1
1 1
1 1
5 1
1 1
1 1
1 1
2 2
1 1
2 1
2 1
2 1
2






































t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
Теперь воспользуемся известным разложением





0 1
1
k
k
t
t
Итак,












0 1
1 1
1
,
1 1
k
k
t
t
t
t
t
t
;












0 2
2 2
1
,
1 1
k
k
t
t
t
t
t
t
. Тогда
























0 0
1 1
1 1
1 1
1 1
1 1
1
k
k
k
k
k
t
t
t
t
t
t
t
t
. Точно таким же образом
























0 0
1 2
2 2
2 2
1 1
1 1
1
k
k
k
k
k
t
t
t
t
t
t
t
t
. Теперь можно записать разложение исходной дроби











































0 1
1 1
2 0
1 1
0 1
2 2
1 1
5 1
1 1
5 1
1 1
k
k
k
k
k
k
k
k
k
k
t
t
t
t
t
t
t
t
t
Умножим полученное выражение на
t

1
, тогда




































0 0
1 1
1 1
2 1
1 1
2 2
1 1
1 1
5 1
1 1
k
k
k
k
k
k
k
k
t
t
t
t
t
t
t
t
t
. Поэтому коэффициент при
k
t
в разложении будет иметь вид
1 1
1 1
5 1
1 2
1 1
1 2
























k
k
k
k
k
t
t
t
t
B
Упростим эту формулу, подставив числовые значения и
2 1
t
t
 

 

 

 

,
2 5
1 5
1 1
2 5
1 2
5 1
1 1
1 1
1 1
1 1
1 1
1 2
1 1
2 1
1 1
1 1
2



























k
k
k
k
k
k
k
k
k
k
k
k
k
t
t
t
t
t
t
аналогично

 

2 5
1 5
1 1
1 1
2
k
k
k
k
k
t
t





Отсюда

 














1 1
1 2
5 1
5 1
5 1
k
k
k
k
B

 


 
 
 





























1 1
2 2
5 1
5 1
2 5
1 5
1 5
1 2
5 1
2 5
1 2
k
k
k
k
k
k





 
 
 




























1 1
2 2
2 2
5 1
5 1
5 1
5 1
5 1
5 3
2 5
2 6
5 5
2 1
5 1
k
k
k

Брук Тейлор (1685 – 1731) – английский математик.

34 2
5 1
2 5
1 5
1 2
2













 






 



k
k
Итак, окончательно
2 5
1 2
5 1
5 1
,
2
,
1 2
2 1
0













 






 





k
k
k
B
B
B
(2.9.3)
2.10. Однородные и неоднородные линейные рекуррентные соотношения
Рассмотрим последовательность
 
,...
2
,
1
,
0
,

n
a
n
. Последовательность
 
n
a
называется возвратной, если для некоторого k и всех n выполняется соотношение вида
0 2
2 1
1










n
k
k
n
k
n
k
n
a
p
a
p
a
p
a
, (2.10.1) где постоянные коэффициенты
k
i
p
i
,...,
2
,
1
,

не зависят от n . Многочлен
 
k
k
k
p
t
p
t
t
P





1 1
(2.10.2) называется характеристическим многочленом для возвратной последовательности
 
n
a
Перепишем (2.10.1) следующим образом
k
i
p
c
a
c
a
c
a
c
a
i
i
n
k
k
n
k
n
k
n
,
1
,
,
2 2
1 1












(2.10.3)
Выражение (2.20.3) позволяет вычислять очередной член последовательности по предыдущим k членам. Если задать начальные значения
1 1
0
,...,
,

k
a
a
a
, то можно определить все другие члены последовательности. Соотношение (2.10.3) часто называют однородным линейным рекуррентным соотношением.
Найдем формулу общего члена
n
a из уравнения (2.10.3). Для этого достаточно найти производящую функцию последовательности
 
n
a
- функцию
 




0
k
k
k
a
t
a
t
f
. Введем вспомогательный многочлен
 
k
k
t
c
t
c
t
c
t
L





1 2
2 1
и рассмотрим произведение
   
 
t
C
t
L
t
f
a


. Так как
   
















k
k
n
n
k
k
a
t
c
t
c
t
c
t
a
t
a
t
a
a
t
L
t
f
1 2
2 1
1 0

 























1 1
0 2
2 1
1 2
0 2
1 1
2 0
1 1
0
n
n
k
k
k
k
k
a
c
a
t
a
c
a
c
a
c
a
t
a
c
a
c
a
t
a
c
a
a

2 2






n
k
n
k
n
t
a
a
a
c
, то видно, что степень
 
t
C
не превышает
1

k
, так как коэффициенты при
,...
1
,
0
,


k
t
k
n
будут равны нулю в силу уравнения (2.10.3).
Пусть характеристическое уравнение (2.10.2) имеет простые (может быть кратные) корни, т. е. допускает разложение вида
  
 
 

k
t
t
t
t
t
t
t
P
k
k
k








α
α
α
,
2 1
α
α
2
α
1 2
1
Тогда
 
t
L
t
c
t
c
t
p
t
p
t
p
t
t
t
P
k
k
k
k
k
k
k
k







































1 1
1 1
1 1
1 1
1
Отсюда
 

 
 

k
t
t
t
t
t
t
t
t
t
t
t
t
t
t
L
k
k
k
k
k
k













 





 





 

α
α
α
,
1 1
1 1
1 1
2 1
α
α
2
α
1
α
α
2
α
1 2
1 1
2 1
и характеристическую функцию можно представить в виде
 
 
 








k
i
n
n
i
i,n
a
i
t
t
t
L
t
C
t
f
1
α
1 1
β
. (2.10.4)
Так как по формуле (2.7.5)
 







0 1
1 1
k
k
k
k
n
n
t
C
t
, то









0 1
β
1 1
k
k
k
i
k
k
n
n
i
t
t
C
t
t
, и, следовательно,
 
 
 
 








k
i
n
j
j
j
i
j
j
n
n
i
a
i
t
t
C
t
L
t
C
t
f
1
α
1 0
1
,
β
. (2.10.5)

35
Формула (2.10.5) дает разложение производящей функции последовательности
 
n
a
Для нахождения формулы общего члена
n
a необходимо найти коэффициент при
n
t
в разложении (2.10.5).