Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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. 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 and 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?

share|improve this question
add comment

1 Answer 1

up vote 14 down vote accepted

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. 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.

share|improve this answer
    
Thank you very much! Your solution certainly wasn't obvious to me even in hindsight. –  motl737 Apr 19 '13 at 18:20
    
You're welcome! I actually rather enjoyed working it out. –  Todd Trimble Apr 19 '13 at 19:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.