6
$\begingroup$

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?

$\endgroup$

1 Answer 1

16
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you very much! Your solution certainly wasn't obvious to me even in hindsight. $\endgroup$
    – Simd
    Apr 19, 2013 at 18:20
  • $\begingroup$ You're welcome! I actually rather enjoyed working it out. $\endgroup$
    – Todd Trimble
    Apr 19, 2013 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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