% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P11}{20(2)}{2013} % 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} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % 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 A simple proof of an identity of Lacasse} % 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{Yidong Sun \\ \small Department of Mathematics, \\[-0.8ex] \small Dalian Maritime University, 116026 Dalian, P.R. China\\[-0.8ex] %\small North Kentucky, U.S.A.\\ \small\tt sydmath@yahoo.com.cn \\ %\and %Forgotten Second Author \qquad Forgotten Third Author\\ %\small School of Hard Knocks\\[-0.8ex] %\small University of Western Nowhere\\[-0.8ex] %\small Nowhere, Australasiaopia\\ %\small\tt \{fsa,fta\}@uwn.edu.ao } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Jan 5, 2013}{Apr 9, 2013}{Apr 17, 2013}\\ \small Mathematics Subject Classifications: 05A15, 05A19.} \begin{document} \maketitle \begin{abstract} In this note, using the derangement polynomials and their umbral representation, we give a simple proof of an identity conjectured by Lacasse in the study of the PAC-Bayesian machine learning theory. % keywords are optional \bigskip\noindent \textbf{Keywords:} Derangement polynomial; Umbral operator. \end{abstract} \section{Introduction} In his thesis \cite{Lacasse}, Lacasse introduced the functions $\xi(n)$ and $\xi_2(n)$ in the study of the PAC-Bayesian machine learning theory, where \begin{eqnarray*} \xi(n) \hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{n}\binom{n}{k}\left(\frac{k}{n}\right)^k\left(1-\frac{k}{n}\right)^{n-k}, \\ \xi_2(n)\hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{n}\sum_{j=0}^{n-k}\binom{n}{k}\binom{n-k}{j}\left(\frac{k}{n}\right)^k\left(\frac{j}{n}\right)^j\left(1-\frac{k}{n}-\frac{j}{n}\right)^{n-k-j}. \end{eqnarray*} Based on numerical verification, Lacasse presented the following conjecture. \begin{conjecture} For any integer $n\geq 1$, there holds \begin{eqnarray}\label{eqn 1.1} \xi_2(n)\hskip-.22cm &=&\hskip-.22cm \xi(n)+n. \end{eqnarray} \end{conjecture} Recently, by applying a multivariate Abel identity due to Hurwitz, Younsi \cite{Younsi} gave an algebraic proof of this conjecture. Later, using a decomposition of triply rooted trees into three doubly rooted trees, Chen, Peng and Yang \cite{Chen} gave it a nice combinatorial interpretation. A very short proof was also obtained by Prodinger \cite{Prodinger}, based on the study of the tree function, with links to Lambert's W-function and Ramanujan's Q-function. In this note, using the derangement polynomials and their umbral representation, we provide another simple proof of (\ref{eqn 1.1}). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The derangement polynomials and the proof of (\ref{eqn 1.1})} Recall that the derangement polynomials $\{\mathcal{D}_{n}(\lambda)\}_{n\geq 0}$ are defined by \begin{eqnarray}\label{eqn 2.1} \mathcal{D}_{n}(\lambda) \hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{n}\binom{n}{k}D_k\lambda^{n-k}. \end{eqnarray} where $\mathcal{D}_{n}(1)=n!$ and $\mathcal{D}_n(0)=D_n$ is the $n$-th derangement number, counting permutations on $[n]=\{1,2,\dots, n\}$ with no fixed points. The derangement polynomials $\mathcal{D}_{n}(\lambda)$, also called $\lambda$-factorials of $n$, have been considerably investigated by Eriksen, Freij and W$\ddot{a}$stlund \cite{Eriksen}, Sun and Zhuang \cite{SunZhuang}. They have a basic recursive relation \cite{Eriksen} and an Abel-type formula \cite{SunZhuang}, \begin{eqnarray} \mathcal{D}_{n}(\lambda+\mu) \hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{n}\binom{n}{k}\mathcal{D}_{k}(\lambda)\mu^{n-k}, \label{eqn 2.2}\\ \mathcal{D}_{n}(\lambda+\mu) \hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{n}\binom{n}{k}(\lambda+k)^{k}(\mu-k-1)^{n-k}, \label{eqn 2.3} \end{eqnarray} and obey the following property \cite{SunZhuang}, \begin{eqnarray}\label{eqn 2.4} \sum_{k=0}^{n}\binom{n}{k}\mathcal{D}_{k}(\lambda)\mathcal{D}_{n-k}(\mu+1) \hskip-.22cm &=&\hskip-.22cm (\lambda+\mu-1)^{n+1}+(n-\lambda-\mu+2)\mathcal{D}_n(\lambda+\mu). \end{eqnarray} Denote by $\mathbf{D}$ the umbral operator defined by $\mathbf{D}^n=D_n$ for $n\geq 0$ (See \cite{Gesselb, Roman, RomRota} for more information on the umbral calculus), then by (\ref{eqn 2.1}) $\mathcal{D}_{n}(\lambda)$ can be represented as \begin{eqnarray*} \mathcal{D}_{n}(\lambda) \hskip-.22cm &=&\hskip-.22cm (\mathbf{D}+\lambda)^n. \end{eqnarray*} Setting $\lambda=0, \mu=n+1$ in (\ref{eqn 2.4}), we have \begin{eqnarray*} n^{n+1}+\mathcal{D}_{n}(n+1) \hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{n}\binom{n}{k}\mathcal{D}_{k}(0)\mathcal{D}_{n-k}(n+2) \\ \hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{n}\binom{n}{k}\mathcal{D}_{k}(0)\mu^{n-k}|_{\mu=(\mathbf{D}+n+2)} \\ \hskip-.22cm &=&\hskip-.22cm \mathcal{D}_{n}(\mu)|_{\mu=(\mathbf{D}+n+2)} \hskip2cm \mbox{by (\ref{eqn 2.2})} \\ \hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{n}\binom{n}{k}k^{k}(\mu-k-1)^{n-k}|_{\mu=(\mathbf{D}+n+2)} \hskip1cm \mbox{by (\ref{eqn 2.3})} \\ \hskip-.22cm &=&\hskip-.22cm \sum_{k=0}^{n}\binom{n}{k}k^k\mathcal{D}_{n-k}(n-k+1), \end{eqnarray*} which proves (\ref{eqn 1.1}), if one notices that $\xi(n)$ and $\xi_2(n)$, by (\ref{eqn 2.3}), can be rewritten as \begin{eqnarray*} \xi(n)=\frac{1}{n^n}\mathcal{D}_{n}(n+1) \hskip.2cm \mbox{and}\hskip.2cm \xi_2(n)= \frac{1}{n^n}\sum_{k=0}^{n}\binom{n}{k}k^k\mathcal{D}_{n-k}(n-k+1). \end{eqnarray*} \begin{remark} By the nontrivial property of $\mathbf{D}$ \cite{SunZhuang}, \begin{eqnarray*} (\mathbf{D}+\lambda)(\mathbf{D}+\lambda+n+1)^{n}\hskip-.22cm &=&\hskip-.22cm (n+\lambda)^{n+1}, \end{eqnarray*} one can get another expression for $\xi_2(n)$, \begin{eqnarray*} \xi_2(n) \hskip-.22cm &=&\hskip-.22cm \xi(n)+n= \frac{1}{n^n}\big(\mathcal{D}_{n}(n+1)+n^{n+1}\big) \\ \hskip-.22cm &=&\hskip-.22cm \frac{1}{n^n}\big((\mathbf{D}+n+1)^n+\mathbf{D}(\mathbf{D}+n+1)^n \big) \\ \hskip-.22cm &=&\hskip-.22cm \frac{1}{n^n}\big((\mathbf{D}+1)(\mathbf{D}+n+1)^n \big) =\frac{1}{n^n}\sum_{k=0}^{n}\binom{n}{k}(\mathbf{D}+1)^{k+1}n^{n-k} \\ \hskip-.22cm &=&\hskip-.22cm \frac{1}{n^n}\sum_{k=0}^{n}\binom{n}{k}\mathcal{D}_{k+1}(1)n^{n-k}=\frac{1}{n^n}\sum_{k=0}^{n}\binom{n}{k}(k+1)!n^{n-k}. \end{eqnarray*} This expression has been obtained by Younsi by using the Hurwitz identity on multivariate Abel polynomials and plays a critical role in his proof. \end{remark} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgements} The author is grateful to the referee for the helpful suggestions and comments. The work was partially supported by The National Science Foundation of China and by the Fundamental Research Funds for the Central Universities (2012QN061 and 2012TD032). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \bibliographystyle{plain} % \bibliography{myBibFile} \begin{thebibliography}{10} \bibitem{Chen} W.~Y.~C. Chen, J.~F.~F. Peng, and H.~R.~L. Yang. \newblock Decomposition of triply rooted trees. \newblock {\em Electronic J. Combinatorics 20(2), $\#$P10}, 2013. \bibitem{Eriksen} N. Eriksen, R. Freij, and J. W$\ddot{a}$stlund. \newblock Enumeration of derangements with descents in prescribed positions. \newblock {\em Electronic J. Combinatorics 16(1), $\#$R32}, 2009. \bibitem{Gesselb} I.~M. Gessel. \newblock Applications of the classical umbral calculus. \newblock {\em Algebra Universalis, 49:397--434}, 2003. \bibitem{Lacasse} A. Lacasse. \newblock Bornes PAC-Bayes et algorithmes d'apprentissage. Ph.D. Thesis, Universite Laval, Quebec, 2010. \bibitem{Prodinger} H. Prodinger. \newblock An identity conjectured by Lacasse via the tree function. \newblock {\em arXiv:1301.3669}, 2013. \bibitem{Roman} S. Roman. \newblock The Umbral Calculus. \newblock {\em Academic Press, Orlando, FL}, 1984. \bibitem{RomRota} S. Roman and G.-C. Rota. \newblock The umbral calculus. \newblock {\em Adv. Math. 27:95--188}, 1978. \bibitem{SunZhuang} Y. Sun and J. Zhuang. \newblock $\lambda$-factorials of $n$. \newblock {\em Electronic J. Combinatorics 17, $\#$R169}, 2010. \bibitem{Younsi} M. Younsi. \newblock Proof of a combinatorial conjecture coming from the PAC-Bayesian machine learning theory. \newblock {\em arXiv:1209.0824}, 2012. \end{thebibliography} \end{document}