Плоские деревья и числа Каталана

Содержание

Слайд 2

Cn – это число правильных расстановок n пар скобок.
Пример:
C0=1
C1=1 ( )
C2=2

Cn – это число правильных расстановок n пар скобок. Пример: C0=1 C1=1
(( )) ( )( )
C3=5 ((( ))) ( )( )( ) ( )(( )) (( ))( ) (( )( ))

Числа Каталана

Слайд 3

C3 = 5
Число путей = Cn
Cn =

Пути в квадрате

((( )))

(( )(

C3 = 5 Число путей = Cn Cn = Пути в квадрате
))

(( ))( )

( )(( ))

( )( )( )

Слайд 4

Дерево – связный граф без циклов
Двоичное дерево – это такое дерево, у

Дерево – связный граф без циклов Двоичное дерево – это такое дерево,
каждой вершины которого не более двух потомков
Пример:
n=0, где n - количество вершин => 0 (пустое дерево)
n=1 => 1 дерево
n=2 => 2
n=3 => 5

Деревья на плоскости

Слайд 5

(( ))( )(( ))
Взаимно однозначное
соответствие

Двоичные деревья

(( ))( )(( )) Взаимно однозначное соответствие Двоичные деревья

Слайд 6

Посчитать количество строго двоичных деревьев с n+1 листами, при n=3

Строго двоичные деревья

Итого:

Посчитать количество строго двоичных деревьев с n+1 листами, при n=3 Строго двоичные
количество деревьев с n+1 листами равно Cn

(( ))( )

( )( )( )

( )(( ))

((( )))

(( )( ))

Слайд 7

Сколько существует троичных деревьев с n вершинами?
n=0 => 1 дерево (пустое)
n=1 =>

Сколько существует троичных деревьев с n вершинами? n=0 => 1 дерево (пустое)
1 дерево
n=2 => 3 дерева
n=3 => 12 деревьев

Троичные деревья

Слайд 8

Сколько существует троичных деревьев с n вершинами?
n=4 => 55 деревьев

Троичные деревья


Сколько существует троичных деревьев с n вершинами? n=4 => 55 деревьев Троичные деревья

Слайд 9

Сколько существует троичных деревьев с n вершинами?

Троичные деревья

Сколько существует троичных деревьев с n вершинами? Троичные деревья

Слайд 10


Tn – всего троичных деревьев с n вершинами.

Троичные деревья

Tn – всего троичных деревьев с n вершинами. Троичные деревья

Слайд 11

сn(p, r) =
Пример:
сn(2, 1) = = = сn
Теорема: Tn =

сn(p, r) = Пример: сn(2, 1) = = = сn Теорема: Tn
сn(3, 1) =

Числа Фусса-Каталана

Слайд 12

tn = сn(3, 1)
tn + 1 = , t0 =

tn = сn(3, 1) tn + 1 = , t0 = 1
1
Тn + 1 = , Т0 = 1

Доказательство теоремы

Слайд 13

Доказательство теоремы
Тn + 1 =

Доказательство теоремы Тn + 1 =

Слайд 14

Следствие : Число строго троичных деревьев с 2n+1 листьями равно сn
n=1 =>

Следствие : Число строго троичных деревьев с 2n+1 листьями равно сn n=1
1 дерево
n=2 => 3 дерева
n=3 => 12

Строго троичные деревья

Имя файла: Плоские-деревья-и-числа-Каталана.pptx
Количество просмотров: 60
Количество скачиваний: 0