Expected tail and head length of $\rho$ for a finite random function Let $F: D \rightarrow D$ be a random function on finite domain $D$ of size $n$.  It is well-known that, from any $x \in D$, iterating $F$ on $x$ traces out a sequence of values $x, F(x), F(F(x)), \ldots$ that must eventually repeat (since $D$ is finite) and resembles a Greek "$\rho$".  The expected number of total elements in this $\rho$ is $\sqrt{n\pi/2}$ with half being on the tail and half on the head.  I've seen this stated in several places, but cannot find a proof.
Illustration: In order to clarify what I'm asking (since the comments make it clear that this might be useful), fix an integer $n$.  Uniformly sample $a_0 \in [1,n]$ and make a vertex with label $a_0$.  Do this again, obtaining a vertex labeled $a_1$ and make a directed edge from $a_0$ to $a_1$ (this does not preclude $a_0 = a_1$).  The pigeon-hole principle tells us that eventually we will create a cycle in this digraph; we terminate the process when this occurs. Clearly the graph will look like the letter $\rho$: the "tail" is the part of the graph before we enter the cycle (the tail might have length zero, of course), and the "head" is the is part of the graph comprising the cycle.

My question is this: what is the expected length of the tail and head, in terms of $n$.  Asymptotically, the answer is known to be $\sqrt{n\pi/8}$, but I cannot find a derivation.
 A: Well, I've spent some time on this and I have (sort of) got it figured out.
This question has roots in the "birthday problem" where we ask how many people we must have in a group before the probability that at least two share a birthday exceeds $1/2$.  The answer is 23.  (This assuming that birthdays are uniform, which they're not.  The non-uniformity only lowers the number of people required.)
With a little thought, we can see that the length of the $\rho$ as asked above is equivalent to a birthday-like question: how many random points do we need before we repeat ourselves.  We can ask this in a few different forms: what $t \in [1,n]$ do we need before we exceed probability $p$, what is the expected number of points needed to see a collision, etc.
Let's focus on the question asked: expectation.  The probability that there is no collision after $t$ trials is clearly 
$$\frac{n}{n} \frac{n-1}{n} \frac{n-2}{n} \cdots \frac{n-t+1}{n} $$
Now let $X$ be the R.V. for the number of trials until we repeat for the first time.  Then the probability above is $\Pr[X > t]$ so $E[X]$ is 
$$ \sum_{t \geq 0} \frac{n}{n} \frac{n-1}{n} \frac{n-2}{n} \cdots \frac{n-t+1}{n} $$
(I'm using an alternative formulation of expectation here).
This is all well-and-good, except one doesn't get a very good sense of the answer from the sum.  As mentioned above, this is claimed to be about $\sqrt{n\pi/2}$, but how?  
It turns out that a sum similar to the above was studied by Ramanujan nearly 100 years ago; he called it the Q-Function. 
$$ Q(n) = \sum_{1 \leq t \leq n} \frac{n!}{(n-t)!n^t} $$
Since the Q-Function starts at 1 and our desired sum starts at 0, our sum will be $1 + Q(n)$.  Asymptotic analysis shows that 
$$ Q(n) \sim \sqrt{\frac{n \pi}{2}} + \frac{2}{3} $$
The derivation I found for this is in "Analysis of Algorithms", R. Sedgewick and P. Flajolet, Addison-Wesley, 1996.  It's quite involved.  Interestingly, the $\sqrt{\frac{n \pi}{2}}$ term comes from evaluating the famous integral over $e^{-x^2/2}$.
To answer the final question: what is the length of the tail and head?  When a repetition occurs, it is uniformly likely to collide with any point already established.  (Imagine the waving of hands now) therefore on average it will land in the middle, putting half of the $\sqrt{\frac{n \pi}{2}}$ elements on the tail and the other half on the head.  Therefore the expected length of the head and tail is $\sqrt{\frac{n \pi}{8}}.$
