Дискретная математика доказать тождество

[AlexeIII]

$\[ n(n + 1)^{n - 1} = \sum\limits_{k = 1}^n {C_n^k k^{k - 1} (n - k + 1)^{n - k} } \] $
Помогите пожалуйста...

[gris]

Справа и слева одинаковое число слагаемых. Может быть они и равны все попарно? Что если расписать биномиальные коэффициенты через факториалы?

-- Вт май 19, 2009 20:45:09 --

Например, для $n=3$:
Левая часть

$$3(3+1)^2=27+18+3=48$$

Правая часть

$$C_3^1\cdot 1^0\cdot 3^2+C_3^2\cdot 2^1\cdot 2^1+C_3^3\cdot 3^2\cdot 1^0=27+12+9=48$$

Нет, не равны попарно...

-- Вт май 19, 2009 21:34:20 --

Попробуем для $n=4$:
Левая часть

$$4(4+1)^3=256+192+48+4=500$$

Правая часть

$$C_4^1\cdot 1^0\cdot 4^3+C_4^2\cdot 2^1\cdot 3^2+C_4^3\cdot 3^2\cdot 2^1+C_4^4\cdot 4^3\cdot 1^0=256+108+72+64=500$$

Может быть по индукции попробовать?

[AlexeIII]

Сейчас еще попытаюсь глянуть на индукцию, просто мне кажеться, что скорее всего нужно придумать какуюто хитрую группировку или както разбить на суммы.

У меня, както, не выходит

[EtCetera]

Вот какие соображения можно здесь применить:
1. Для левой части
$n(n+1)^{n-1}=$ $\sum_{m=1}^n(n+1)^{n-1}=$ $\sum_{m=1}^n(m+n+1-m)^{n-1}=$ $\sum_{m=1}^n\sum_{k=0}^{n-1}C_{n-1}^km^k(n+1-m)^{n-1-k}=$ $\sum_{m=1}^n\sum_{k=1}^nC_{n-1}^{k-1}m^{k-1}(n+1-m)^{n-k}=?$
Сходство с правой частью достаточно наглядно.
2. Для правой части (будем обозначать ее $S_n$)
$S_n=\sum_{k=1}^nC_n^kk^{k-1}(n-k+1)^{n-k}=$ $n!\sum_{k=1}^n\frac{k^{k-1}}{k!}\frac{(n+1-k)^{(n+1-k)-1}}{(n-k)!}=$ $(n+1)!\sum_{k=1}^n\frac{k^{k-1}}{k!}\frac{(n+1-k)^{(n+1-k)-1}}{(n+1-k)!}-n!\sum_{k=1}^n\frac{k^{k-1}}{(k-1)!}\frac{(n+1-k)^{(n+1-k)-1}}{(n+1-k)!}=$ $\left[\begin{array}{c}\tilde k=n+1-k\\k=n+1-\tilde k\end{array}\right]=$ $(n+1)!\sum_{k=1}^n\frac{k^{k-1}}{k!}\frac{(n+1-k)^{(n+1-k)-1}}{(n+1-k)!}-n!\sum_{\tilde k=1}^n\frac{(n+1-\tilde k)^{(n+1-\tilde k)-1}}{(n-\tilde k)!}\frac{{\tilde k}^{\tilde k-1}}{{\tilde k}!}=$ $(n+1)!\sum_{k=1}^n\frac{k^{k-1}}{k!}\frac{(n+1-k)^{(n+1-k)-1}}{(n+1-k)!}-S_n$
Откуда:
$S_n=\frac{(n+1)!}{2}\sum_{k=1}^n\frac{k^{k-1}}{k!}\frac{(n+1-k)^{(n+1-k)-1}}{(n+1-k)!}=$ $\frac{1}{2}\sum_{k=1}^nC_{n+1}^kk^{k-1}(n+1-k)^{(n+1-k)-1}$
Последняя сумма отличается несколько бОльшей симметричностью, чем исходная (а значит, может представлять бОльшие возможности для маневра). Например:
$S_{2m}=\sum_{k=1}^mC_{2m+1}^kk^{k-1}(2m+1-k)^{(2m+1-k)-1}$ (симметричные члены дублируются)
$S_{2m+1}=\sum_{k=1}^mC_{2m+2}^kk^{k-1}(2m+2-k)^{(2m+2-k)-1}+\frac{1}{2}C_{2m+2}^{m+1}(m+1)^{2m+2}$
Однако эти соображения являются просто руководством к действию. Может быть из них можно извлечь что-либо полезное, может быть - нет (я пока не знаю ).

[RIP]

С помощью производящих рядов равенство доказывается просто. Если обозначить

$$f(z)=\sum_1^\infty\frac{n^{n-1}}{n!}z^n,\quad g_a(z)=\sum_0^\infty\frac{(n+a)^n}{n!}z^n,$$

то нужно доказать

$$f(z)g_1(z)=zg_2(z).$$

Но известно (доказывается с помощью ряда Бюрмана-Лагранжа), что

$$f(ze^{-z})=z,\quad g_a(ze^{-z})=\frac{e^{az}}{1-z}.$$

Это первое, что приходит в голову. Но должно как-то по-простому решаться. Наверняка, есть какая-то комбинаторная интертрепация.

-- Ср 20.5.2009 02:18:06 --

Впрочем, это из пушки по воробьям. Первым должно приходить на ум такое решение. Если раскрыть $(n+1-k)^{n-k}$ по биному Ньютона и перегруппировать слагаемые, то всё сводится к доказательству равенства

$$\sum_{k=1}^m(-1)^k\binom mkk^{m-1}=0,\quad m\ge2.$$

Последнее равенство можно доказать, например, разложив $\frac{x^{m-1}}{(x+1)(x+2)\ldots(x+m)}$ на простейшие дроби и подставив $x=0$.

Но всё-таки интересно, каков комбинаторный смысл у этого тождества.

[AlexeIII]

Всем спасибо за ответы, разобрался)

Как вариант, просто обобщенная формула биномиальных коэффициентов Абеля