6

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?

Community
  • 1
Simd
  • 3,195

1 Answers1

16

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.

Todd Trimble
  • 52,336