Раскрашивание корневых деревьев

[ilya_msu]

Здравствуйте! Задача по графам, Пусть $q(n,m)$ - количество раскрашенных деревьев с n вершинами, доказать формулу $q(4,m)=4m+44C^2_m+64C^4_m$. Я уже нашел похожий пример для 3 вершин, все понятно, однако тут возник вопрос - почему нет слагаемого для случая с тремя цветами. Если подбирать варианты, то для 1 2 и 4 цветов у меня все получается.

[patzer2097]

ilya_msu в сообщении #864403 писал(а):

Пусть $q(n,m)$ - количество раскрашенных деревьев с n вершинами, доказать формулу $q(4,m)=4m+44C^2_m+64C^4_m$.

сомневаюсь, что раскрашенных деревьев с $4$ вершинами бывает только $4$ штуки. Что бы эта формулировка не значила

[ilya_msu]

patzer2097 в сообщении #864641 писал(а):

ilya_msu в сообщении #864403 писал(а):

Пусть $q(n,m)$ - количество раскрашенных деревьев с n вершинами, доказать формулу $q(4,m)=4m+44C^2_m+64C^4_m$.

сомневаюсь, что раскрашенных деревьев с $4$ вершинами бывает только $4$ штуки. Что бы эта формулировка не значила

Пример для случая трех вершин topic71599.html
Там хорошо объяснен алгоритм, однако в этой формуле нету слагаемого для случая когда 3 цвета взяты из m.
Тут никто и не говорил про 4 штуки :)

[patzer2097]

ilya_msu в сообщении #864647 писал(а):

Тут никто и не говорил про 4 штуки :)

Вы писали

ilya_msu в сообщении #864403 писал(а):

Пусть $q(n,m)$ - количество раскрашенных деревьев с n вершинами, доказать формулу $q(4,m)=...$

[ilya_msu]

patzer2097 в сообщении #864648 писал(а):

ilya_msu в сообщении #864647 писал(а):

Тут никто и не говорил про 4 штуки :)

Вы писали

ilya_msu в сообщении #864403 писал(а):

Пусть $q(n,m)$ - количество раскрашенных деревьев с n вершинами, доказать формулу $q(4,m)=...$

Я писал про 4 вершины, а деревьев совсем не 4 получается из формулы, если конечно m не 1. Посмотрите ссылку с примером для 3...
Вот условие целиком : Каждая вершина дерева независимо от остальных окрашивается в один из m цветов. Пусть $q(n,m)$ - количество раскрашенных деревьев с n вершинами, доказать формулу $q(4,m)=4m+44C^2_m+64C^4_m$

[patzer2097]

ilya_msu в сообщении #864701 писал(а):

Вот условие целиком

Понимаете, если вы хотите, чтобы Вас поняли, то условие надо сразу писать "целиком".

ilya_msu в сообщении #864701 писал(а):

Каждая вершина дерева независимо от остальных окрашивается в один из m цветов.

Может, Вы не это имели в виду? В такой формулировке число раскрашенных деревьев равно $m^n$, умноженному на число нераскрашенных. Что с Вашей формулой для $q(4,m)$ соотносится плохо

[ilya_msu]

patzer2097 в сообщении #864865 писал(а):

ilya_msu в сообщении #864701 писал(а):

Вот условие целиком

Понимаете, если вы хотите, чтобы Вас поняли, то условие надо сразу писать "целиком".

ilya_msu в сообщении #864701 писал(а):

Каждая вершина дерева независимо от остальных окрашивается в один из m цветов.

Может, Вы не это имели в виду? В такой формулировке число раскрашенных деревьев равно $m^n$, умноженному на число нераскрашенных. Что с Вашей формулой для $q(4,m)$ соотносится плохо

Да, виноват, но сути это не меняет, если Вам не понятна формула то посмотрите пример для 3 по ссылке выше. Там хорошо объяснена логика. Для 4 вершин есть 4 варианта выбора корня и структуры. Если есть m цветов то всего можно сделать 4m деревьев, в случае когда используем один цвет. Это о первом слагаемом. Остальные так же рассчитываются, я же задаю вопрос - Почему нету слагаемого для случая выбора трех цветов из m??

[ilya_msu]

Если точнее определить вопрос, то вот такая задача, нет причин сомневаться в условии, я знаю как решать, получаю практически ту же формулу, но там еще должно быть слагаемое с сочетанием из m по 3, помноженное на число вариантов для этого случая, т.е когда используем три цвета из m. Почему его нет в условии? Вариант номер раз - ошибка, вариант номер два - я чего-то важного не понял или не знаю.