% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf An identity conjectured by Lacasse 
 via the tree function}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Helmut Prodinger\thanks{The  author was supported by an incentive grant of the NRF of South Africa.}\\
\small Department of Mathematics\\[-0.8ex]
\small University of Stellenbosch\\[-0.8ex] 
\small 7602 Stellenbosch, South Africa\\
\small\tt hproding@sun.ac.za\\
}

\title{An identity conjectured by Lacasse via the tree function}



\date{\dateline{XXX 2013}{XXX, 2013}\\
\small Mathematics Subject Classifications: 05A15, 05A19.}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
A. Lacasse conjectured a combinatorial identity in his study of learning theory. Various people found independent proofs. Here is another one that is based on the study of the tree function, with links to Lamberts $W$-function and Ramanujan's $Q$-function. It is particularly short.
 \end{abstract}


Let
\begin{align*}
\xi(n)&=\sum_{k=0}^n\binom nk \Bigl(\frac kn\Bigr)^k\Bigl(\frac {n-k}{n}\Bigr)^{n-k},\\
\xi_2(n)&=\sum_{k_1+k_2+k_3=n}\frac{n!}{k_1!k_2!k_3!}
 \Bigl(\frac {k_1}n\Bigr)^{k_1}\Bigl(\frac {k_2}n\Bigr)^{k_2}\Bigl(\frac {k_3}n\Bigr)^{k_3}.
\end{align*}
Then Lacasse~\cite{Lacasse} conjectured that $\xi_2(n)=\xi(n)+n$. There are now three independent
proofs~\cite{Younsi, CePeYa, Sun}. Here, we want to shed additional light on the matter, 
by using the \emph{tree function} (equivalent to Lambert's $W$-function~\cite{CoGoHaJeKn}) and linking the enumeration
to the celebrated $Q$-function of Ramanujan~\cite{FlGrKiPr}.

As Younsi has already pointed out, it is easier to work with
\begin{align*}
\alpha(n)&=n^n\xi(n)=\sum_{k=0}^n\binom nk k^k(n-k)^{n-k},\\
\beta(n)&=n^n\xi_2(n)=\sum_{k_1+k_2+k_3=n}\frac{n!}{k_1!k_2!k_3!}
 k_1^{k_1}k_2^{k_2}k_3^{k_3}.
\end{align*}

The tree function~\cite{GoJa} $y(z)$ is defined by $y=ze^y$ and possesses the expansion
\begin{equation*}
y(z)=\sum_{n\ge1}n^{n-1}\frac{z^n}{n!}.
\end{equation*}
Therefore
\begin{equation*}
\sum_{n\ge0}n^{n}\frac{z^n}{n!}=1+zy'(z)=1+\frac{y}{1-y}=\frac{1}{1-y}.
\end{equation*}
Consequently,
\begin{equation*}
\alpha(n)=n![z^n]\Bigl(\frac{1}{1-y}\Bigr)^2\quad\text{and}\quad
\beta(n)=n![z^n]\Bigl(\frac{1}{1-y}\Bigr)^3.
\end{equation*}
Now we compute the coefficients of a general power via Cauchy's integral formula:
\begin{align*}
[z^n]\Bigl(\frac{1}{1-y}\Bigr)^d
&=\frac1{2\pi i}\oint\frac{dz}{z^{n+1}}\Bigl(\frac{1}{1-y}\Bigr)^d\\*
&=\frac1{2\pi i}\oint\frac{dy(1-y)e^{-y}e^{y(n+1)}}{y^{n+1}}\Bigl(\frac{1}{1-y}\Bigr)^d\\
&=[y^n]\frac{e^{ny}}{(1-y)^{d-1}}\\
&=\sum_{k=0}^n\frac{n^{n-k}}{(n-k)!}\binom{k+d-2}{d-2}.
\end{align*}
Therefore
\begin{align*}
\alpha(n)=\sum_{k=0}^n\frac{n!}{k!}n^k,\qquad
\beta(n)=\sum_{k=0}^n\frac{n!}{k!}(n+1-k)n^k,
\end{align*}
and
\begin{align*}
\beta(n)-\alpha(n)&=\sum_{k=0}^n\frac{n!}{k!}(n-k)n^k\\
&=\sum_{k=0}^n\frac{n!}{k!}n^{k+1}-\sum_{k=1}^n\frac{n!}{(k-1)!}n^k=n^{n+1},
\end{align*}
as claimed.

Note that $\alpha(n)$ is linked to Ramanujan's celebrated $Q$-function~\cite{FlGrKiPr} via
\begin{equation*}
\alpha(n)=n^n\big(1+Q(n)\big).
\end{equation*}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem{CePeYa} W.~Y.~C. Chen, J.~F.~F. Peng and H.~R.~L. Yang, Decomposition of triply rooted trees, Electronic Journal of Combinatorics 20, Issue 2 (2013), P10, 10 pages.

 

\bibitem{FlGrKiPr} P. Flajolet, P. Grabner, P. Kirschenhofer and H. Prodinger, 
On Ramanujan's $Q(n)$-function, Journal of Computational and Applied Mathematics, 58:103--116, 1995. 

\bibitem{Lacasse} A. Lacasse, Bornes PAC-Bayes et algorithmes d'apprentissage, Ph.~D. thesis, Universit\'e Laval, Quebec, 2010.


\bibitem{GoJa} I.~Goulden and D.~Jackson, Combinatorial Enumeration, Wiley, 1983.


\bibitem{Sun}  Y.~Sun, A simple proof of an identity conjectured by Lacasse,
Electronic Journal of Combinatorics 20, Issue 2 (2013), P11, 3 pages.

\bibitem{Younsi}  M. Younsi, Proof of a combinatorial conjecture coming from the PAC-Bayesian machine learning theory,
arXiv:1301.0679.





\bibitem{CoGoHaJeKn} R. Corless, G. Gonnet, D. Hare, D. Jeffrey and D. Knuth,  On the Lambert $W$-function, Advances in Computational Mathematics 5: 329--359, 1996.

\end{thebibliography}

\end{document}