Используя коды Прюфера, посчитайте количество деревьев с заданной последовательностью степеней d1,d2,...,do степень vi равна do для i=l,...n

задан 25 Май '17 21:47

Не do а di

(25 Май '17 21:48) Spl35
10|600 символов нужно символов осталось
1

Известно, что номер вершины встречается в коде Прюфера ровно k-1 раз, где k -- степень вершины размеченного дерева. Поэтому число таких деревьев будет равно числу кодов Прюфера длины n-2 в которых число i встречается di-1 раз. А это мультиномиальный коэффициент: $%\frac{(n-2)!}{(d_1-1)!\cdot (d_2-1)! \cdots (d_n-1)!}$% Если не ошибаюсь...

ссылка

отвечен 26 Май '17 2:03

изменен 26 Май '17 2:04

@abc: пусть n=3. Тогда формула даёт 1, но размеченные деревья с тремя вершинами все имеют один и тот же набор степеней 1, 1, 2. И их три штуки.

(26 Май '17 2:35) falcao

@falcao Вы решаете другую задачу, у вас набор степеней 1,1,2 не привязан к конкретным вершинам v1,v2,v3. В исходной задаче на такую привязку дается явное указание: "степень vi равна di для i=l,...n"

(27 Май '17 0:15) abc

@abc: да, я действительно не так понял условие. При том толковании, которое у меня было, получалось что-то сложное. А здесь, конечно, будут перестановки с повторениями, если заданы степени конкретных вершин.

(27 Май '17 0:22) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,476

задан
25 Май '17 21:47

показан
810 раз

обновлен
27 Май '17 0:22

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru