ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5273
Скачиваний: 10
21
Такие функции соответствуют семействам последовательно-
стей, элементами которых являются (
n
r
) неупорядоченных r-
выборок или функции от них. Например, функция f(t) = (1 + t)
n
однозначно связана с последовательностью чисел {(
n
r
)}; r =
=0,1,2,...,n в выражении
(1 + t)
n
=
∑
=
n
r 0
(
n
r
) t
r
. (*)
Итак, пусть имеется множество последовательностей
{а}={(а
0
,а
1
,...,а
n
)} и множество соответствующих им производя-
щих функций
{F
a
(t)}, F
a
(t) =
∑
∞
=0
r
a
r
t
r
.
Суммой последовательностей а = (а
0
,а
1
,...) и b = (b
0
,b
1
,...) на-
зовем последовательность
с = а + b = {а
0
+ b
0
, а
1
+ b
1
,...}={с
0
,с
1
,...};
а суммой производящих функций вида (*)
− производящую функ-
цию
F
c
(t)=F
a
(t) + F
b
(t);
F
c
(t)=
∑
∞
=0
r
c
r
t
r
;
где c
r
= a
r
+ b
r
.
Произведением (или сверткой последовательностей а и b
назовем последовательность а
×b = d = (d
0
,d
1
,..., у которой
d
r
= a
0
b
r
+ a
1
b
r–1
+... + a
r
b
0
; r =0,1,...,
а произведением (сверткой) производящих функций F
а
(t) и F
в
(t)
вида (*) – производящую функцию
F
d
(t) = F
a
(t) * F
b
(t) =
∑
=0
r
d
r
t
r
.
Для последовательности 0 = (0,0,...), F
0
(t) = 0.
Последовательности e = (1,0,0,...) соответствует производя-
щая функция F
e
(t)=1.
Вид производящей функции зависит от вида последователь-
ности рассматриваемого класса r-сочетаний. Зная число членов
последовательности и их кратность, выписывают степенной ряд
∑
=
n
r 0
a
r
t
r
.
22
и стараются найти его сумму в наиболее компактной форме.
Пример 1.3.1. Найти производящую функцию для r-сочета-
ний с ограниченным числом повторений из n элементов.
Вначале получим производящую функцию для конечной по-
следовательности чисел C
n
0
,C
n
1
,..., C
n
n
. Запишем выражение
(а + х)
n
в виде (а + х)
n
= (а + х)(а + х)... (а + х) и раскроем скобки
в правой части равенства. Например:
(а + х)
2
= аа + ах + ха + хх;
(а + х)
3
= ааа + аах + аха + ахх + хаа + хах + хха + ххх =
= ааа + 3аах + 3ахх + ххх.
Из этой записи видно, что в нее входят все неупорядоченные
выборки с повторениями, составленные из букв х и а, в количест-
ве равном значению показателя степени. Этот же вывод справед-
лив и для общего случая.
Приведем теперь подобные члены. Подобными будут члены,
содержащие одинаковое количество букв х (следовательно, и
букв а). Далее, найдем, сколько будет членов, в которые входят к
буква х и, следовательно, n-к буква а. Эти члены являются пере-
становками с повторениями, составленными из к букв х и n –к
букв а. Перестановки элементов х могут осуществляться к! спо-
собами, а элементов а (n–к)! способами. Учитывая, что эти пере-
становки могут осуществляться независимо друг от друга и в то
же время будут одинаковы, можно сказать, что множество всех
перестановок n! распадается на части, состоящие из к!
×(n–к)!
одинаковых перестановок каждая. Значит, число различных пере-
становок с повторениями из к букв х и n–к букв а определится по
формуле
k
n
C
k)!
k!*(n
n!
k)
P(k,n
=
−
=
−
.
Отсюда вытекает, что после приведения подобных членов
выражение х
к
а
n–к
войдет с коэффициентом С
n
к
. Итак, мы пока-
зали,что
(а + х)
n
= c
n
0
a
n
x
0
+ c
1
n
a
n–1
x +... + c
n
.
Это равенство принято называть биномом Ньютона.
Если принять в этом равенстве а = 1, то получим:
23
(1 + х)
n
= c
n
0
+ c
1
n
x +... + c
n
k
α
k
+... + c
n
n
x
n
=
∑
=
n
r 0
(
n
k
)
α
k
.
Мы видим, что (1 + х)
n
является производящей функцией
для чисел с
n
k
, k=0,1,...,n.
С помощью этой производящей функции можно легко дока-
зать многие свойства чисел с
n
k
.
А теперь вернемся к рассматриваемому примеру. Произво-
дящую функцию для r-сочетаний с ограниченным числом повто-
рений можно построить из следующего соотношения.
∏
=
n
r 1
(1 + x
r
t) =
∑
=
n
r 0
a
r
t
r
, например,
(1 +x
1
t)(1 + x
2
t)(1 +x
3
t) = 1 + (x
1
+ x
2
+ x
3
)t + (x
1
x
2
+ x
2
x
3
+ x
1
x
3
)t
2
+
+ x
1
x
2
x
3
t
3
=
∑
=
3
0
r
a
r
t
r
. a
r
=
∑
<
<
<
=
n
ir
i
i
ir
i
i
...
2
1
1
,...
2
,
1
x
i1
,x
i2
,...,x
ir
.
В частном случае, когда х
1
= 1, i = 1,2,...,n, в качестве коэф-
фициентов с
r
получили числа r-сочетаний
(1 + t)
n
=
∑
=
n
r 0
(
n
r
)t
r
. (1.3.1)
Пусть элемент х
к
появляется в r-сочетаниях с повторениями
0,1,2,...,j раз, тогда i появлениям элемента х
к
соответствует одно-
член х
i
k
t
i
, а по обобщенному правилу суммы появлениям элемен-
та х
к
либо 0, либо 1,... j раз соответствует полином
1 + х
k
t + x
2
k
t
2
+... + x
j
k
t
j
;
и, значит, производящая функция в этом случае имеет вид:
F(t) =
∏
=
n
k 1
(1 + x
k
t + x
2
k
t
2
+... + x
j
k
t
j
).
Если в этой задаче существенным является не вид произво-
дящей функции, а число а
r
соответствующих r-сочетаний, то при-
нимаем х
1
= х
2
= ... = х
n
=1 и представляем производящую функ-
цию
(1 + t + t
2
+... + t
j
)
n
в виде ряда
∑
=
n
r 1
a
r
t
r
.
Пример 1.3.2. Найти производящую функцию для r-
сочетаний с неограниченным числом повторений из n элементов.
24
Эту функцию можно построить, воспользовавшись резуль-
татами предыдущего примера при j =0,1,2,....,
f(t) = (1 + t + t
2
+...)
n
= (1 – t)
–n
=
∑
=0
r
(
n+r–1
r
)(–t)
r
=
∑
=0
r
(((–n)(–n–1)...(–n–r+1))/r!)*(–1)
r
t
r
;
∑
=0
r
(
n+r–1
r
)t
r
,
(1.3.2)
откуда имеем последовательность а = (а
0
,а
1
,...), а
r
=(
n+r–1
r
)
;
r = 0,
1,... чисел r-сочетаний с повторениями из n-элементов. Этот ре-
зультат согласуется с полученным ранее.
1.3.1 Экспоненциальная производящая функция
Экспоненциальные производящие функции соответствуют
упорядоченным r-выборкам или r-перестановкам. Из определения
упорядоченных и неупорядоченных r-выборок ясно, что первых в
r! раз меньше, чем вторых. Поэтому формулу
(1.3.1) можно запи-
сать в виде
(1 + t)
n
=
∑
=
n
r 0
Р(n,r) t
2
/ r!, (1.3.1.1)
где Р(n,r) – число r-перестановок из n элементов. Это и есть про-
изводящая функция для числа r-перестановок.
В случаях, когда допускаются повторения элементов, необ-
ходимо в левой части формулы (1.3.1.1) биномы (1 +t) заменить
на соответствующие полиномы вида
...;
!
3
!
2
!
1
1
3
2
t
t
t
+
+
+
если никакие ограничения на повторные появления элементов не
наложены, или на полиномы вида
;
!
...
!
!
2
2
1
1
e
ke
k
k
k
t
k
t
k
t
+
+
+
если
соответствующий
элемент
допускает
k
1
,k
2
,..., k
е
повторений
в
выборках
.
Представление
этого
произведения
в
виде
ряда
по
степеням
t
дает
в
качестве
коэффициентов
при
t
r
/r!
числа
r-
перестановок
,
допускающих
указанные
выше
повторения
.
25
Производящие
функции
для
упорядоченных
выборок
называ
-
ют
экспоненциальными
потому
,
что
производящая
функция
для
r-
перестановок
с
неограниченным
числом
повторений
из
n
элемен
-
тов
имеет
вид
степени
ряда
для
экспоненциальной
функции
е
t
:
;
!
...
!
2
!
1
1
2
r
t
n
e
t
t
r
o
r
r
nt
n
∑
∞
=
=
=
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
+
+
+
что
позволяет
записать
ее
весьма
компактно
.
В
частности
,
если
наложить
дополнительные
условия
,
что
каждый
элемент
должен
появиться
хотя
бы
один
раз
,
то
производящая
функция
будет
:
n
t
n
e
t
t
)
1
(
...
!
2
!
1
2
−
=
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
+
+
.
Частые
повторения
одних
и
тех
же
вычислительных
ситуа
-
ций
,
выражений
и
величин
приводят
к
появлению
специальных
чисел
.
Их
часто
открывают
и
переоткрывают
в
разных
частях
ма
-
тематики
.
Чтобы
избежать
ненужных
переоткрытий
,
значения
специальных
чисел
табулируют
.
Приведем
некоторые
сведения
об
этих
числах
.
Числа Стирлинга.
Их
получают
из
хорошо
известного
ком
-
бинаторного
выражения
следующим
образом
:
(t)
n
= t(t – 1)... (t – n + 1) =
∑
=
n
k 0
s(n,k)t
k
, n>0.
Коэффициенты
s(n,k)
называются
числами Стирлинга
1-
го
рода
.
Обратные
им
числа
S(n,k),
определяемые
из
соотношения
:
t
n
=
∑
=
n
k 0
s(n,k) (t)
n
, n>0,
называются
числами Стирлинга
2-
го
рода
.
Принимается
,
что
(t) = t
0
= s(0,0) = 1.
Функции
(t)
n
и
t
n
являются
производящими
для
чисел
Стирлинга
соответственно
1-
го
и
2-
го
рода
.
Числа Фибоначчи.
Числа
f(n)
называют
числами
Фибонач
-
чи
,
если
f(0) = f(1) = 1;
f(n) = f(n–1) + f(n–2) , n
≥ 2.