Здравствуйте! Помогите, пожалуйста, доказать тождество, будьте добры

$$\sum_{i=1}^{n-1}\binom{n}{i}i^{n-i-1} (n-i)^{i-1} = 2 n^{n-2}$$

задан 28 Июн 15:31

изменен 1 Июл 9:47

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

Любое дерево раскрашивается в $%2$% цвета правильным образом.

Обозначим через $%F (m,n) -$% число деревьев имеющих $%n $% белых и $%m $% черных вершин.

Докажем , что : $%\boxed {F (m,n)=n^{m-1}m^{n-1}}$%

$$F (1,n)=1\ ,\ F (2,n)=n\cdot 2^{n-1}$$

Пусть $%m\le n $% .Тогда существует висячая белая вершина.

Поэтому:

$$F (n,m)=C_n^1\cdot m\cdot F (m,n-1)-C^2_n\cdot m^2\cdot F (m,n-2)+C^3_n \cdot m^3\cdot F (m,n-3)-...=$$ $$=m^{n-1}(C^1_n \cdot (n-1)^{m-1}-C^2_n\cdot (n-2)^{m-2}+C^3_n \cdot (n-3)^{m-2}-...)=m^{n-1}\cdot n^{m-1}$$

т.к. число способов разместить $%m-1 $% предмет по $%n$% корзинам так, чтобы не было пустых корзин:

$$n^{m-1}-C^1_n \cdot (n-1)^{m-1}+C^2_n\cdot (n-2)^{m-2}-C^3_n \cdot (n-3)^{m-2}+...)=0 \ \ \ \ ( m-1 < n)$$

Поэтому удвоенное число деревьев на $%n $% вершинах :

$$2T_n=\sum_{i=1}^{n-1}C_n^i\cdot F (i, n-i)=\sum_{i=1}^{n-1}C_n^i\cdot i^{n-i-1}(n-i)^{i-1}=2n^{n-2}$$

Последнее верно по формуле Келли для числа деревьев на $%n$% помеченнных вершинах.

ссылка

отвечен 1 Июл 22:24

изменен 1 Июл 22:30

Sergic Primazon , большое Вам спасибо! Вы мне очень помогли!

(1 Июл 23:02) Serg
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×702
×155

задан
28 Июн 15:31

показан
81 раз

обновлен
1 Июл 23:02

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

по почте:

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

по RSS:

Ответы

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

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