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

21
Во втором случае имеем 0 < (1 − x)/x < 1 и поэтому:
0 <
n
B
s
(x) = x n
·
s
X
k = 0
n k

·
1 − x x

k
< x n
·
s
X
k = 0
n k

По аналогичным соображениям получаем равенство:
lim n → ∞
n
B
s
(x) = lim n → ∞
x n
·
s
X
k = 0
n k

= 0 .
Тем самым, первая часть Следствия 3.4 доказана. Для до- казательства второй части достаточно заметить равенство:
n
X
k=s
n k

· (1−x)
k
· x n−k
=
n
B
n
(x) −
n
B
s−1
(x) = 1 −
n
B
s−1
(x) .
3.5. Замечание. При доказательстве Следствия 3.4 были по- лучены простые, но интересные выражения:
n
B
s
(x) = x n
·
s
X
k = 0
n k

·
1 − x x

k
,
n
B
s
(0.5) = 2
−n
·
s
X
k = 0
n k

В первом из них можно сделать замену (1 − x)/x = a − 1.
Тогда x = 1/a и первое выражение принимает вид:
n
B
s a
−1
= a
−n
·
s
X
k = 0
n k

· (a − 1)
k
Второе получается подстановкой a = 2. Эти выражения имеют смысл в теории помехоустойчивого блочного кодиро- вания. Вспомним соответствующие определения.
Пусть A – конечный алфавит, ](A) = a ≥ 1, n ≥ 1. Рас- смотрим слова (блоки) длины n : w = w(1) · · · w(n) ∈ A
n

22
Множество A
n можно снабдить метрикой Хэмминга:
d(w,
e w ) = ]
i = 1, . . . , n | w(i) 6=
e w(i)
Определим замкнутый шар в A
n радиуса s с центром w:
Ш
(n)
s
(w) = {
e w ∈ A
n
| d(w,
e w ) ≤ s}.
Очевидно,
Ш
(n)
0
(w) = {w}; Ш
(n)
s
(w) = A
n
, при s ≥ n. Про- стое комбинаторное рассуждение показывает, что количество элементов множества Ш
(n)
s
(w) не зависит от w :
]

Ш
(n)
s
(w)

= ]

Ш
(n)
s

=
s
X
k = 0
n k

· (a − 1)
k
Поэтому значение неполных биномиальных сумм приобре- тает вполне конкретный смысл:
n
B
s a
−1
= ]

Ш
(n)
s
.
] (A
n
) .
Предположим, что при передаче блоки w и e
w подвергаются не более, чем s искажениям, каждый. Тогда для однозначно- го восстановления значения искаж¨енного блока – w это или e
w – необходимо и достаточно, чтобы выполнялось условие:
Ш
(n)
s
(w) ∩ Ш
(n)
s
(
e w ) = ∅ .
Таким образом, для над¨ежного исправления не более s ис- кажений в передаваемых блоках, эти блоки должны окру- жать непересекающиеся замкнутые шары радиуса s. Что да¨ет верхнюю границу количества разных передаваемых блоков:
] (A
n
)
]

Ш
(n)
s

=

n
B
s a
−1


−1

23
Следовательно, информационная ¨емкость блока построен- ного кода имеет верхнюю границу:
log a

] (A
n
)
]

Ш
(n)
s

= n − log a

]

Ш
(n)
s

Соответственно, нижняя граница количества избыточных или проверочных символов в блоке, обеспечивающих исправ- ление s искажений, равна log a

]

Ш
(n)
s

= log a
s
X
k = 0
n k

· (a − 1)
k
!
Это мотивирует важность функции ]

Ш
(n)
s

, для которой хотелось бы иметь компактное выражение. В случае двоич- ного кодирования, при a = 2, A = F
2
, проясняется интерес к неполным биномиальным суммам по нижнему индексу, о которых авторы книги ([10]) сообщают:
”
. . . для частичной суммы элементов ряда треугольника
Паскаля не существует замкнутого выражения.“(с. 191)
В этом утверждении речь ид¨
ет о выражении специального,
гипергеометрического вида, пригодного сразу для всех n и s. Что не исключает потенциальной возможности компакт- ного представления функциями иной природы, и замкнутых выражений для отдельных n или s. Например, при s ≥ 0:
s
X
k = 0
−1
k

=
s
X
k = 0
(−1)
k
= [ s– ч¨етное ] = (1 + (−1)
s
)/ 2 ,
s
X
k = 0
1
k

= 1 + [ s ≥ 1 ] ,
s
X
k = 0
2
k

= 1 + 2·[ s ≥ 1 ] + [ s ≥ 2 ] .

24
Поначалу может показаться удивительным тождество, да- ющее пример замкнутых, компактных выражений:
s
X
k = 0
n k

· (−1)
k
= (−1)
s
·
n − 1
s

Но с точки зрения производящих функций, сумма слева –
это коэффициент при x s
в разложении Маклорена функции:
X
a ≥ 0
x a
·
X
b ≥ 0
n b

· (−x)
b
=
1 1 − x
· (1 − x)
n
= (1 − x)
n−1
Указанные равенства обеспечивают простоту выражения знакопеременной суммы биномиальных коэффициентов. Тот же при¨
ем для неполной суммы биномиальных коэффициен- тов не да¨
ет ничего коротко разворачиваемого:
X
s ≥ 0
x s
·
s
X
k = 0
n k

=
X
a ≥ 0
x a
·
X
b ≥ 0
n b

· x b
=
1 1 − x
· (1 + x)
n
Это рассуждение, конечно, не доказывает категоричного утверждения о несуществовании компактного выражения для рассматриваемой суммы. Вопрос оста¨ется открытым.
Прежде наши производящие функции вовлекали биноми- альные коэффициенты по нижнему индексу. Включение верх- него индекса также да¨
ет полезные формулы.
3.6. Лемма. Для u ≥ 0 и |z| < 1 имеется тождество:
X
v ≥ 0
v u

25
= z u
·
X
v ≥ u v·(v − 1)· . . . ·(v − (v − u) + 1)
(v − u)!
· z v−u
=
= z u
·
X
v ≥ u v·(v − 1)· . . . ·(u + 1)
(v − u)!
· z v−u
=
= z u
·
X
v ≥ u
(−v)·(−v + 1)· . . . ·(−u − 1)
(v − u)!
· (−z)
v−u
=
= z u
·
X
v ≥ u
(−u−1)·(−u−2)· . . . ·(−u−1−(v−u)+1)
(v − u)!
· (−z)
v−u
=
= z u
·
X
s ≥ 0
−u−1
s

·(−z)
s
= z u
·(1 − z)
−u−1
=
z u
(1 − z)
u+1
Только что полученное биномиальное тождество дополним его полезным усеч¨
енным вариантом.
3.7. Лемма. При u, m ≥ 0 и |z| < 1 имеется равенство:
m
X
v = 0
v u

· z v
=
z u
(1 − z)
u+1
− z m+1
·
u
X
s = 0
m+1
s

·
z u−s
(1 − z)
u−s+1
Доказательство. Левую часть равенства обозначим F
u
(z) и при −1 < θ < (1−z)/|z| изучим производящую функцию:
X
u ≥ 0
F
u
(z) · θ
u
=
X
u ≥ 0
θ
u
·
m
X
v = 0
v u

· z v
=
=
m
X
v = 0
z v
·
X
u ≥ 0
v u

· θ
u
=
m
X
v = 0
z v
·(1+θ)
v
=
1−(z(1+θ))
m+1 1−z(1+θ)
=
=
1−z m+1
·(1+θ)
m+1 1 − z − z · θ
=
1−z m+1
·(1+θ)
m+1 1 − z

1−
z
1−z
· θ

=

26
=
1 1 − z
· 1 − z m+1
· (1 + θ)
m+1
·
X
k ≥ 0
z k
(1 − z)
k
· θ
k
=
= 1 − z m+1
· (1 + θ)
m+1
·
X
k ≥ 0
z k
(1 − z)
k+1
· θ
k
=
=
X
u ≥ 0
z u
(1−z)
u+1
· θ
u
− z m+1
·(1+θ)
m+1
·
X
k ≥ 0
z k
(1−z)
k+1
· θ
k
Искомая формула получается при сравнении множителей при θ
u
, с уч¨
етом равенства:
(1+θ)
m+1
·
X
k ≥ 0
z k
· θ
k
(1−z)
k+1
=
m+1
X
s = 0
m+1
s

· θ
s
·
X
k ≥ 0
z k
· θ
k
(1−z)
k+1
=
=
X
u ≥ 0
θ
u
·
min(u, m+1)
X
s = 0
m + 1
s

·
z u−s
(1 − z)
u−s+1
Лемма 3.7 доказана. При подстановке в е¨е формулу z = 1/2
получим полезное тождество.
3.8. Следствие. При u, m ≥ 0 имеется равенство:
m
X
v = 0
v u

·
1 2
v+1
= 1 −
1 2
m+1
·
min(u, m+1)
X
s = 0
m+1
s

Двойные числовые и степенные ряды исследованы в учеб- нике ([9, Гл. 13, с. 229-251]). Свойства биномиальных коэф- фициентов изложены в книге ([10, Гл. 5, с. 178-232]). Много тождеств дано в справочнике ([21, Гл. 4, с. 606-635; Прил. 1,
с. 772]). Монографии ([22, 23]) почти полностью посвящены биномиальным тождествам. В статье ([1]) мы с коллегами применили несколько неочевидных биномиальных формул,

27
способ доказательства которых представляет методический интерес для этого раздела книги. Сами формулы не столь поучительны и не появятся в последующем тексте.
3.9. Лемма. Далее можно считать s ≥ 4, но некоторые фор- мулы после сокращения верны и при меньших s :
1)
s − m m

=
4
m
2
s
·
X
u ≥ 0
s + 1 2u + 1

·
u m

,
2)
σ
X
m = 0
σ − m m

·

2 − s
(s − 1)
2

m
=
(s − 2)
σ+1
− 1
(s − 3) · (s − 1)
σ
;
3)
s
X
m = 0
s − m m

· (2 − s)
m
· (s − 1)
s−2m
=
(s − 2)
s+1
− 1
s − 3
;
4)
s − 1
X
m = 1
m ·
s − m m

·
(2 − s)
m
· (s − 1)
s−2m s − m
=
=
(s − 2) · 1 − (s − 2)
s−1

s − 3
;
5)
s − 1
X
m = 0
s − m m

·
(2 − s)
m
· (s − 1)
s−2m s − m
=
(s − 2)
s
+ 1
s
;
6)
s − 2
X
m = 2
m · (m − 1) ·
s − m m

·
(2 − s)
m
· (s − 1)
s−2m
(s − m) · (s − m − 1)
=
=
(s − 2)
2
· (s − 2)
s−3
− 1

s − 3
;

28 7)
s − 2
X
m = 1
m ·
s − m m

·
(2 − s)
m
· (s − 1)
s−2m
(s − m) · (s − m − 1)
=
= −(s − 2)
s−2
− 1 ;
8)
s − 2
X
m = 1
m ·
s − m m

·
(2 − s)
m
· (s − 1)
s−2m s − m − 1
=
=
1 − (s − 2)
s−2
· (s
2
− 3s + 1)
s − 3
;
9)
s − 2
X
m = 0
s − m m

·
(2 − s)
m
· (s − 1)
s−2m s − m − 1
=
= (s − 3) · (s − 2)
s−2
;
10)
s − 2
X
m = 0
s − m m

·
(2 − s)
m
· (s − 1)
s−2m
(s − m) · (s − m − 1)
=
=
(s − 4) · (s − 2)
s−2
− 1
s
Доказательство. Порядок формул в этой лемме выбран та- ким образом, что последующие выводятся из предыдущих.
Для доказательства формулы 1, собер¨ем левый биноми- альный коэффициент в двойную производящую функцию и преобразуем е¨
е, разложив в сумму простейших дробей по y:

29
X
s ≥ 0
y s
·
s
X
m = 0
s − m m

· x m
=
X
k, m ≥ 0
k m

· x m
· y k+m
=
=
X
k ≥ 0
y k
·
X
m ≥ 0
k m

· x m
· y m
=
X
k ≥ 0
y k
· (1 + xy)
k
=
1 1−y−xy
2
=
=
1 2
√
1 + 4x
·


1 +
√
1 + 4x
1 −
1 +
√
1 + 4x
2
· y
−
1 −
√
1 + 4x
1 −
1 −
√
1 + 4x
2
· y


=
=
1
√
1+4x
·
X
s ≥ 0
1+
√
1+4x
2

s+1
−
1−
√
1+4x
2

s+1
!
· y s
,
Сравнивая коэффициенты при одинаковых степенях y, по- лучаем равенство полиномов от x:
s
X
m = 0
s − m m

· x m
=
=
1
√
1 + 4x
·
1 +
√
1 + 4x
2

s+1
−
1 −
√
1 + 4x
2

s+1
!
=
=
1 2
s+1
·
√
1 + 4x
·
X
k ≥ 0
s + 1
k

·

√
1 + 4x

k
· (1−(−1)
k
) =
=
1 2
s
·
√
1 + 4x
·
X
u ≥ 0
s + 1 2u + 1

·

√
1 + 4x

2u+1
=
=
1 2
s
X
u ≥ 0
s+1 2u+1

·(1 + 4x)
u
=
1 2
s
X
u ≥ 0
s+1 2u+1

X
m ≥ 0
u m

·(4x)
m
=

30
=
1 2
s
·
X
m ≥ 0 4
m
· x m
·
X
u ≥ 0
s + 1 2u + 1

·
u m

Теперь сравнение коэффициентов при x m
да¨ет искомое ра- венство 1. Отметим, что по пути доказано участие указанных биномиальных коэффициентов в интересных суммах:
s
X
m = 0
s − m m

· (−1)
m
=
2
√
3
· sin
(s + 1)π
3
,
s
X
m = 0
s − m m

= F
s
,
где F
s
– числа Фибоначчи (1, 1, 2, 3, . . . ).
Для получения равенства 2 мы используем предыдущую формулу 1:
σ
X
m = 0
σ − m m

·

2 − s
(s − 1)
2

m
=
=
X
m ≥ 0 4
m
2
σ
·
X
u ≥ 0
σ + 1 2u + 1

·
u m

·

2 − s
(s − 1)
2

m
=
=
1 2
σ
·
X
u ≥ 0
σ + 1 2u + 1

·
X
m ≥ 0
u m

·

4 ·
2 − s
(s − 1)
2

m
=
=
1 2
σ
·
X
u ≥ 0
σ + 1 2u + 1

·

1 + 4 ·
2 − s
(s − 1)
2

u
=
=
1 2
σ
·
X
u ≥ 0
σ + 1 2u + 1

·
s − 3
s − 1

2u
=
=
1 2
σ
·
s − 1
s − 3
·
X
u ≥ 0
σ + 1 2u + 1

·
s − 3
s − 1

2u+1
=

31
=
1 2
σ+1
·
s − 1
s − 3
·

1 +
s − 3
s − 1

σ+1
−

1 −
s − 3
s − 1

σ+1
!
=
=
(s − 2)
σ+1
− 1
(s − 3) · (s − 1)
σ
Для доказательства 3 мы используем 2 , полагая σ = s :
s
X
m = 0
s − m m

· (2 − s)
m
· (s − 1)
s−2m
=
= (s − 1)
s
·
s
X
m = 0
s − m m

·

2 − s
(s − 1)
2

m
=
=
(s − 2)
s+1
− 1
s − 3
=
s
X
k = 0
(s − 2)
k
Для доказательства 4 мы используем 2 , полагая σ = s − 2 :
s − 1
X
m = 1
m s − m
·
s − m m

· (2 − s)
m
· (s − 1)
s−2m
=
=
s − 1
X
m = 1
s − m − 1
m − 1

· (2 − s)
m
· (s − 1)
s−2m
=
= (s − 1)
s−2
· (2 − s) ·
s − 2
X
m = 0
s − 2 − m m

·

2 − s
(s − 1)
2

m
=
=
(s − 2) · 1 − (s − 2)
s−1

s − 3

32
Для доказательства 5 мы используем формулы 3 и 4 , за- метив равенство:
1
s − m
=
1
s
·

1 +
m s − m

Тождество 6 доказывается аналогично 4 , с последующей подстановкой σ = s − 4 .
Для доказательства 7 мы используем формулы 4 и 6 , при- меняя равенство:
m
(s − m) · (s − m − 1)
=
=
1
s − 2
·

m s − m
+
m · (m − 1)
(s − m) · (s − m − 1)

Для доказательства 8 мы используем формулы 6 и 7 , за- метив равенство:
m s − m − 1
=
= (s − 1) ·
m
(s − m) · (s − m − 1)
−
m · (m − 1)
(s − m) · (s − m − 1)
Для доказательства 9 мы используем формулы 3 и 8 , за- метив равенство:
1
s − m − 1
=
1
s − 1
·

1 +
m s − m − 1

Тождество 10 следует из 5 и 9 , поскольку верно равенство:
1
(s − m) · (s − m − 1)
=
1
s − m − 1
−
1
s − m
Что завершает доказательство всех формул Леммы 3.9.

33
Следующий пример иллюстрирует пользу комбинаторики в аналитических разделах математики:
3.10. Пример. Возьм¨
ем вещественно гладкую функцию:
f (0) = 0 ; f (x) = exp
−1/x
2
при x 6= 0 .
Е¨
е ряд Маклорена нулевой, но f (x) > 0 при x 6= 0. Об- нуление всех производных f
(k)
(0) да¨ет оценка, следующая из правила Лопиталя: f (x) = o (x k
) при k ≥ 0. Немного сложнее это выводится из явного вида f
(k)
(x) при k ≥ 0. И нахож- дение высших производных является отдельной интересной задачей. Действительно, начальные производные таковы:
exp
−1/x
2

(0)
= 1 · exp
−1/x
2
,
exp
−1/x
2

(1)
=
2
x
3
· exp
−1/x
2
,
exp
−1/x
2

(2)
=
4
x
6
−
6
x
4

· exp
−1/x
2
,
exp
−1/x
2

(3)
=
8
x
9
−
36
x
7
+
24
x
5

· exp
−1/x
2
Индукцией по k легко доказать, что exp
−1/x
2

(k)
= P
k
(1/x) · exp
−1/x
2
, deg P
k
(t) = 3k .
В частности,
P
0
(t) = 1, P
1
(t) = 2t
3
, P
2
(t) = 4t
6
− 6t
4
,
P
3
(t) = 8t
9
− 36t
7
+ 24t
5

34
В общем случае получаем:
P
k
(1/x) = exp {−1/x
2
} · exp {−1/x
2
}

(k)
=
=
X
s ≥ 0 1
s! x
2s
·

X
n ≥ 0
(−1)
n n! x
2n

(k)
=
=
X
s≥0 1
s! x
2s
·
X
n≥0
(−1)
n
(−2n)(−2n−1) . . . (−2n−(k−1))
n! x
2n+k
=
=
k!
x k
·
X
s, n ≥ 0
(−1)
n s! n!
·
−2n k

·
1
x
2(s+n)
=
m=s+n, n ≥ 0
s = m − n ≥ 0
=
=
k!
x k
·
X
m ≥ 0 1
x
2m
·
X
m ≥ n ≥ 0
(−1)
n
(m − n)! n!
·
−2n k

=
=
k!
x k
·
X
m ≥ 0 1
m! x
2m
·
X
m ≥ n ≥ 0
(−1)
n
·
m n

·
−2n k

Таким образом, искомый многочлен имеет вид:
P
k
(t) = k! t k
·
X
m ≥ 0
t
2m m!
·
X
m ≥ n ≥ 0
(−1)
n
·
m n

·
−2n k

Обозначим вспомогательный многочлен:
Q
k
(t) = k! ·
X
m ≥ 0
t m
m!
·
X
m ≥ n ≥ 0
(−1)
n
·
m n

·
−2n k

Тогда получим равенства:
P
k
(t) = t k
· Q
k
(t
2
) , deg Q
k
(t) = k .
Начальные многочлены Q
k
(t) таковы:
Q
0
(t) = 1 , Q
1
(t) = 2t , Q
2
(t) = 4t
2
− 6t ,