% 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} % 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}{March 22, 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} 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, 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 the Hurwitz identity on multivariate Abel polynomials, 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 using an identity of Hurwitz 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} % 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{Chen} W.~Y.~C. Chen, J.~F.~F. Peng, and H.~R.~L. Yang. \newblock Decomposition of triply rooted trees. \newblock {\em arXiv:1212.6468v1}, 2012. \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, $\#$R32}, 2009. \bibitem{Gesselb} I.~M. Gessel. \newblock Applications of the classical umbral calculus. \newblock {\em Algebra Universalis, 49:397--434}, 2003. \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, $\#$169}, 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}