Ямненко Р.Є. Дискретна математика
Подождите немного. Документ загружается.
2. Нехай q
0
=1iдляn ≥ 1
q
n
=
n
k=0
(−1)
k−1
C
k
n
T
k
T
n−k
.
Нехай Q(t) – експоненцiйна генератриса послiдовностi {q
n
}. Показати, що
Q(t)=e
e
t
+e
−t
−2
.
3. Довести конгруентнiсть Тучарда: для всiх n, m ∈ N i простого p має
мiсце рiвнiсть
B
n+p
m
≡ mB
n
+ B
n+1
mod p.
Задачi для самостiйної роботи
1. Довести, що числа Бела можна подати у виглядi
T
n
=
k
1
,k
2
,...,k
n
n!
n
j=1
k
j
!(j!)
k
j
,
де сума розглядається по всiх розбиттях числа n таких, що
k
1
+2k
2
+ ...+ nk
n
= n.
2. Показати, що
n
k=0
s(n, k)T
k
=1,n=0, 1, 2,... .
3. Перевiрити, що:
n
k=0
S(n, k)=B
n
,n≥ 0.
4. Довести формулу Добiнського:
B
n
=
1
e
∞
i=0
i
n
i!
.
5. Довести, що коли p – просте число, то
B
n+p
m
≡
n
k=1
(B
p
m
+ k)S(n, k)modp.
80
ЗАНЯТТЯ 14
Числа Бернулi та многочлени Бернулi
Означення 14.1. Многочленами Апеля, породженими послiдовнiстю
{a
n
,n≥ 0}, називають послiдовнiсть многочленiв
A
n
(x)=
n
k=0
C
k
n
a
k
x
n−k
.
Приклад 14.2. Нехай a
n
=1для всiх n.Тодi
A
n
(x)=
n
k=0
C
k
n
x
n−k
=(1+x)
n
.
Означення 14.3. Послiдовнiсть B
n
чисел Бернулi – це послiдовнiсть, експо-
ненцiйна генератриса якої дорiвнює
t
e
t
− 1
=
∞
n=0
B
n
t
n
n!
.
Означення 14.4. Послiдовнiсть многочленiв Апеля, породжена послiдовнi-
стю чисел Бернуллi {B
n
}, називають послiдовнiстю многочленiв Бернуллi.
Таким чином, многочлен Бернуллi степеня n має вигляд
B
n
(x)=
n
k=0
C
k
n
B
k
x
n−k
.
Теорема 14.5. Нехай ϕ(x) функцiя, яка має 2l неперервних похiдних. При
n>mмає мiсце формула Ойлера-Маклорена:
n−1
k=m
ϕ(k)=
+
n
m
ϕ(x)dx −
1
2
[ϕ(n) − ϕ(m)]+
+
l−1
r=1
B
2r
(2r)!
[ϕ
(2r−1)
(n) − ϕ
(2r−1)
(m)] +
+ϕ
(2l)
(m + θ(n − m))(n − m)
B
2l
(2l)!
,
де 0 <θ<1.
81
Задачi для аудиторної роботи
1. Експоненцiйна генeратриса послiдовностi многочленiв Бернуллi
{B
n
(x)} дорiвнює
F (x, t)=
∞
n=0
B
n
(x)
n!
t
n
.
Довести, що
а) F (x, t)=
t
e
t
− 1
e
tx
;
б) при n ≥ 2
B
n
(1) = B
n
(0) = B
n
.
2. Встановити, що при n ≥ 2 має мiсце рекурентне спiввiдношення
B
n
=
n
k=0
C
k
n
B
k
.
3. Довести, що
n 0 1 2 3 4 5 6 7 8 9 10
B
n
1 −
1
2
1
6
0 −
1
30
0
1
42
0 −
1
30
0
5
66
4. Довести, що
B
1
(x)=x −
1
2
;
B
2
(x)=x
2
− x +
1
6
;
B
3
(x)=x
3
−
3
2
x
2
+
1
2
x.
5. Довести, що
B
n
(x)=nx
n−1
(n =0, 1, 2,...).
6. Довести, що:
а)
n
j=1
j
l
=
B
l+1
(n +1)−B
l+1
l +1
;
б)
n
j=1
j =
n(n +1)
2
;
82
в)
n
j=1
j
2
=
n(n + 1)(2n +1)
6
;
г)
n
j=1
j
3
=
n(n +1)
2
2
.
7. Довести, що
B
n
=
n
k=0
(−1)
k
k +1
k
0
n
.
8. Нехай
cth(t)=
e
t
+ e
−t
e
t
− e
−t
.
Перевiрити, що
t cth(t) − t =
2t
e
2t
− 1
=
∞
n=0
B
n
(2t)
n
n!
.
Одержати звiдси розклад
cth(t)=
1
t
+
∞
k=1
B
2k
2
2k
(2k)!
t
2k−1
.
Використовуючи формулу Ойлера
ctg(t)=i
e
it
+ e
−it
e
it
− e
−it
= i cth(it),
встановити, що
ctg(t)=
1
t
+
∞
k=1
B
2k
(−1)
k
2
2k
(2k)!
t
2k−1
.
Додатковi задачi
1. Нехай s>1 i
ζ(s)=
∞
k=1
1
k
s
.
Довести, що ζ(2s) (s – натуральне число) дорiвнює
ζ(2s)=
2
2s−1
π
2s
(−1)
s−1
B
2s
(2s)!
(зокрема ζ(2) =
∞
k=1
1
k
2
=
π
2
6
).
83
2. Довести, що при α>−1:
n
k=1
k
α
=
n
α+1
n +1
1+O
1
n
1+α
.
Задачi для самостiйної роботи
1. Нехай
th(t)=
e
t
− e
−t
e
t
+ e
−t
.
Довести тотожнiсть:
th(t)=2cth(2t) − cth(t)
i встановити, що
th(t)=
∞
k=1
B
2k
(2
2k
− 1)2
2k
(2k)!
t
2k−1
.
Довести, що:
tg(t)=
∞
k=1
B
2k
(2
2k
− 1)2
2k
(−1)
k−1
(2k)!
t
2k−1
.
2. Нехай
csch(t)=
2
e
t
− e
−t
.
Довести, що
csch(t)=−cth(t)+cth
t
2
,
i встановити, що
csch(t)=
1
t
+
∞
k=1
B
2k
2 − 2
2k
(2k)!
t
2k−1
.
3. Нехай
H
n
=
n
k=1
1
k
.
Використовуючи формулу Ойлера-Маклорена, довести, що iснує границя
lim
n→∞
(H
n
− ln n)=C
(число C називають сталою Ойлера; C =0, 577 215 7 ... ).
84
4. Довести, що:
n + B
2n
=
n
k=0
B
2k
C
2k
2n
.
5. Нехай A
n
(x) – це послiдовнiсть многочленiв Апеля, породжена послi-
довнiстю {a
n
}.
а) Довести, що
A
n
(x)=nA
n−1
(x)(n =1, 2,...).
б) Довести, що якщо
F (t)=
∞
n=0
a
n
n!
t
n
,F(t, x)=
∞
n=0
A
n
(x)
n!
t
n
,
то
F (t, x)=e
tx
F (t).
85
ЗАНЯТТЯ 15
Основнi поняття теорiї графiв
Нехай X = {x
1
,x
2
,...,x
n
} – деяка скiнченна множина (множина вер-
шин), M
2
– множина всiх невпорядкованих пар елементiв iз X, M
2
=
{(x
i
,x
j
): x
i
∈ X, x
j
∈ X, i < j}.
Означення 15.1. Граф Γ(X, W) – геометрична конфiгурацiя, яка складає-
ться з множини вершин X i множини ребер W ⊂M
2
.Вершиниx
i
та x
j
графа називають iнцидентними (сумiжними), якщо ребро (x
i
,x
j
) ∈ W .
Приклад 15.2. Нехай X = {1, 2, 3}. Побудуємо всi графи з множиною вер-
шин X.ТодiM
2
= {(1, 2), (1, 3), (2, 3)}. Маємо 8 графiв:
• •
•
1 2
3
• •
•
1 2
3
••
•
21
3
1) W = {(2, 3)} 2) W = {(1, 2)} 3) W = {(1, 3)}
• •
•
1 2
3
• •
•
1 2
3
••
•
21
3
4) W = {(1, 2); (2, 3)} 5) W = {(1, 2); (1, 3)} 6) W = {(2, 3); (2, 3)}
• •
•
1 2
3
••
•
21
3
7) W = ∅
8) W = M
2
= {(1, 2); (1, 3); (2, 3)}
Означення 15.3. Степенем d(x
i
) вершини графа Γ називають число вершин
x
j
, iнцидентних вершинi x
i
.
Приклад 15.4. На наступному рисунку вказано степенi вершин графа.
• •
••
••
3 2
23
31
86
Означення 15.5. Якщо d(x
i
)=1,товершинуx
i
називають кiнцевою верши-
ною графа Γ, якщо d(x
i
)=0,товершинуx
i
називають iзольованою. У разi,
коли всi вершини мають однаковий степiнь, граф називають регулярним.
Нехай a
ij
=
1, (x
i
,x
j
) ∈ W,
0, (x
i
,x
j
) ∈ W.
Означення 15.6. Матрицю A =(a
ij
) називають матрицею iнцидентностi
(сумiжностi) графа Γ(X, W ).
Приклад 15.7. Запишемо матрицю iнцидентностi графа Γ(X, W), зображе-
ного на рисунку:
• •
•
1 2
345
• •
X = {1, 2, 3}, W = {(1, 2); (1, 3)}
Вiдповiдь:
A =
⎛
⎜
⎜
⎜
⎜
⎝
01101
10000
10000
00000
10000
⎞
⎟
⎟
⎟
⎟
⎠
.
Означення 15.8. Послiдовнiсть вершин i ребер x
i
1
, (x
i
1
,x
i
2
), x
i
2
, (x
i
2
,x
i
3
),
x
i
3
,...,(x
i
n−2
,x
i
n−1
), x
i
n−1
, (x
i
n−1
,x
i
n
), x
i
n
, у якiй сусiднi ребра iнцидентнi
однiй i тiй же вершинi, називають маршрутом. Вказаний маршрут з’єднує
вершини x
i
1
та x
i
n
, i його можна позначати x
i
1
,x
i
2
,...,x
i
n−1
,x
i
n
(наявнiсть
ребер припускається).
Маршрут графа називають ланцюгом, якщо всi його ребра рiзнi, i про-
стим ланцюгом, якщо всi його вершини рiзнi. Замкнений ланцюг називають
циклом. Замкнений маршрут називають простим циклом, якщо всi його n
вершин рiзнi i n ≥ 3.
Означення 15.9. Вiдстанню d(u, v) мiж двома вершинами u i v графа Γ
називають довжину найкоротшого простого ланцюга, який їх з’єднує. Якщо
u i v не з’єднанi, покладемо d(u, v)=∞. Найкоротший простий u...v-ланцюг
також називають геодезичним.
Означення 15.10. Дiаметром d(Γ) зв’язного графа Γ називають довжину
найдовшого геодезичного ланцюга в ньому:
d(Γ) = max
u,v∈Γ
d(u, v).
87
Вершина є центральною в Γ, якщо вiдстань вiд неї до будь-якої iншої вершини
є найменшою. Ця вiдстань є радiусом Γ i позначається, як r(Γ):
r(Γ) = min
u∈Γ
max
v∈Γ
d(u, v).
Приклад 15.11. Розглянемо граф Γ на рисунку нижче:
• •
•
•
•
v
2
v
1
v
3
v
5
v
4
На ньому v
1
,v
2
,v
5
,v
2
,v
3
– маршрут, який не є ланцюгом, а v
1
,v
2
,v
5
,v
4
,v
2
,v
3
– ланцюг, але не простий ланцюг, v
1
,v
2
,v
5
,v
4
– простий ланцюг, v
2
,v
4
,v
5
,v
2
– простий цикл.
Дiаметр графа d(Γ) = 2, центральною у ньому є вершина v
2
, вiдстань вiд
якої до будь-якої iншої вершини графа Γ дорiвнює r(Γ) = 1.
Означення 15.12. Два графи G i H iзоморфнi (позначається G H), якщо
мiж їх множинами вершин iснує взаємно однозначна вiдповiднiсть, яка збе-
рiгає сумiжнiсть.
Приклад 15.13. Показати,щографиΓ
1
та Γ
1
iзоморфнi:
1 2
6
3 4
5
• •
•
• •
•
Γ
1
1 5
6
2
3
4
• •
••
•
•
Γ
2
Розв’язок. Досить просто побудувати бiєктивне вiдображення мiж множина-
ми вершин графiв Γ
1
i Γ
2
, яке зберiгає сумiжнiсть:
123456
152436
.
Дiйсно, вершина 1 графа Γ
1
сумiжна з вершинами 2, 3 i 6, а її образ –
вершина 1 графа Γ
2
теж сумiжна з вiдповiдними образами – вершинами 5,
2 i 6. Перевiряючи послiдовно так вершини далi, отримуємо, що Γ
1
Γ
2
.
88
Означення 15.14. Кажуть,щографΓ(X
,W
) є пiдграфом графа Γ(X, W ),
якщо X
⊂ X, W
⊂ W . Якщо X
= X, то пiдграф Γ(X
,W
) називають
остовним пiдграфом.
Означення 15.15. Граф Γ(X, W ) називають зв’язним, якщо будь-якi двi
вершини x
i
∈ X та x
j
∈ X можна сполучити ланцюгом.
Означення 15.16. Граф Γ(X, W ) є сумою графiв Γ(X
1
,W
1
),...,Γ(X
k
,W
k
),
якщо
X =
k
i=1
X
i
,W=
k
i=1
W
i
.
Цю суму називають прямою, якщо X
i
∩X
j
= ∅,i = j. Такi графи називають
компонентами зв’язностi.
Приклад 15.17. Знайти компоненти зв’язностi графа, зображеного на ри-
сунку:
• •
•
1 2
748
3 5
6 9
• •
•
•
•
•
Вiдповiдь. Граф складається з трьох компонент зв’язностi:
X
1
= {1, 2, 7, 8},X
2
= {4},X
3
= {3, 5, 6, 9}.
Означення 15.18. Декартовим добутком графiв G(X, V ) i H(Y,U) назива-
ють граф G × H, вершинами якого є пари вигляду (x, y), x ∈ X, y ∈ Y ,i
в якому вершини (x
1
,y
1
) та (x
2
,y
2
) сумiжнi тодi i лише тодi, коли сумiжна
хоча б одна з пар x
1
, x
2
(у графi G)чиy
1
, y
2
(у графi H).
89