Раскрашивание корневого дерева

[andrey_hse]

Добрый день! Имеется простая, на первый взгляд, задачка, но не могу понять, где у меня нарушается логика: "Каждая вершина дерева независимо от остальных окрашивается в один из m цветов. Пусть $q(n,m)$ - количество раскрашенных деревьев с n вершинами. Доказать, что $q(3,m)=2m+10C_m^2+9C_m^3$".
В общем, я рассуждаю так: 3 вершины => всего возможно 3 дерева ($n^{n-2}$). Рассмотрим для начала 3 цвета. По формуле должно получиться 45 цветов. Итак, обозначаю вершины как $\{1,2,3\}$, цвета - как $\{a,b,c\}$.
1. Допустим, корнем является вершина 1, а листьями - вершины 2 и 3 (порядок не имеет значение). Тогда перебираем все варианты для цветов: $a-a-a$, $a-a-b$, $a-a-c$, $b-a-b$, $b-a-c$, $c-a-c$, $a-b-a$, $a-b-b$, $a-b-c$, $b-b-b$, $b-b-c$, $c-b-c$, $a-c-a$, $a-c-b$, $a-c-c$, $b-c-b$, $b-c-c$, $c-c-c$. Итого 18 вариантов для 1 дерева.
2. Аналогично, для двух других деревьев, тем самым получаем 54 варианта.
Очевидно, что в каком-то месте я просчитал одни и те же варианты несколько раз. Только вот не могу понять, где. Помогите разобраться в этом деле, пожалуйста.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Дооформите, пожалуйста, формулы $\TeX$ом.
Множество набирается так: \{1,2,3\}, раскраски тоже выпишите в виде формул (русские буквы замените на латинские).

andrey_hse в сообщении #718210 писал(а):

q(n,m)

Это тоже следует оформить.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[AKM]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: не указана.

[provincialka]

Очень странная формула: она подходит только для $m\ge3$. Может, индексы перепутались местами? Может, цветов должно быть меньше, чем вершин? Хотя, вы же взяли оба числа за 3...
Вообще в таких задачах надо четко понимать, какие решения считать "разными".

[andrey_hse]

Для следующего поколения :)

Будем раскрашивать корневое дерево, используя 1, 2 или 3 различных краски.
1. Начнем с одной краски из $m$ возможных. Фиксируем корень дерева и рассматриваем два случая: когда ветки отходят от корневой вершины и когда вершины соединены последовательно. Каждое из этих деревьев можно раскрасить однозначно. Таким образом получаем $2m$ вариантов раскраски при помощи одной краски.
2. Теперь используем 2 краски из m, то есть делаем выборку $C_{m}^{2}$. И снова рассматриваем 2 случая расположения вершин: когда ветки отходят от корневой вершины и когда вершины соединены последовательно. В первом случае корневую вершину можно раскрасить двумя способами, а оставшиеся ветки покрасить либо в выбранные 2 цвета из m (порядок не имеет значения), либо покрасить в цвет, отличный от вершины. Таким образом получаем $4C_{m}^{2}$ способов раскраски для первого случая. Для второго расположения вершин: опять корень можно покрасить двумя способами, а для оставшихся вершин перебираем возможные варианты покраски, избегая совпадения цветов для всех трех вершин (3 способа для каждого цвета корневой вершины). В итоге имеем еще $6C_{m}^{2}$ раскрашенных корневых деревьев, что в сумме дает $10C_{m}^{2}$ деревьев.
3. Наконец, используем для раскраски 3 цвета, которые можно выбрать $C_{m}^{3}$ способами. Фиксируя цвет корневой вершины, получаем единственный вариант, если остальные ветки исходят из этой вершины, и 2 варианта, если вершины соединены последовательно. То есть, итого $3\cdot3\cdotC_{m}^{3}=9C_{m}^{3}$.

Итоговая формула: $q(3,m)=2m+10C_{m}^{2}+9C_{m}^{3}$. Что и требовалось доказать.

[ilya_msu]

А для той же задачи, но c 4 вершинами, доказать формулу $q(4,m)=4m+44C^2_m+64C^4_m$, почему там нет слагаемого с вариантами для 3 цветов? 1, 2, и 4 есть, а 3 нету.