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

62
Пусть n ≥ m
0
+ 1 , тогда для всех k ≥ 0 получаем:
∆
k u
n
2
k
≤ 2
−k
·
k
X
s = −1
|R
n+s
| ·
k + 1
s + 1

≤
≤ 2
−k
· ε ·
k
X
s = −1
k + 1
s + 1

= 2
−k
· ε · (1 + 1)
k+1
= 2·ε .
Полученная оценка доказывает равномерную сходимость в первом случае.
Для исследования второго предела мы используем при¨
ем из доказательства Следствия 3.4. Величины ε и m
0
– та- кие же, как и ранее. Заметим, что из сходимости R
n следует е¨
е ограниченность: |R
n
| < C для некоторой C. Используем новое выражение для конечной разности следующим образом:
∆
k u
n
=
−
m
0
− 1
X
s = −1
R
n+s
(−1)
s
k+1
s+1

−
k
X
s = m
0
R
n+s
(−1)
s
k+1
s+1

≤
≤
m
0
− 1
X
s = −1
|R
n+s
| ·
k + 1
s + 1

+
k
X
s = m
0
|R
n+s
| ·
k + 1
s + 1

≤
≤ C ·
m
0
− 1
X
s = −1
k + 1
s + 1

+ ε ·
k
X
s = m
0
k + 1
s + 1

Здесь мы считаем k ≥ m
0
, и, поскольку n ≥ 0, при s ≥ m
0
оказывается выполненным неравенство n + s ≥ m
0
Следовательно, мы получаем оценку:
∆
k u
n
2
k
≤ C · 2
−k
·
m
0
− 1
X
s = −1
k + 1
s + 1

+ ε · 2
−k
·
k
X
s = m
0
k + 1
s + 1

≤

63
≤ C · 2
−k
·
m
0
− 1
X
s = −1
k + 1
s + 1

+ ε · 2
−k
·
k
X
s = −1
k + 1
s + 1

=
= C · 2
−k
·
X
−1≤ s < m
0
k + 1
s + 1

+ ε .
Оставшаяся ограниченная сумма биномиальных коэффи- циентов является полиномом от k степени m
0
. Поэтому су- ществует предел:
lim k → ∞
2
−k
·
X
−1≤ s < m
0
k + 1
s + 1

= 0 ,
и найд¨
ется k
0
такое, что для k ≥ k
0
будет выполнено:
2
−k
·
X
−1≤ s < m
0
k + 1
s + 1

≤ ε/C ;
∆
k u
n
2
k
≤ ε + ε = 2·ε для всех n ≥ 0 .
Доказательство Леммы 5.8 закончено.
5.9. Пример. Рассмотрим интересный и важный для пони- мания конечных разностей случай. Пусть d ≥ 0 – целое число.
Возьм¨
ем последовательность u очень простого вида:
u n
= [ n = d ] , H
u
(t) = t d
Е¨
е конечные разности и их производящие функции вычис- лим по Лемме 5.2. Для k, n ≥ 0 получим:
∆
k u
n
=
X
0 ≤ s ≤ k
(−1)
s
·
k s

·[ n + s = d ] =
=
X
0 ≤ s ≤ k
(−1)
s
·
k s

·[ s = d − n ] = (−1)
d−n
·

k d − n

;

64
H
∆
k u
(t) =
X
n ≥ 0
∆
k u
n
· t n
=
d
X
n = 0
(−1)
d−n
·

k d − n

· t n
=
=
X
0 ≤ m ≤ min(k, d)
(−1)
m
·
k m

· t d−m
В рассмотренном случае H
∆
k u
(t) = t d
+ . . . – полином сте- пени d. В частности, при d ≥ k :
H
∆
k u
(t) = t d
· (1 − t
−1
)
k
= t d−k
· (t − 1)
k
;
H
∆
k u
(0) = ∆
k u
0
= (−1)
d
·
k d

= (−1)
d
· [ k = d ] ;
H
∆
k u
(1) = [ k = 0 ] ;
H
∆
k u
(−1) = (−1)
d
· 2
k
При d < k значения полинома H
∆
k u
(t) более замысловаты:
H
∆
k u
(1) =
d
X
m = 0
(−1)
m
·
k m

= (−1)
d
·
k − 1
d

;
H
∆
k u
(−1) = (−1)
d
·
d
X
m = 0
k m

= (−1)
d
· ]

Ш
(k)
d

,
здесь Ш
(k)
d
– замкнутый шар радиуса d в пространстве F
k
2
с метрикой Хэмминга (см. Замечание 3.5 на стр. 21).
В силу линейности ∆
k и функции Гильберта по u из рас- смотренного Примера 5.9 получаем полезные факты:
5.10. Следствие. Если последовательность u финитна, – то есть, H
u
(t) является полиномом, – тогда H
∆
k u
(t) – полином той же степени и с тем же самым старшим коэффициен- том для всех k ≥ 1. Но обратное неверно: для нефинитной

65
u последовательность ∆
k u может быть финитной при всех k ≥ 1. Так, для постоянных u все разности ∆
k u
n
– нулевые.
Связь рядов Гильберта последовательности и е¨
е k-ой раз- ности в общем случае описывается правилом: H
∆
k u
(t) явля- ется регулярной (маклореновской) частью ряда Лорана:
H
∆
k u
(t) = reg
0

H
u
(t) · 1 − t
−1

k

Иное представление возможно при сходимости ряда
X
s ≥ 0
(−1)
s
· u s
= H
u
(−1) .
В этом случае, по леммам Абеля, степенной ряд H
u
(t) схо- дится равномерно на отрезке [−1, α ], для любого α ∈ (0, 1), а радиус сходимости его не меньше 1:
R
−1
= lim n → ∞
n p|u n
| ≤ 1 .
Несложно оценить первую разность:
|∆u n
| = |u n
− u n+1
| ≤ |u n
| + |u n+1
| ≤ 2 · max (|u n
|, |u n+1
|) .
Из этой оценки следует неравенство:
lim n → ∞
n p|∆u n
| ≤ lim n → ∞
n p|u n
| .
Поэтому, радиусы сходимости рядов H
∆
k u
(t) не убывают с ростом k, и все они не меньше 1. Эта совместная регуляр- ность в окрестности нуля в C производящих функций H
∆
k u
(t)
при k ≥ 0 приводит их к функциональной связи, которую подсказывают геометрические прогрессии.

66
Выразимость последовательности u через такие прогрессии отражается на ряде Гильберта рациональным образом:
u n
=
d
X
s=1
λ
s
· (a s
)
n
, n ≥ 0
⇒
H
u
(t) =
d
X
s=1
λ
s
1 − a s
· t
Комплексная формула Коши позволяет мыслить u беско- нечной линейной комбинацией геометрических прогрессий:
H
u
(t) =
1 2πi
I
|w| = r < 1
H
u
(w)
w − t dw =
1 2πi
I
H
u
(w)/w
1 − (t/w)
dw , |t| < r .
Эта формула выполняется, поскольку H
u
(z) регулярна вну- три и в окрестности контура |w| = r < 1.
Найд¨
ем такое же интегральное представление H

67
При t = 0 этот интеграл также нулевой, поэтому
H
∆u
(t) =
1 2πi
I
|w| = r < 1

1 −
1
w

·
H
u
(w)
w − t dw , |t| < r .
5.11. Лемма. При целых s ≥ 0 и |t| < r:
H
∆
s u
(t) =
1 2πi
I
|w| = r < 1

1 −
1
w

s
·
H
u
(w)
w − t dw .
Доказательство. Эту формулу докажем индукцией по s.
Мы уже убедились, что она верна при s = 0, 1. При s ≥ 2 :
H
∆
s u
(t) = H
∆
s−1
(∆u)
(t) =
1 2πi
I

1−
1
w

s−1
·
H
∆u
(w)
w − t dw =
=
1 2πi
I
1−
1
w

s−1
·


1−
1
w

· H
u
(w) +
1
w
· H
u
(0)

·
dw w − t
=
=
1 2πi
I
1−
1
w

s
·
H
u
(w)
w − t dw +
H
u
(0)
2πi
I
1−
1
w

s−1
·
dw w(w−t)
Во втором интеграле заменим z = 1/w, при |t| < r, s ≥ 2 :
I
|w| = r < 1

1 −
1
w

s−1
·
dw/w
2 1 − (t/w)
=
I
|z| = 1/r > 1
(1 − z)
s−1 1 − t·z dz .
Подинтегральная функция регулярна внутри контура и в его окрестности. Поэтому, этот интеграл нулевой, что завер- шает индукционный шаг. Лемма 5.11 доказана.
В частности, что при целых s ≥ 0 доказана формула:
∆
s u
0
= H
∆
s u
(0) =
1 2πi
I
|w| = r < 1

1 −
1
w

s
·
H
u
(w)
w dw .

68
Перейд¨ем к основному утверждению этой главы, немного иначе доказанному в книге ([9, с. 269-272]).
5.12. Теорема (формула суммирования Эйлера).
При условии существования левой части, есть равенство:
X
s ≥ 0
(−1)
s
· u s
=
X
k ≥ 0
∆
k u
0 2
k+1
Доказательство. Сначала, по символическому методу, под- нимем и опустим индексы:
X
k ≥ 0
∆
k u
0 2
k+1
%
X
k ≥ 0
(1 − u)
k
· u
0 2
k+1
=
X
k ≥ 0 1
2
·
1 − u
2

k
=
=
1 2
·

1 −
1 − u
2

−1
=
1 1 + u
=
X
s ≥ 0
(−1)
s
· u s
&
X
s ≥ 0
(−1)
s
· u s
Эти преобразования требовали ограничения |u| < 1, из ко- торого следуют другие необходимые неравенства:
0 <
1 − u
2
< 1
и
1 − u
2
< 1 .
В силу линейности по u формулы Эйлера, е¨
е справедли- вость доказана для конечных линейных комбинаций геомет- рических прогрессий ((a s
)
n
, n ≥ 0) с множителями |a s
| < 1 .
Однако, для выполнения формулы Эйлера достаточно схо- димости знакопеременной суммы u
0
− u
1
+ u
2
− . . . . Разоб- ранный случай вытекает из этого слабого условия.
Заметим, что формула Эйлера вовлекает все элементы по- следовательности u. Поэтому интерполяция геометрически- ми прогрессиями не да¨
ет полное доказательство формулы без

69
привлечения какой-то теории сходимости. Такие же пробле- мы со сходимостью есть у операторного метода:
X
k ≥ 0
∆
k
2
k+1
=
X
k ≥ 0
(I− ⇓)
k
2
k+1
=
X
k ≥ 0 1
2
·
1− ⇓
2

k
=
= (1+ ⇓)
−1
=
X
s ≥ 0
(−1)
s
· ⇓
s
Для полного обоснования формулы Эйлера получим выра- жение, подобное (%) со стр. 61 из доказательства Леммы 5.8.
Обозначим r n
– остатки бесконечной суммы A = H
u
(−1) :
r n
= A − A
n
=
X
n < m
(−1)
m
· u m
⇒ A
n
= A − r n
Тогда, по Лемме 5.5, получим формулу:
∆
k u
n
= (−1)
n
·
X
−1 ≤ s ≤ k
(A − r n+s
)·

k s

−

k s + 1


=
= (−1)
n
· A ·
X
−1 ≤ s ≤ k

k s

−

k s + 1


−
−(−1)
n
·
X
−1 ≤ s ≤ k r
n+s
·

k s

−

k s + 1


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

k s

−

k s + 1


Теперь мы выразим конечную сумму, используя формулу
Следствия 3.8 со стр. 26:
d
X
k = 0
∆
k u
n
2
k+1
= −(−1)
n
·
d
X
k = 0 1
2
k+1
·
k
X
s = −1
r n+s
·

k s

−

k s+1


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

k s

−

k s+1


!
=

70
= (−1)
n
· r n−1
·

1 −
1 2
d+1

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

k s

−

k s+1


=
= (−1)
n
· r n−1
·

1 −
1 2
d+1

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

k s

−

k s+1


=
= (−1)
n
· r n−1
·

1 −
1 2
d+1

−
−(−1)
n
·
d
X
s = 0
r n+s
·
1 2
d+1
·
s + 1
X
v = 0
d + 1
v

−
s
X
v = 0
d + 1
v

!
=
= (−1)
n
· r n−1
·

1 −
1 2
d+1

−
(−1)
n
2
d+1
·
d
X
s = 0
r n+s
·
d + 1
s + 1

Очевидно, что при d → ∞ уменьшаемое этой разности стремится к (−1)
n
· r n−1
. Поскольку при фиксированном n и s → ∞ разность r n+s стремится к 0, при d → ∞ вычитаемое стремится к 0. Этот факт был установлен при доказательстве
Леммы 5.8. Поэтому при фиксированном n получено:
lim d → ∞
d
X
k = 0
∆
k u
n
2
k+1
=
X
k ≥ 0
∆
k u
n
2
k+1
= (−1)
n
· r n−1
(E )
В частности, получена искомая формула Эйлера:
X
k ≥ 0
∆
k u
0 2
k+1
= r
−1
= A − A
−1
= A .

71
Заметим, что формула суммирования Эйлера через произ- водящие функции выражается следующим образом:
H
u
(−1) =
X
k ≥ 0
H
∆
k u
(0)
2
k+1
Есть е¨
е обобщение, вовлекающее производящие функции по существу. Вид такой формулы найд¨
ем в частном случае из примера 5.9 со стр. 63: u n
= [ n = d ], n, d ≥ 0.
X
k ≥ 0
H
∆
k u
(t)
2
k+1
=
X
k ≥ 0 1
2
k+1
·
min(k, d)
X
m = 0
(−1)
m
·
k m

· t d−m
=
=
d
X
m = 0
(−1)
m
· t d−m
2
X
k ≥ 0
k m

·
1 2
k
=
d
X
m = 0
(−1)
m
· t d−m
2
·
2
−m
2
−m−1
=
=
d
X
m = 0
(−1)
m
· t d−m
=
t d+1
+ (−1)
d t + 1
=
t · H
u
(t) + H
u
(−1)
t + 1
Во второй строке применено биномиальное тождество из
Леммы 3.6 со стр. 24. Окончательное выражение получено благодаря линейности выведенного равенства по u. Следо- вательно, это выражение истинно для финитных u, – для которых H
u
(t) является полиномом.
Теперь, вооруж¨енные знакомством с этой формулой, мы можем доказать е¨е в более общем случае.
5.13. Предложение. При условии сходимости числовой сум- мы H
u
(−1) выполняется равенство степенных рядов:
X
k ≥ 0
H
∆
k u
(t)
2
k+1
=
H
u
(−1) + t · H
u
(t)
1 + t
(})

72
Доказательство. Воспользуемся полученной ранее форму- лой (E ) со стр. 70:
(1 + t) ·
X
k ≥ 0
H
∆
k u
(t)
2
k+1
= (1 + t) ·
X
k ≥ 0 2
−k−1
·
X
n ≥ 0
∆
k u
n
· t n
=
= (1 + t) ·
X
n ≥ 0
t n
·
X
k ≥ 0
∆
k u
n
2
k+1
= (1 + t) ·
X
n ≥ 0
t n
· (−1)
n
· r n−1
=
=
X
n ≥ 0
t n
· (−1)
n
· r n−1
+
X
n ≥ 0
t n+1
· (−1)
n
· r n−1
=
=
X
n ≥ 0
t n
· (−1)
n
· r n−1
+
X
n ≥ 1
t n
· (−1)
n−1
· r n−2
=
= r
−1
+
X
n ≥ 1
t n
· (−1)
n
· ( r n−1
− r n−2
) =
= A −
X
n ≥ 1
t n
· (−1)
n
· (−1)
n−1
· u n−1
= H
u
(−1) + t · H
u
(t) .
Провед¨
енные вычисления доказывают тождественность со- ответствующих формальных степенных рядов. Для обоснова- ния равенства функций, ими представляемых, и правильнос- ти выполненных преобразований надо учесть функциональ- ные свойства H
∆
k u
(t) и H
u
(t).
Вспомним, что из сходимости числового ряда H
u
(−1) сле- дует регулярность всех H
∆
k u
(t) в круге радиуса 1. Поэтому,
предыдущие преобразования степенных рядов справедливы на любом компакте внутри этого круга, а функциональное равенство (}) со стр. 71 выполняется для |t| < 1 , где двойной ряд в левой части сходится абсолютно.
Эффективность формулы суммирования Эйлера проиллю- стрируем примером из книги ([9, с. 274]).
π
4
= arctg (1) =
Z
1 0
dx
1 + x
2
=
Z
1 0
X
n ≥ 0
(−1)
n
· x
2n

dx =

73
=
X
n ≥ 0
(−1)
n
·
Z
1 0
x
2n dx =
X
n ≥ 0
(−1)
n
·
x
2n+1 2n + 1 1
0
=
=
X
n ≥ 0
(−1)
n
2n + 1
= 1 −
1 3
+
1 5
−
1 7
+ . . .
Возьм¨
ем последовательность: u n
= (2n + 1)
−1
. Несложно найти и обосновать по индукции вид е¨е разностей:
∆
m u
n
=
2 · 4 · . . . · 2m
(2n + 1) · (2n + 3) · . . . · (2n + 2m + 1)
=
= 2
m
·
m!
(2n + 1) · (2n + 3) · . . . · (2n + 2m + 1)
=
=
2 2m+1
m + 1
·
2n n

·
n + m + 1
n

−1
·
2n + 2m + 2
n + m + 1

−1
В частности, получаем выражение:
∆
m u
0
= 2
m
·
m!
1 · 3 · . . . · (2m + 1)
=
2 2m+1
m + 1
·
2m + 2
m + 1

−1
Таким образом, формула Эйлера да¨
ет равенство:
π
4
=
X
m ≥ 0 2
m m + 1
·
2m + 2
m + 1

−1
=
1 2
+
1 6
+
1 15
+
1 35
+ . . . .
Слагаемые можно оценить по формуле Стирлинга:
∆
m u
0 2
m+1
∼
2
m m+1
·
r
π(m+1)
2
· 2
−2m−2
=
1 2
m+2
·
r
π
2(m+1)

74 6. ЧИСЛА КАТАЛАНА
Изобретение последовательности 1, 1, 2, 5, 14, 42, 132, . . . при- писывают китайскому математику Мин Ан-ту, нашедшему е¨е рекуррентные соотношения в 1730 году ([32, с. 273]). Геомет- рическую интерпретацию этих чисел дал санкт-петербургс- кий академик Н.И. Фусс в 1791 г., первое основательное со- чинение о них в 1838 г. опубликовал бельгиец Э.Ш. Каталан
([10, с. 231, 396]). Числа стали называться “каталановыми”
после выхода в 1900 г. учебника по комбинаторике Е. Нетто.
Найдено около сотни комбинаторных и алгебраических ин- терпретаций чисел Каталана ([32, с. 272, 283-306, 322-331]).
Ограничимся одной: C
n считает правильные расстановки ско- бок на неассоциативном произведении n + 1 сомножителей x
0
× x
1
× . . . × x n
, n ≥ 0. Начальные варианты расстановок скобок таковы:
a; (a × b); (a × b) × c
, a × (b × c );

(a × b) × c
× d

,

a ×(b × c)
× d

,

a × (b × c) × d


,

a × b × (c × d )


, (a × b) × (c × d )
; . . .
Всякая последовательность с правильно расставленными скобками имеет арифметические характеристики, не завися- щие от скобок – длину и состав, то есть, кратности входящих символов. Но они не всегда определяют саму последователь- ность из-за возможности скобочного различия. Что видно на простейшем примере:
(x × x) × x
6= x × (x × x) .