2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Графы. Раскрашивание деревьев
Сообщение08.05.2011, 23:14 
Каждая вершина дерева независимо от остальных окрашивается в один из $m$ цветов. Пусть $q(n,m)$ количество раскрашенных корневых деревьев с $n$ вершинами. Доказать, что $q(4,m)=4m+44C^2_m+64C^4_m$.

Вообще не понятно, что за ерунда, а что, если у нас $m<4$?
И почему нельзя рассуждать так: всего у нас $m^4$ способов раскрасить 4 вершины разными цветами. Также имеем $n^{n-2}$ различных деревьев, следовательно, результат - перемножение: $m^4 n^{n-2}$.

 
 
 
 Re: Графы. Раскрашивание деревьев
Сообщение09.05.2011, 01:27 
Аватара пользователя
Если $m>n$, то $C_n^m = 0$.
Деревья неупорядоченные, т.е. если из вершины выходит несколько веток, мы можем их переставлять, и такое дерево считается 1 раз.

 
 
 
 Re: Графы. Раскрашивание деревьев
Сообщение09.05.2011, 11:28 
Аватара пользователя
 i  Возвращено из "Карантина".

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group