Файл: Учебное пособие ульяновск 2018 msc2010 05 Combinatorics ббк 22. 176 Удк 519. 1 В313 Рецензенты.pdf

48
×
(−am)·(−am − 1)· . . . ·(−am − (k − m) + 1)
(k − m)!
=
= a ·
(am − 1) · . . . · (am − m + 1)
m!
×
× (−1)
k−m
·
am · (am + 1) · . . . · (am + (k − m) − 1)
(k − m)!
=
= (−1)
k−m
·
(am + (k − m) − 1) · . . . · (am + 1) · am
(k − m)!
×
×
(am − 1) · . . . · (am − m + 1)
m!
· a =
= (−1)
k−m
·
am + (k − m) − 1
k − 1

·
(k − 1)!
m! · (k − m)!
· a =
= (−1)
k−m
·
(a − 1) · m + k − 1
k − 1

·
k m

·
a k
И, следовательно, тождество (`) принимает вид:
k
X
m = 1
(−1)
k−m
·
(a−1)·m+k−1
k − 1

·
k m

·
a k
= (−1)
k−1
·
a k
,
k
X
m = 1
(−1)
m
·
(a−1)·m + k − 1
k − 1

·
k m

= −1 ,
k ≥ 1 .
При m = 0 все множители суммы равны единице, поэтому гипотетическое тождество (`) эквивалентно следующему:
k
X
m = 0
(−1)
m
·
(a−1)·m + k − 1
k − 1

·
k m

= 0 ,
k ≥ 1 .
Его истинность вытекает из следующего утверждения.

49 4.9. Лемма. При всех α, β ∈ C и натуральных k ≥ 1 выпол- няется равенство:
k
X
m = 0
(−1)
m
·
αm + β
k − 1

·
k m

= 0 .
Доказательство. Сначала привлеч¨
ем удобные обозначения.
На мультипликативной группе z
C
= {z a
| a ∈ C } символи- ческих степеней определим “распознающую функцию”:
[ z s
] : z
C
→ {0, 1} , [ z s
](z a
) = [ s = a ] .
По линейности она продолжатся до “коэффициентного опе- ратора” ([11, с. 11]) на пространстве формальных рядов:
[ z s
] : C hh z
C
ii → C , [ z s
]
X
a ∈ C
λ
a z
a

= λ
s
Оператор [ z s
] хорошо определ¨ен на формальных рядах, но его безусловное применение к функциям может приводить к недоразумениям, поскольку функции могут представляться формальными рядами неоднозначно. Рассмотрим пример:
X
k ≥ 0
z k
= (1 − z)
−1
= −z
−1
·

1 −
1
z

−1
= −
X
k ≤ −1
z k
,
[ z s
] (1 − z)
−1
= 2 · [ s ≥ 0 ] − 1 , s ∈ Z .
Поэтому функции могут не обладать некоторыми бесспор- ными свойствами формальных рядов:
F (z) =
X
a ∈ C
[ z a
](F (z)) · z a
Но некоторые свойства оператора [ z s
] универсальны:
[ z s
](F (αz)) = α
s
· [ z s
](F (z)) , α 6= 0 ,

50
[ z
αs
](F (z
α
)) = [ z s
](F (z)) , α 6= 0 ,
[ z s
](F (z)·z t
) =
z s−t
(F (z)) .
Отображение [ z s
] – новое проявление хорошо известной операции. Упомянутое пространство рядов изоморфно про- странству функций {f : C → C }. Функции f соответствует ряд вида
P
a ∈ C
f (a)·z a
, а оператору [ z s
] – отображение под- становки f → f (s). Обычные степенные ряды (или ряды Ло- рана) соответствуют комплекснозначным функциям, опреде- л¨
енным на множестве натуральных (или целых) чисел. Для наших целей их может оказаться недостаточно. Но в ито- ге наше определение формальных рядов слишком широкое,
чтобы снабдить их множество структурой алгебры. Не все формальные ряды умножаемы по стандартному правилу:
X
a ∈ C
λ
a z
a

·
X
b ∈ C
µ
b z
b

=
X
s ∈ C
z s
·
X
a+b = s
λ
a
µ
b

Чтобы не иметь проблем с коэффициентами при z s
, нужны какие-то ограничения на один или оба сомножителя. Здесь достаточно фактической конечности сумм
P
a+b = s
λ
a
µ
b при всех s ∈ C . То есть,– конечности множества пар:
(a, b) ∈ C
2
| a + b = s , λ
a
·µ
b
6= 0
А это может случиться, например, при фактической ко- нечности суммы в одном из сомножителей, или если оба мно- жителя являются несущественными рядами Лорана. Полный список достаточных условий трудноисчерпаем, и его состав- ление не входит в нашу задачу. Мы будем умножать фор- мальные ряды только в допустимой ситуации, и сможем при-

51
менять правило:
[ z s
](F (z) · G(z)) =
X
a+b = s
[ z a
](F (z)) ·
z b
(G(z)) .
Покажем, как оно работает в нашей задаче.
Ранее, в Лемме 3.6 на стр. 24, для u ≥ 0 было доказано тождество:
X
v ≥ 0
v u

· z v
=
z u
(1 − z)
u+1
Из него для u, s ∈ N
0
следует:
[ z s
]

z u
(1 − z)
u+1

=
s u

При α > 0 и t ≥ 0 получаем равенства:
z t
((1 − z)
k
) = (−1)
t
·
k t

=
z
−αt
((1 − z
−α
)
k
) =
=
z
−αt

z
α
− 1
z
α

k
!
;
[ z s
]
z
α
− 1
z
α

k
!
= 0 ,
при s > 0 или s 6
... α ∈
N .
Следовательно, при β ≥ 0, α > 0 и k ∈ N у нас есть выра- жение для фигурирующей в лемме суммы:
z
β

z
α
−1
z
α

k
·
z k−1
(1−z)
k
!
=
X
s, t ≥ 0
(−1)
t
k t

·

s k−1

·[ s−αt = β ] =
=
X
t ≥ 0
(−1)
t
k t

·
αt+β
k−1

=
k
X
m = 0
(−1)
m
·
αm+β
k−1

·
k m

52
С другой стороны, при α ∈ N можно записать:
z k−1
(1 − z)
k
·
z
α
− 1
z
α

k
=
z k−1
z
αk
·
z
α
− 1 1 − z

k
=
= (−1)
k
·
z k−1
z
αk
· (z
α−1
+ . . . + z + 1)
k
Это многочлен Лорана со степенями z, изменяющимися от k−1−αk ≤ −1 до k−1−αk+(α−1)·k = −1. Поэтому при любых натуральных α, β и k доказано равенство:
z
β

z
α
−1
z
α

k
·
z k−1
(1−z)
k
!
=
k
X
m = 0
(−1)
m
·
αm+β
k−1

·
k m

= 0 .
Но сумма справа является полиномом от α и β тоталь- ной степени, меньшей k. При фиксированном натуральном k его можно считать полиномом от β с полиномиальными по
α коэффициентами. При каждом натуральном α этот поли- ном от β имеет бесконечно много корней, следовательно, его коэффициенты – полиномы от α – обнуляются при любых натуральных подстановках α. Поэтому эти полиномы от α
вместе с исходным полиномом от α и β – тождественно ну- левые. Значит, последнее равенство выполняется для любых комплексных α, β, и доказательство леммы завершено. Тем самым, доказана и гипотеза (Γ). В частности, при a ∈ R
(a, 0, 0, . . . )
−1
= (c
1
, c

53 4.10. Лемма. Пусть d, n ≥ 1 и (a n
), (b n
), (
e a
n
), (e b
n
) – такие вещественные последовательности, что
(d · a
1
, d · a
2
, . . . )
−1
= (d · b
1
, d · b
2
, . . . ) ,
e a
n
= a n/d
· [ d \ n ] , e b
n
= b n/d
· [ d \ n ] .
Тогда (
e a
1
,
e a
2
, . . . )
−1
= (e b
1
, e b
2
, . . . ) .
Доказательство. По условию, равносильны равенства:
y = x
. Y
n ≥ 1
(1 − x n
)
d·a n
,
x = y
. Y
m ≥ 1
(1 − y m
)
d·b m
Применив подстановки x = t d
, y = w d
, получим:
w d
= t d
.Y
n ≥ 1 1−t d·n

d·a n
, t d
= w d
.Y
m ≥ 1 1−w d·m

d·b m
Теперь, извлекая корень степени d, получаем эквивалент- ные равенства, доказывающие Лемму 4.10:
w = t
. Y
n ≥ 1 1 − t d·n

a n
, t = w
. Y
m ≥ 1 1 − w d·m

b m
Лемма 4.10 позволяет обобщить Пример 4.7 на стр. 45.
4.11. Следствие. Если d ≥ 1, то (a·[ n = d ])
−1
= (e b
n
), где e
b n
= n
−1
·
X
m \ (n/d)
µ

n m·d

· (−1)
m
·
a·m·d m

· [ d \ n ] .

54 5. КОНЕЧНЫЕ РАЗНОСТИ
Одним из применений линейных операторов в комбинаторике является символическое исчисление Дж. Блиссара (иначе
– теневой анализ [24]). Для иллюстрации некоторых идей метода в этой главе мы рассмотрим конечные разности и разбер¨
ем формулу суммирования Эйлера, их использующую.
5.1. Определение. На числовых последовательностях вида u = (u n
, n ≥ 0) зададим преобразование разности:
∆ : u → ∆u, ∆u n
= u n
− u n+1
Степени его определим обычным образом:
∆
0
u = u ; ∆
k+1
u = ∆(∆
k u) , k ≥ 0 .
Найд¨
ем первое выражение степеней оператора ∆ – конеч- ных разностей. Вскоре мы получим другие формулы для них.
И все они вовлекают биномиальные суммы или их коэффи- циенты. Тем самым, эта глава будет приложением Главы 3,
на результаты которой мы будем постоянно опираться.
5.2. Лемма. Пусть k, n ≥ 0, тогда
∆
k u
n
=
X
0 ≤ s ≤ k
(−1)
s
·
k s

· u n+s
(δ)
Доказательство. Поднимем индексы u n
% u n
, тогда
∆u n
% u n
− u n+1
= (1 − u) · u n
;
∆
k u
n
% (1−u)
k
·u n
=
k
X
s = 0
(−1)
s
k s

·u s
·u n
=
k
X
s = 0
(−1)
s
k s

·u n+s

55
Теперь, опуская индексы u n
& u n
, получим искомое ра- венство. И такое рассуждение требует комментария.
5.3. Комментарий. Это – пример “теневого доказательства”.
Формула (δ) легко подтверждается разными традиционными способами – индукцией или через выражение ∆ посредством более ясных линейных операций (см. стр. 13):
∆u = u − u⇓ = (I− ⇓)u ;
∆
k u = (I− ⇓)
k u =
X
0 ≤ s ≤ k
(−1)
s
·
k s

· u⇓
s
Объясним – почему “теневое” рассуждение привело к пра- вильной формуле. Это позволит учитывать ограничения ме- тода в менее очевидных ситуациях. В разобранном случае причин три. Во-первых, – линейность ∆ и ∆
k
, как операто- ров на пространстве числовых последовательностей. Вторая причина – такие последовательности хорошо интерполиру- ются конечными линейными комбинациями геометрических прогресссий. Ведь конечная система Вандермонда
X
0 ≤ s ≤ n x
s
· (a s
)
k
= u k
, 0 ≤ k ≤ n разрешима для любых u
0
, . . . , u n
и различных a
0
, . . . , a n
. Сле- довательно, любой начальный отрезок последовательности u выглядит как конечная линейная комбинация геометричес- ких прогрессий (a s
)
k
, k ≥ 0
. Третья причина учитывает ха- рактер равенства (δ). Его правая часть линейна по u, вовле- кая ограниченный набор элементов. Это позволяет проверять равенство только на геометрических прогрессиях подъ¨
емом индексов. Доказательство Леммы 5.2 прояснено.

56
Привед¨
ем другие полезные выражения для степеней раз- ностей через новые характеристики последовательности.
5.4. Определение. Для u = (u n
, n ≥ 0) обозначим час- тичные суммы S
n
, знакопеременные частичные суммы A
n и
частичные суммы более общего, гильбертового вида Q
n
:
S
< 0
:= 0 ;
S
n
=
X
0 ≤ m ≤ n u
m
, при n ≥ 0 ;
A
< 0
:= 0 ;
A
n
=
X
0 ≤ m ≤ n
(−1)
m
· u m
, при n ≥ 0 ;
Q
< 0
:= 0 ;
Q
n
=
X
0 ≤ m ≤ n q
m
· u m
, при n ≥ 0, q 6= 0 .
5.5. Лемма. При k, n ≥ 0 имеются выражения:
∆
k u
n
=
X
−1 ≤ s ≤ k
S
n+s
· (−1)
s
·
k + 1
s + 1

;
∆
k u
n
= (−1)
n
·
X
−1 ≤ s ≤ k
A
n+s
·

k s

−

k s + 1


;
∆
k u
n
= q
−n
·
X
−1 ≤ s ≤ k
Q
n+s
·(−q)
−s
·

k s

+ q
−1
·

k s + 1


Доказательство. В формулу (δ) из Леммы 5.2 со стр. 54
поочер¨
едно подставим выражения:
u
α
= S
α
− S
α−1
= (−1)
α
· (A
α
− A
α−1
) , α ≥ 0 .
Тогда преобразование конечных сумм даст равенства:
∆
k u
n
=
X
0 ≤ a ≤ k
(−1)
a
·
k a

· (S
n + a
− S
n + a − 1
) =
=
X
0 ≤ a
(−1)
a
·
k a

·S
n+a
−
X
0 ≤ a
(−1)
a
·
k a

·S
n+a−1
=

57
=
X
−1 ≤ a
(−1)
a
·
k a

· S
n+a
−
X
−1 ≤ a
(−1)
a+1
·

k a + 1

· S
n+a
=
=
X
−1 ≤ a
(−1)
a
·S
n+a
·

k a

+

k a+1


=
X
−1 ≤ a
(−1)
a
·S
n+a
·
k+1
a+1

Далее, тем же способом:
∆
k u
n
=
X
0 ≤ b ≤ k
(−1)
b
·
k b

· (−1)
n+b
· (A
n+b
− A
n+b−1
) =
= (−1)
n
·
X
0 ≤ b
k b

· A
n+b
− (−1)
n
·
X
0 ≤ b
k b

· A
n+b−1
=
= (−1)
n
·
X
−1 ≤ b
k b

· A
n+b
− (−1)
n
·
X
−1 ≤ b

k b + 1

· A
n+b
=
= (−1)
n
·
X
−1 ≤ b
A
n+b
·

k b

−

k b + 1


Третья формула доказывается аналогично первым двум,
при этом используется подстановка в формулу (δ):
u
α
= q
−α
· (Q
α
− Q
α−1
) , α ≥ 0 .
И, тем самым, Лемму 5.5 можно считать доказанной.
5.6. Замечание. В предположении ограниченности частич- ных сумм (S
n
, n ≥ 0), (A
n
, n ≥ 0) или (Q
n
, n ≥ 0) вытекают интересные оценки разностей (∆
k u
n
, k, n ≥ 0).
Пусть сначала |S
n
| ≤ C
1
для всех n ≥ 0, тогда
|∆
k u
n
| ≤ C
1
·
X
−1 ≤ s ≤ k
k + 1
s + 1

= C
1
· 2
k+1

58
Для второй оценки предварительно исследуем знак разнос- ти при k > s :
k s

−

k s+1

=

k s+1

·
s+1
k−s
− 1

=

k s+1

·
2·s + 1 − k k−s
Так аргументируется известное наблюдение – биномиаль- ные коэффициенты монотонно растут до середины строки треугольника Паскаля, а потом они симметрично убывают.
Математически это выражается эквивалентностями, выпол- няющимися для всех целых s ≥ −1 и k ≥ 0 :
k s

−

k s+1

≥ 0 ⇔ s ≥
k−1 2
⇔ s ≥
k−1 2

=
k
2

Теперь если |A
n
| ≤ C
2
для всех n ≥ 0 , то получаем:
|∆
k u
n
| ≤ C
2
·
X
−1 ≤ s ≤ k
k s

−

k s + 1

=
= C
2
·
X
s < [k/2]


k s + 1

−
k s


− C
2
·
X
s ≥ [k/2]

k s

−

k s + 1


=
= C
2
·

k
[k/2]

− C
2
·

−

k
[k/2]

= 2 · C
2
·

k
[k/2]

Из формулы Стирлинга для факториала следует:

k
[k/2]

∼
r
2
πk
· 2
k
, при k → ∞ .
Поэтому при ограниченных A
n существует C
3
такое, что
|∆
k u
n
| ≤ C
3
·
r
2
πk
· 2
k

59
Две предыдущие оценки разностей можно обобщить. Если
|Q
n
| ≤ D для всех n ≥ 0 , то получаем:
|∆
k u
n
| ≤ 2 · D · q
−n
· (1 + q
−1
)
k
, при q > 0 ;
|∆
k u
n
| ≤ 2·D·|q|
−n−d(k+q)/(1−q)e
·

k d(k+q)/(1−q)e

, при q < 0 .
Здесь выражение d(k+q)/(1−q)e указывает нижнюю гра- ницу целых s ≥ −1, для которых при q < 0
k s

+ q
−1
·

k s + 1

≥ 0 .
Формула Стирлинга в этом случае при k → ∞ да¨ет:

k d(k+q)/(1−q)e

∼
∼
1
√
2πk
·

|q|
1/2
+ |q|
−1/2

·

|q|
1/(1+|q|)
+ |q|
−|q|/(1+|q|)

k
,
и окончательная оценка разностей при q < 0 упрощается:
|∆
k u
n
| ≤
e
D
√
2πk
· |q|
−n
· (1 + |q|
−1
)
k
Мы видим, что при |q| = 1 оценки наиболее просты. И
это мотивирует использование частичных сумм S
n и A
n
, для которых получаем очевидное следствие.
5.7. Следствие.
а) если частичные суммы (S
n
, n ≥ 0) ограничены, то огра- ничены (∆
k u
n
2
k
, k, n ≥ 0).
б) если ограничены знакопеременные суммы (A
n
, n ≥ 0), то существует равномерный по n ≥ 0 предел lim k → ∞
∆
k u
n
2
k
= 0 .

60
Поскольку сходящиеся последовательности ограничены, б)
выполняется при сходимости A
n
→ A = H
u
(−1).
5.8. Лемма. Если частичные суммы (S
n
, n ≥ 0) сходятся к
S = H
u
(1), то существует равномерный по k ≥ 0 предел lim n → ∞
∆
k u
n
2
k
= 2
−k
· lim n → ∞
∆
k u
n
= 0 ,
а также – равномерный по n ≥ 0 предел lim k → ∞
∆
k u
n
2
k
= 0 .
Доказательство. Пусть имеется сходимость:
S
n
→ S =
X
0 ≤ m u
m
= H
u
(1) .
Тогда u n
→ 0 и по формуле (δ) со стр. 54 при любом фиксированном k существует предел:
lim n → ∞
∆
k u
n
= 0 .
Но скорость сходимости может серь¨езно зависеть от k. На- пример, возьм¨
ем последовательность u
n
=
(−1)
n n + 1
−
(−1)
n+1
n + 2
=
(−1)
n
·(2n + 3)
(n + 1)·(n + 2)
Для не¨
е легко вычисляются частичные суммы:
S
n
=
n
X
m = 0
(−1)
m m + 1
−
(−1)
m+1
m + 2

= 1 −
(−1)
n+1
n + 2
→ 1 = S .
По Лемме 5.5 получаем:
∆
k u
n
=
X
−1 ≤ s ≤ k

1 −
(−1)
n+s+1
n + s + 2

·(−1)
s
·
k + 1
s + 1

=

61
=
k
X
s = −1
(−1)
s
·
k + 1
s + 1

+ (−1)
n
·
k
X
s = −1 1
n + s + 2
·
k + 1
s + 1

=
= −(1 − 1)
k+1
+ (−1)
n
·
X
−1 ≤ s ≤ k
1
n + s + 2
·
k + 1
s + 1

Поэтому
∆
k u
n
=
k
X
s = −1 1
n+s+2
·
k+1
s+1

>
1
n+2
·
k+1 1

=
k+1
n+2
Таким образом, содержательным утверждением о первом пределе в текущей Лемме является не его существование и значение, а равномерный характер этой сходимости.
Выведем ещ¨е одну формулу конечной разности. Для этого обозначим R
n
– остатки бесконечной суммы S :
R
n
= S − S
n
=
X
n < m u
m
⇒ S
n
= S − R
n
Тогда, по Лемме 5.5, получим важное для ближайших расч¨е- тов выражение:
∆
k u
n
=
X
−1 ≤ s ≤ k
(S − R
n+s
) · (−1)
s
·
k + 1
s + 1

=
= S ·
k
X
s = −1
(−1)
s
·
k+1
s+1

−
k
X
s = −1
R
n+s
·(−1)
s
·
k+1
s+1

=
= −
X
−1 ≤ s ≤ k
R
n+s
· (−1)
s
·
k + 1
s + 1

(%)
Сходимость S
n
→ S означает, что R
n
→ 0, и поэтому
∀ ε > 0 ∃ m
0
∀ m ≥ m
0
|R
m
| < ε .