Is there an elementary proof of this identity?


$$n + 1 - \sum\_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(n-k)^{n+1-k}}{n^{n}} =1 + \sum\_{k=1}^n \frac{n!}{(n-k)!n^k}\;?$$


The term on the right is the average time to find a duplicate birthday from the classic Birthday Problem and the sum on the left is a special case of this [sum](https://math.stackexchange.com/questions/361452/asymptotics-of-sum-of-binomials). As a sanity check, if you compute the answers numerically (exactly) for small $n$ they are exactly the same.


The numerator of the sum on the left is $n^{n+1}-Q(n)n^n$ (Q(n) is called Ramanujan's function by Knuth) according to [A219706](http://oeis.org/A219706) and [A063169](http://oeis.org/A063169). This immediately gives the identity as the term on the right is $1+Q(n)$. Am I just missing a simple direct proof of their equality too?



Elementary proof for identity involving sums of binomials
After canceling $1$'s and clearing denominators, the identity can be rearranged to this one: 


$$n^{n+1} = \sum\_{k=1}^{n} \binom{n}{k} k^{k-1} (n-k)^{n-k+1} + \sum\_{k=1}^n \binom{n}{k} n^{n-k} k!$$ 


and now we proceed to give a bijective proof. The left side counts data of the form 


* Endofunction $f: S \to S$ on an $n$-element set $S$, plus a distinguished point $s$ of $S$.


Draw the endofunction as a directed graph, where an edge is drawn from $x$ to $y$ if $f(x) = y$. This graph can be decomposed into connected components, and there are two disjoint possibilities: 


* Case 1: either $s$ belongs to a cycle (this includes the case where $f(s) = s$), or
* Case 2: removal of the edge from $s$ to $f(s)$ produces a disconnection of the connected component of $s$.


Let us count the possibilities for the first case. The cycle to which $s$ belongs defines a $k$-element set, say, and gives a structure of linear order on this set, namely the ordering $s, f(s), \ldots, f^{k-1}(s)$. There are $k!$ ways of giving such a linear order, and this order describes the restriction of $f$ to the cycle containing $s$. The remainder of $f$ is just given by some function $S \backslash \mathrm{cycle}(s) \to S$ on the complement, of which there are $n^{n-k}$ many. Thus the second sum of the asserted identity counts the possibilities for case 1. 


For case 2, consider the set of elements $x$ such that $f^{(j)}(x) = s$ for some $j \geq 0$. This defines some $k$-element subset, and the graph of the restriction of $f$ to this subset is described as a rooted tree with root at $s$. The number of such rooted tree structures on a $k$-element set is $k^{k-1}$, by [Cayley's theorem](http://en.wikipedia.org/wiki/Cayley%27s_formula). Then, the rest of $f$ is given by its restriction to the complement of this $k$-element set (notice it takes the complement to itself) -- there are $(n-k)^{n-k}$ possibilities here -- *plus* knowledge of the element $f(s)$ which belongs to this $(n-k)$-element set. Thus the first sum on the right side of the identity counts the number of possibilities for case 2, and we are done. 


