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

Мы знаем формулу Кэли, что на n вершинах можно построить n^(n-2) различных дерева. Способов построить две древесные компоненты:

1) Выбираем 1 вершину из 6 и строим два дерева на 1 вершине и 5 вершинах. Способов построить: C(6,1) * 1 * 5^3

2) Выбираем 2 вершины из 6 и строим два дерева на 2 вершинах и 4 вершинах. Способов построить: C(6,2) * 2^0 * 4^2

3) Выбираем 3 вершины из 6 и строим два дерева на 3 вершинах и 3 вершинах. Способов построить: (1/2) * C(6,3) * 3^1 * 3^1

Но почему в третьем случае возникает множитель 1/2 ? Не могу понять...

задан 25 Июн '19 14:22

изменен 25 Июн '19 14:23

10|600 символов нужно символов осталось
1

Когда множество разбивается на 2 подмножества одинакового размера, возникает эффект "пересчета". Чтобы это увидеть, попробуйте расписать число разбиений 4 занумерованных вершин на 2 компоненты. Получится 3 варианта, а не 6, т.к. мы не упорядочиваем компоненты в разбиениях. Например, разбиение [{1, 2}, {3,4}] и разбиение [{3 4}, {1,2}] идентичны.

В общем случае, при подсчете разбиений на подмножества так, что k из них одинакового размера, нужно делить на k!

ссылка

отвечен 25 Июн '19 22:04

изменен 25 Июн '19 22:47

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,268
×540

задан
25 Июн '19 14:22

показан
157 раз

обновлен
25 Июн '19 22:47

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

по почте:

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

по RSS:

Ответы

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

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