Mixed moments for the birthday problem Let $X_1,X_2,\dots$ be iid draws from the uniform distribution on $\{1,2,...,m\}$, and let the random variable $N$ be the minimum $j$ such that $X_j = X_i$ for some $i<j$.
I'm aware that the expected value of $N \choose 2$ (I call this a "mixed moment" since it's 1/2 times the second moment minus 1/2 times the first moment) is exactly $m$. Who first noticed/proved this?
Also, I've heard that, more generally, the expected value of $N \choose k$ is a degree-$k/2$ polynomial function of $m$ when $k$ is even. Where can I learn more about this?
 A: $\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\B}{\mathcal B}
\newcommand{\F}{\mathcal F}
\newcommand{\X}{\mathcal X}
\newcommand{\ep}{\epsilon}
\newcommand{\la}{\lambda}
\newcommand{\si}{\sigma}
\newcommand{\Si}{\Sigma}
\renewcommand{\c}{\circ}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\E}{\operatorname{\mathsf E}}
\newcommand{\PP}{\operatorname{\mathsf P}}$
For any natural $n$, 
\begin{multline*}
 \PP(N>n)=\PP(X_1,\dots,X_n\text{ take distinct values })=\frac{m(m-1)\cdots(m-n+1)}{m^n} \\ 
 =\frac{(m-1)\cdots(m-n+1)}{m^{n-1}},
\end{multline*}
whence
\begin{equation}
 \PP(N=n)=\PP(N>n-1)-\PP(N>n)
 =\frac{(m-1)\cdots(m-n+2)}{m^{n-1}}\,(n-1). 
\end{equation}
So, 
\begin{multline*}
 \mu_k(m):=\E \binom Nk \\ 
 =\frac1{k!}\sum_{n=k}^{m+1}\frac{n-1}{m^{n-1}}\,n(n-1)\cdots(n-k+1)(m-1)\cdots(m-n+2). \tag{1}
\end{multline*}
From here, with the help of Mathematica, I do get 
\begin{equation}
 \E \binom N2=m. 
\end{equation}
However, $\mu_4(10)-3\mu_4(9)+3\mu_4(8)-\mu_4(7)=0.0126\ldots\ne0$, so that $\mu_4$ is not a polynomial of degree $4/2=2$. That is, in general the statement that $\E \binom Nk$ is a polynomial of degree $k/2$ in $m$ is false. 
Let us now show that $\mu_4(m)$ is not a polynomial in $m$ of any degree. Let  $X_m$ be a random variable (r.v.) with the Gamma distribution with parameters $m$ and $1$, so that $X_m$ has the distribution of the sum of $m$ iid standard exponential r.v.'s, each of those r.v.'s with mean $1$. Then, by the central limit theorem, $\PP(X_m>m)\to1/2$ as $m\to\infty$.
An expression for $\mu_4(m)$ for any natural $m$ (also obtained with the help of Mathematica) is 
$\frac{1}{3} m \left(-2 e^m m E_{1-m}(m)+m+1\right)$, where $E_n(z)=\int_1^\infty t^{-n}e^{-tz}\,dt$ is "the exponential integral function"; I have verified numerically that for $m=1,\dots,100$ the latter expression for $\mu_4(m)$ matches the special case of (1) for $k=4$. So, if $\mu_4(m)$ were a polynomial in $m$, then so would be $e^m m^2 E_{1-m}(m)$. But 
\begin{multline*}
 e^m m^2 E_{1-m}(m)=e^m m^2 \frac1{m^m}\int_m^\infty u^{m-1}e^{-u}du
 =m\,\frac{e^m m!}{m^m}\,\PP(X_m>m) \\ 
 \sim m\,\sqrt{2\pi m}\,\frac12 
\end{multline*}
as $m\to\infty$, 
by Stirling's formula and because $\PP(X_m>m)\to1/2$. 
So, $e^m m^2 E_{1-m}(m)$ cannot be a polynomial in $m$. Thus, $\mu_4(m)$ is not a polynomial in $m$, of any degree.
A: Here is an approach via Lagrange inversion.
Let $N$ denote the time of the first repeat, and let $T(z)$ (the ``tree function'') be the formal power series satisfying $T(z)=z\,e^{T(z)}$. 
If $F$ is a formal power series  the coefficients of $G(z):=F(T(z))$ are given by (Lagrange inversion)
$$[z^0]G(z)=[z^0] F(z) \mbox{ , }  [z^k]G(z)=\tfrac{1}{k} [y^{k-1}] F^\prime(y)\,e^{ky} =[y^k](1-y)F(y)\,e^{ky}\mbox{ for } k\geq 1\;.$$
In particular
$$[z^m] T(z)^k=\frac{k}{m} \frac{m^{m-k}}{(m-k)!}\mbox{ and }
            \frac{1}{1-T(z)}=\sum_{n\geq 0}\frac{n^{n}}{n!}z^n$$
        Using the first relation it is easily seen that the generating function of $N$ may be written as
        $$\mathbb{E} t^N=\frac{m!}{m^m} [z^m]\frac{t}{1- tT(z)}$$
        Thus the binomial moments $\mathbb{E}{N \choose k}$ of $N$ can be obtained as 
        $$\mathbb{E}{N \choose k} = \frac{m!}{m^m} [z^m t^k]\frac{1+t}{1- (1+t)T(z)}=\frac{m!}{m^m} [z^m ]\frac{T(x)^{k-1}}{(1- T(z))^{k+1}}$$
        Differentiation shows that $z\,T^\prime(z)= \frac{T(z)}{1-T(z)}$.
        Therefore 
        \begin{align*} \mathbb{E}{N \choose 2} &=\frac{m!}{m^m} [z^m ]\frac{T(z)}{(1- T(z))^{3}}\\
           &=\frac{m!}{m^m} [z^{m-1} ]\frac{T^\prime(z)}{(1- T(z))^{2}}\\
           &=\frac{m!}{m^m} [z^{m-1} ]\big(\frac{1}{1- T(z)}\big)^\prime\\
           &=\frac{m!}{m^m} m\,[z^{m} ]\frac{1}{1- T(z)}
                                       =m\end{align*}
        (I don't know who first observed that.)
       Similarly 
        \begin{align*} \mathbb{E}{N \choose 4} &=\frac{m!}{m^m} [z^m ]\frac{T(z)^3}{(1- T(z))^{5}}\\
      &=\frac{m!}{m^m} [z^{m-1} ] T^\prime(z)\frac{T(z)^2}{(1- T(z))^{4}}\\
      &=\frac{m!}{m^m} [z^{m-1} ]\big(\frac{1}{1- T(z)}-\frac{2}{3}\frac{1}{(1-T(z))^2}+\frac{1}{3}\frac{T(z)}{(1-T(z))^3}\big)^\prime\\
      &=\frac{m!}{m^m} m\,[z^{m}]\big(\frac{1}{1- T(z)}-\frac{2}{3}\frac{1}{(1-T(z))^2}+\frac{1}{3}\frac{T(z)}{(1-T(z))^3}\big)\\
      &=\frac{m^2}{3} +m -\frac{2}{3} m\,\mathbb{E}(N)\end{align*}
Clearly other binomial moments can be treated in the same way.
