Лемма 2.
Для любого
n
1
и
m n
выполнено соотношение
D
m
(
x
n
) =
k
0
+
...
+
k
d
=
n,
0
k
1
+2
k
2
+
...
+
dk
d
m
−
n
n
!
k
0
!
. . . k
d
!
N
−
1
N
k
1
+2
k
2
+
...
+
dk
d
N
m
−
n
.
(5)
Доказательство леммы 2.
Для любых
x
n
и
Y
m
существует не
более одного варианта вложения отрезка
x
n
в отрезок последователь-
ности
Y
m
вспомогательным способом. Это свойство позволяет найти
число
D
m
(
x
n
)
следующим образом. Выберем числа
k
i
,
0
k
i
n
,
i
= 0
, . . . , d, k
0
+
. . .
+
k
d
=
n,
и будем считать, что из
n
знаков отрезка
последовательности
x
n
некоторые
k
0
знаков “вставлены” вспомога-
тельным способом сразу за предшествующим “вставленным” знаком
отрезка
x
n
, некоторые
k
1
из оставшихся знаков “вставлены” с пред-
варительным пропуском одного знака, некоторые
k
2
из оставшихся
знаков “вставлены” с предварительным пропуском двух знаков и так
далее. Наконец, оставшиеся
k
d
знаков “вставлены” с предваритель-
ным пропуском
d
знаков (при этом считаем, что знак
x
1
“вставлен” с
предварительным пропуском
l
знаков, если
j
1
=
l
−
1
). Число отрезков
Y
m
длины
n
+
k
1
+ 2
k
2
+
. . .
+
dk
d
, в которые данный отрезок по-
следовательности
x
n
может быть вложен вспомогательным образом,
равно
C
k
0
n
C
k
1
n
−
k
0
C
k
2
n
−
k
0
−
k
1
. . . C
k
d
k
d
(
N
−
1)
k
1
+2
k
2
+
...
+
dk
d
.
Последние
m
−
n
−
k
1
−
2
k
2
−
. . .
−
dk
d
символов отрезка
Y
m
могут быть выбраны произвольно, т.е.
N
m
−
n
−
k
1
−
2
k
2
−
...
−
dk
d
способами.
В итоге, суммируя по
k
1
+ 2
k
2
+
. . .
+
dk
d
в диапазоне от 0 до
m
−
n
,
получаем
D
m
(
x
n
) =
k
0
+
...
+
k
d
=
n,
0
k
1
+2
k
2
+
...
+
dk
d
m
−
n
n
!
k
0
!
. . . k
d
!
N
−
1
N
k
1
+2
k
2
+
...
+
dk
d
N
m
−
n
.
Лемма 2 доказана.
Согласно неравенству
P
m
(
x
n
)
P
d
m
(
x
n
)
и лемме 2 в кач ествениж-
ней оценки для вероятности
P
d
m
(
x
n
)
можно взять вероятность
P
m
(
x
n
) =
D
m
(
x
n
)
N
m
=
=
1
N
n
k
0
+
...
+
k
d
=
n,
0
k
1
+2
k
2
+
...
+
dk
d
m
−
n
n
!
k
0
!
. . . k
d
!
N
−
1
N
k
1
+2
k
2
+
...
+
dk
d
.
Эта оценка не зависит от
x
n
и согласно лемме 1 достигается на
отрезках из одинаковых знаков. Таким образом, теорема 1 доказана.
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2012. № 2
7
