Комбинаторное тождество

[Alexander Evnin]

Я случайно обнаружил такое тождество

$$\sum_{k=1}^{n-1}C_{n-2}^{k-1}k^{k-2}(n-k)^{n-k-2}=2n^{n-3}.$$

1) Попробуйте его доказать.
2) Как узнать, новое ли оно?

[grizzly]

Alexander Evnin в сообщении #1184522 писал(а):

2) Как узнать, новое ли оно?

Ничто не ново под луною

Я не первый раз отвечаю на подобные вопросы. И пока мне всегда хватает трёх источников:
1. Риордан, Комбинаторные тождества.
2. Этот обзор. По ссылке первый том обзора. Меняя очевидным образом в адресной строке номер тома, можно найти ещё несколько.
3. А также эта замечательная книга. По последней ссылке очень похожее на Ваше тождество значится под номером (9.11.1).

PS. Избыточная информации в этом ответе дана с целью ссылаться на это сообщение в будущем.

[Alexander Evnin]

Спасибо за полезные ссылки!
Да, тождество 9.11.1 похоже на моё, но всё-таки - другое!

[grizzly]

Alexander Evnin в сообщении #1184644 писал(а):

Да, тождество 9.11.1 похоже на моё, но всё-таки - другое!

Да, другое. Оно интересное и красивое, я не спорю.
Но. Хотя я не спец. в предмете (мне просто нравятся комбинаторные тождества), мне кажется, что ноги должны расти из того же тождества Абеля. По ссылке 2 в конце тома 4 ещё посмотрите (в районе 10.24) -- тоже похоже и в более обобщённом виде. Но Ваше пока не выходит.

[grizzly]

Alexander Evnin
Я попытался избавиться от двойки в правой части равенства. Успешно. Я использую тривиальное свойство треугольника $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$. С учётом этого и после очевидных сдвигов, получим:

$$\sum_{k=0}^{n}C_{n}^{k}(k+2)^{k}(n-k+1)^{n-k-1}=(n+3)^{n}.$$

Как по мне, стало даже чуть эстетичнее Оно равносильно стартовому и на Абеля стало ещё больше похоже.

[Alexander Evnin]

В кн. С. К. Ландо. Лекции о производящих функциях, изд. 3, 2007 на с. 115
обнаружил тождество Абеля

$$\sum_{i+j=n, i,j>0}C_n^ii^{i-1}j^{j-1}=2(n-1)n^{n-2},$$

которое несложно преобразуется к моему тождеству. Так что, действительно, ничто не ново под Луной:)
Могу только заметить, что у Ландо доказательство весьма громоздкое (занимает две страницы), моё же очень короткое.

Вот оно.

Найдём вероятность $p$ того, что две случайные вершины дерева (с $n$ вершинами) смежны.
С одной стороны, $p=\frac{n-1}{C_n^2}=\frac{2}{n}$. С другой стороны, подсчитаем количество помеченных $n$-вершинных деревьев, содержащих ребро $uv$. Пусть после удаления ребра $uv$ вершина $u$ входит в дерево с $k$ вершинами. Тогда это дерево можно составить $C_{n-2}^{k-1}k^{k-2}$ способами. После этого дерево с вершиной $v$ составляется $(n-k)^{n-k-2}$ способами. Значит, доля деревьев с ребром $uv$ среди всех помеченных деревьев с $n$ вершинами равна

$$\frac{\sum_{k=1}^{n-1}C_{n-2}^{k-1}k^{k-2}(n-k)^{n-k-2}}{n^{n-2}}.$$

Приравняв два выражения для $p$, и получим заявленное мною тождество.

[grizzly]

Alexander Evnin
Здорово!
Зря я зациклился на втором вопросе, забыв, что мы в Олимпиадном разделе. Но всё равно было интересно, да ещё такая красивая развязка

-- 15.01.2017, 17:07 --

И за книгу спасибо!

[Alexander Evnin]

Про тождество Абеля написано и здесь: С. К. Ландо. Введение в дискретную математику. 2012