Из работ по дискретной математике
(
например
,
из работы
[3])
из
-
вестно
,
что одной из интерпретаций последовательности Каталана
1
является число бинарных деревьев поиска с
n
+ 1
“
листьями
”.
Таким
образом
,
число бинарных деревьев поиска с
n
“
листьями
”
определяет
-
ся
(
n
−
1)
-
м числом последовательности Каталана
.
Поскольку
“
листья
”
в рассматриваемом дереве поиска не упорядочены
,
то можно менять
их порядок любым способом для заданного дерева поиска
.
Следова
-
тельно
,
существует
n
!
различных расположений
“
листьев
”.
Поэтому
получим следующее число деревьев поиска
:
n
!
C
n
−
1
=
n
!
(
n
+ 1
−
1)
µ
2
n
−
2
n
−
1
¶
=
=
(
n
−
1)!(2
n
−
2)!
(
n
−
1)!(2
n
−
2
−
n
+ 1)!
=
(2
n
−
2)!
(
n
−
1)!
,
(3)
C
n
=
1
(
n
+ 1)
µ
2
n
n
¶
.
Случай
2.
Кустовое дерево
,
линейный запрос
.
Поскольку линейная
цепочка может быть разорвана на
k
-
й позиции
(
на
k
-
м отношении
)
и
любая ее часть может быть левым входом
,
то число деревьев поиска в
этом случае описывается выражением
y
n
=
n
−
1
X
k
=1
2
y
k
y
n
−
k
,
(
4
)
где
y
1
= 1
.
В работе
[2]
показано
,
что справедливо следующее соотношение
:
y
n
= 2
n
−
1
x
n
/n
!
.
Таким образом
,
число деревьев поиска в рассматрива
-
емом случае может быть оценено формулой
y
n
=
2
n
−
1
n
!
(2
n
−
2)!
(
n
−
1)!
.
(
5
)
1
Последовательность Каталана
—
последовательность вида
(1, 2, 5, 14, 42, 132,
429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845,
. . .
),
названная по
имениЮджина Чарльза Каталана
(1814–1894).
Последовательность Каталана
,
напри
-
мер
,
определяет число правильных скобочных структур длины
2
n
и определяется сле
-
дующей рекуррентной формулой
:
k
n
=
n
−
1
X
m
=0
µ
n
m
¶
k
m
k
n
−
m
−
1
.
Производящая функ
-
ция
K
x
=
k
0
+
k
1
x
+
k
2
x
2
+
. . .
последовательности Каталана удовлетворяет условию
xK
2
x
−
K
x
+ 1 = 0
.
Решая это уравнение и используя условие
K
(0) = 1
,
получаем
функцию
K
x
=
1
− √
1
−
4
x
2
x
;
разложив функцию
√
1
−
4
x
в ряд
,
получаем выраже
-
ние для
k
n
:
k
n
=
1
n
+ 1
µ
2
n
n
¶
.
94 ISSN 0236-3933.
Вестник МГТУ им
.
Н
.
Э
.
Баумана
.
Сер
. "
Приборостроение
". 2004.
№
1
