Домівка > Математика > Кількість відмінних двійкових дерев з n вершинами

Кількість відмінних двійкових дерев з n вершинами

Кількість відмінних двійкових дерев з n позначеними вершинами

Для двійкового дерева з n вершинами, кількість ребер становить n-1. Отже, цю задачу можна звести до кількості варіантів розташування n-1 ребер у n вершин. Ребро можна зробити або лівим, або правим. Тому, для першого ребра ми маємо 2n варіантів, для другої 2n-1 і так далі. З цього, для n-1 вершин загалом розташувань буде

= 2n\times(2n-1)\times(2n-2)\times\dots\times(2n-(n-2))

= 2n\times(2n-1)\times(2n-2)\times\dots\times(n+2)

=\frac{(2n)!}{(n+1)!}

Кількість відмінних двійкових дерев з n невідрізненними вершинами

Тобто тут нас цікавить кількість структурно відмінних дерев.

Якщо вершини однакові (непозначені), тоді кількість відмінних двійкових дерев буде такою ж як і в попередньому питанні поділеною на кількість перестановок для n вершин, а саме n!.

\frac{(2n)!}{(n+1)!n!}=\frac{1}{n+1}{2n\choose n}

Це є число Каталана #n, яке асимптотично дорівнює \frac{4^n}{n^{3/2}\sqrt{\pi}}.

Погляд з іншого боку

Інакше, ми можемо розбити наше дерево на верхівку і два дочірніх дерева. Позначимо b_n кількість відмінних двійкових дерев з n вершинами. Тоді

b_n = \Sigma_{k = 0}^{n-1} b_kb_{n-k}.

Advertisements
Категорії:Математика Позначки:
  1. Коментарів ще немає.
  1. No trackbacks yet.

Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: