\documentclass[12pt,reqno]{amsart}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\newcommand{\ol}[1]{\overline{#1}}
\newcommand{\mf}[1]{\mathfrak{#1}}
\newcommand{\mi}[1]{\mathit{#1}}
\newcommand{\msf}[1]{\mathsf{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\hg}[5]{
{}_{#1} \msf{F}_{#2}
\left[
\begin{matrix}
#3 \cr #4
\end{matrix}
\,;\,
#5
\right]
}

\textheight22.8cm 
\textwidth15.6cm 
\hoffset-1.7cm 
\voffset-.5cm
\numberwithin{equation}{section}
\sloppypar

\title{Lacunary Laguerre series
		from a combinatorial perspective}

\author{Volker Strehl}

\date{\today}

\address{Volker Strehl, 
Department Informatik
(Theoretische Informatik),
Universit\"at Erlangen--N\"urnberg,
Martensstra\ss e 3,
D-91058 Erlangen,
Germany.}

\email{Volker.Strehl@fau.de}


\begin{document}

\begin{abstract}
In recent work, 
Babusci, Dattoli, G\'orska, and Penson
have presented a number of 
lacunary generating functions
for the generalized Laguerre
polynomials $L_n^{(\alpha)}(x)$,
i.e., series of the type
$\sum_{n \geq 0} 
c_n L_{2n}^{(\alpha)}(x)\, t^n$, 
by a method closely related to
umbral calculus.
This work is complemented here, 
deriving many of their results by 
interpreting Laguerre polynomials 
combinatorially as enumerators for 
discrete structures 
(injective partial functions). 
This combinatorial view pays in 
that it suggests natural extensions 
and gives a deeper insight into 
the known formulas.
\end{abstract}

\maketitle

\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de Combinatoire \bfs 76 \rms (2017), 
Article~B76c\hfill}
\def\thepage{}

\section{Introduction}

\subsection{History and motivation}

The following citation is taken
from the Introduction of an article by 
Adriano Garsia and Jeff Remmel \cite{GR80}, 
published in 1980 in
the very first volume of the
\emph{European Journal of Combinatorics}. 
It has been reproduced (in French) 
in a slightly shortened version
%(on which my quotation is based)% 
by Dominique Foata in the introduction to 
the written version \cite{Fo84} of
his talk on the combinatorics
of orthogonal polynomials,
presented at the 
International Congress of 
Mathematicians in Warsaw, 1983.

\medskip
\begin{quote}\it
It has become increasingly apparent 
since the work of Foata--Schutzenberger 
and recent works of the Lotharingian 
school of combinatorics [\ldots] that 
the special functions and identities 
of classical mathematics are gravid 
with combinatorial information. 
This information can be expressed 
in the form of correspondences or 
more precisely encodings of objects 
into words of certain languages and 
natural bijections between different 
classes of languages. The classical 
identities appear then as relations 
between enumerators of these words 
by suitable statistics.
At present a systematic study is 
taking place to mine this information 
out of the classical literature. 
This increasingly rich inventory of 
correspondences has led to new 
identities as well as more revealing 
proofs of the old ones.
\end{quote}
\medskip

In this context, Foata mentions 
various schools of combinatorics
(\'ecoles \emph{bostonienne}, 
\emph{californienne},
\emph{lotharingienne},
\emph{qu\'ebecoise},
\emph{viennoise})
inspired by these ideas,
and the number of references,
witnessing the enormous
activities in the spirit 
expressed in this citation, has 
drastically increased
compared to the original text.


The above quotation very well describes 
the atmosphere of departure around 1980. 
I will not try to give an overview, 
least of all a comprehensive account of
what has been achieved in those days. 
But in relation to the present article 
I have to mention some particular work 
that I have personally been involved in.
Foata's work on the combinatorics of 
Hermite polynomials, see 
\cite{Fo78}, and also
\cite{FG79} and
\cite{Fo81},
with a  simple proof of the bilinear
generating function, known
as Mehler's formula, and its
multilinear generalizations,
constitutes an early striking example 
for the elegance and efficiency of
combinatorial concepts and methods
in this domain.
The combinatorial model itself,
involutions alias matchings
of complete graphs, belongs 
to combinatorial folklore.
 
In 1981 I have been invited by 
Dominique Foata to jointly work on 
similar items for the 
Laguerre polynomials, i.e., 
their bilinear generating function
that goes under the name
Hille--Hardy identity,
which will appear in this article 
towards the end as 
Eq.~(\ref{eqn:hillehardy}).
We have set up a combinatorial
model, the very same one that 
will be introduced here in 
Section~\ref{ssec:laguerreconfig},
and we have given a proof
of the Hille--Hardy identity 
based on this model. 
The model then guided us to
invent and to prove a multilinear
extension, 
see \cite{FS81} and \cite{FS83}. 

Another striking event in
those days was the combinatorial
proof of the generating
function for the Jacobi polynomials, 
achieved by Foata and Leroux
in \cite{FL83}. The model deals with 
complementary pairs of Laguerre 
configurations, which naturally produces
tree-like objects and therefore
relates to Lagrange inversion. 
For me it has been a challenge to study 
further properties of the Jacobi polynomials,
including Bailey's bilinear generating function,
by looking through combinatorial glasses. 
Some of this work has been published in articles, 
but I will not give the references here, 
because it has materialized, together
with lots of otherwise unpublished work, 
in my habilitation thesis
\cite{St90}.

After having completed 
\cite{St90},
my interests shifted, well under the influence
of the spectacular success of Zeilberger's 
ideas and implementations, towards the
algorithmic side of hypergeometric series,
binomial identities, and symbolic summation.
See, e.g., my article \cite{St94}
which deals with both,
combinatorial and algorithmic aspects.
The chapter on the combinatorics
of special function identities
appeared to be closed for me. 

\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL VOLKER STREHL}{\SMALL LACUNARY
LAGUERRE SERIES FROM A COMBINATORIAL PERSPECTIVE}

It came as a surprise when
Karol Penson contacted me in 2012, 
sending me the list
\cite{BDGP12} 
(not containing any proofs)
of lacunary generating functions for the 
Laguerre polynomials and asking, 
what a combinatorialist could say about 
these new results.
My first reaction was reluctant,
because the formulas looked 
pretty complicated, and I was not sure 
that one could produce combinatorial 
proofs that would be more enlightening 
than tour-de-force work.
My mind changed when I received a 
first version of what is now the article 
\cite{BDGP16}.
I started to look closer and it appeared 
to me that indeed something interesting 
could be said when interpreting these 
identities  in terms of the good old 
Laguerre configurations.
The present article is the result of my 
investigations. 
I have taken some of the major results of 
\cite{BDGP16} 
and cast them into combinatorics. 
But it would not have been
too exciting for me to present intricate 
combinatorial proofs for results that have 
been obtained (formally) analytically more 
easily.
In my opinion the value of the 
combinatorial approach lies in that it 
guides on the way towards reasonable 
generalizations, specializations, and 
refinements in an intuitive, 
even ``visible'' way. 


\subsection{Structure of the article}
\label{ssec:structure}

Sections~\ref{sec:notation} to
\ref{sec:differential}
prepare the ground for the combinatorial 
work with Hermite and Laguerre series.
To start with,
Section~\ref{sec:notation} 
is about notation and conventions relating 
to exponential generating functions
for families of combinatorial structures. 
It will be assumed that the reader is 
familiar with these notions that have 
been formalized in essentially equivalent 
ways in many places. 
The classical titles
(in chronological order) 
\cite{Ri58},
\cite{Co74},
\cite{Fo74},
\cite{GJ83},
\cite{Wi90},
\cite{BLL98},
\cite{FS09}
constitute just a subjective selection
from the literature.

The main actors of this article,
Hermite and Laguerre configurations, 
are introduced in 
Section~\ref{sec:vocabulary}.
These are families of combinatorial objects 
used to interpret the integer coefficients 
(in a suitable normalization)
of the classical polynomials bearing 
the same name. 
In 
Section~\ref{ssec:other} 
some pointers are given to other work on 
Laguerre polynomials (or, more generally,
classical orthogonal polynomials) 
and combinatorics, that is not touched
upon in this article.

In the subsequent section,
Section~\ref{sec:examples},  
some elementary examples are given that
demonstrate the use of these combinatorial models. 
Some of these ideas are used later on.
Another item of the same kind is the use 
of differential operators from a combinatorial
perspective, which is presented in 
Section~\ref{sec:differential}. 
This  material has been included mainly 
because in the article
\cite{BDGP16} by Babusci et al.\
differential operators play an important role, 
but here this aspect is not treated any further. 

The proper combinatorial
contributions of this article
are presented beginning with 
Section~\ref{sec:natural}, 
where a very natural idea for
obtaining lacunary generating
function combinatorially is
exploited: just copy the 
base sets where the combinatorial
structures live, and use a basic
decomposition property of 
Laguerre configuration. 
These copying procedures could
be used to obtain
$k$-lacunary series for
$k=2,3,4,\ldots$, but 
only the cases $k=2$ and $k=3$
are treated in detail, and for
$k=4$ the result is given.
It should then be obvious what
the result for arbitrary $k$
looks like.

The approach to lacunary 
Laguerre series as presented in 
Section~\ref{sec:simplest} 
is different, and, in my opinion, it is 
more interesting than the previous one.
The basic idea is to consider
superpositions of Laguerre
configurations and perfect
matchings (i.e., a special
class of Hermite configurations)
as combinatorial objects.
This forces the ground set to
be of \emph{even} cardinality,
which naturally leads to a 
lacunary generating function. 
As a result, we obtain a very nice,
strikingly simple double 
lacunary generating function
for the Laguerre polynomials, which
is expressed in terms of Hermite
polynomials. 
The interest of this combinatorial 
set-up lies in the fact, that it can 
be easily generalized in various ways, 
one of which is presented in 
Section~\ref{sec:motivated}.
By considering the superposition
of Laguerre and (general) Hermite
configurations, i.e.,
involutions alias general matchings, 
we are led to a bilateral (not lacunary)
generating function, that can be 
specialized to yield further lacunary 
Laguerre series. 
In my experience, it would have been 
difficult to imagine the general result
without the underlying combinatorial 
model in mind.  

Another extension of the basic identity in 
Section~\ref{sec:simplest} 
is then tackled in 
Section~\ref{sec:another}.
This generalizes from the ordinary
Laguerre polynomials 
$L_{2n}^{(0)}$ to the
generalized Laguerre polynomials 
$L_{2n}^{(k)}$.
The cases $k=1$ and $k=2$ have been 
treated experimentally by
Babusci et al.\ in \cite{BDGP16},
with rather strange 
(at first sight, at least) 
coefficient polynomials showing up 
which were not explained any further. 
The combinatorial approach, however, 
yields a very nice and simple 
explanation for these ``wild'' 
polynomials, that are counting certain 
balls-into-boxes configurations.
This leads to a very satisfactory 
result for general $k$ through a 
combinatorial proof.

Section~\ref{sec:moreext} 
can be seen as an addendum
to the foregoing: 
first, in 
Section~\ref{ssec:alphaext}
the same situation as in 
Section~\ref{sec:another} 
is treated, but now with an additional 
cycle counting parameter. 
Secondly, in 
Section~\ref{ssec:tripleext}
it is indicated that also triple lacunary
Laguerre series can be obtained this way. 
Not all details are given, but
they could be worked out, if desired.

A result from \cite{BDGP16},
featuring the polynomials 
$L_{2n}^{(\alpha-2n)}(x)$,
which is already typographically
different from all the others,
is the object of 
Section~\ref{sec:charlier}.
Indeed, these polynomials
are not proper Laguerre polynomials, 
as their parameter $\alpha-2n$ 
depends on $n$. 
These polynomials are essentially 
Charlier polynomials, which are generally 
easier to treat than Laguerre polynomials, 
as the combinatorial objects counted by 
them are just colored permutation.
Anyway, the daunting analytical
expression has a very simple combinatorial
explanation.

Finally, in 
Section~\ref{sec:binomial}
another interesting hypergeometric series from 
\cite{BDGP16}
is considered, which is actually 
equivalent to one treated here already in 
Section~\ref{sec:natural}.
By relating this series to the classical 
Hille--Hardy bilinear generating function
for the Laguerre polynomials,
for which a combinatorial
proof is known since long, 
see \cite{FS81} and \cite{FS83},
one obtains intriguing hypergeometric and
binomial identities. 
The core result is expressed as a nice 
umbral substitution identity, which relates
Laguerre and Legendre polynomials.
This looks as if a direct combinatorial 
proof should be manageable, but I have not 
been able to construct one --- so I leave
this as a combinatorial puzzle. 
 
 

\section{Notation and conventions}
\label{sec:notation}

If $\mf{E}$ is a family of 
combinatorial structures 
(in the sense of the
\emph{combinatorial species}
or  
\emph{species of structure} of \cite{BLL98},
but we will use only very basic
facts and conventions), 
and $A$ is any finite set, then 
$\mf{E}[A]$ will denote the set of
$\mf{E}$-structures living on $A$.
If $A=[n]=\{1,2,\ldots,n\}$, then 
$\mf{E}[n]$ will be
written in place of $\mf{E}[[n]]$.
For any set $A$ of cardinality  $n$, 
which is denoted by $\sharp A=n$,
the sets $\mf{E}[A]$ and
$\mf{E}[n]$ are equivalent
in a functorial way. 
This is made precise in species theory, 
but needs not to be detailed here.
As mentioned at the beginning of 
Section~\ref{ssec:structure}, 
there are many places, where a similar 
formalism for the combinatorics
of exponential generating is described.

Generally, we are dealing here with 
structures which are both
\emph{labeled}
(by the elements of the respective 
ground set $A$),
and \emph{weighted},
in the sense that a mapping
(\emph{weight function}),  
$w:\mf{E}[A]\to R[x]$
is specified that is compatible
with transport of 
structures via bijections.
Here $R$ is some suitable ring,
$R[x]$ is its polynomial ring,
in the variable $x$. 
Typically, the weight $w(e)$ for 
$e \in \mf{E}[A]$ 
will be of the kind 
$w(e)= \tilde{w}(e)\, x^{\sharp{A}}$,
where 
$\tilde{w}(e) \in R$
encodes some structural information 
about $e$ and the term 
$x^{\sharp A}$ 
keeps track of the size 
(also called \emph{order}) 
of the underlying vertex set. 
 
The adequate tools for enumeration are 
then exponential generating functions:
\[
	\mathcal{E}(x) = 
	\sum_{n \geq 0} 
	\frac{1}{n!} 
	\sum\big\{ w(e)  
	\,;\, 
	e \in \mf{E}[n] \big\}
	=
	\sum_{n \geq 0}
	\frac{x^n}{n!} 
	\sum\big\{ 
	\tilde{w}(e)  
	\,;\, e \in \mf{E}[n] 
	\big\}.
\]
It will be convenient to use the
set-up of \emph{multisorted}
structures, which then gives rise to 
exponential generating functions in more 
than one variable. 
The case of two-sorted structures is
typical: the family of structures $e$ 
belonging to $\mf{E}$ and living
on a pair $(A,B)$ of disjoint
finite sets will be denoted as 
$\mf{E}[A,B]$, 
and these structures are weighted by 
$w(e)=\tilde{w}(e)\,
x^{\sharp A}
y^{\sharp{B}}$. 
The exponential generating function would
then be written as
\begin{align*}
	\mc{E}(x,y) &=
	\sum_{n\geq 0}
	\sum_{X \uplus Y = [n]}
	\frac{1}{\sharp X!}
	\frac{1}{\sharp Y!}
	\sum \big\{
	w(e) \,;\, e \in \mf{E}[X,Y]
	\big\}
	\cr
	&=
	\sum_{n \geq 0}
	\frac{1}{n!}
	\sum_{k + \ell = n}
	\binom{n}{k,\ell}\,
	x^k \,y^\ell\,
	\sum \big\{ w(e) \,;\,
	e \in \mf{E}[k,\ell]\big\}
	\cr
	&=
	\sum_{n\geq 0}
	\frac{1}{n!}\,
	\mc{E}_n(x,y),
\end{align*}
where 
$\mf{E}[k,\ell]= \mf{E}[A,B]$ 
for
$A=[k]$ 
and 
$B=[k+\ell]\setminus[k]$, say.
In this notation the enumerating polynomials
$\mc{E}_n(x,y)$
for $\mf{E}$-structures of order $n$ are
\emph{homogeneous} polynomials
in $x$ and $y$ of total degree $n$. 
There is no need for an extra variable
$t$, with the term $t^n$ indicating  
the order of $\mf{E}$-structures,
but it can be made visible
by making the substitution
$x \to x\,t$, $y \to y\,t$,
if desired.




\section{The combinatorial vocabulary: 
		Hermite and Laguerre configurations}
\label{sec:vocabulary}

\subsection{Hermite
configurations}
\label{ssec:hermite}

For any finite set $A$, let 
$\mf{I}[A]$, respectively $\mf{M}[A]$,
denote the set of all involutions,
respectively fixed point free involutions on $A$
(alias
\emph{matchings} respectively 
\emph{perfect matchings} 
of the complete graph with vertex set $A$).
For $\mu \in \mf{I}[A]$ the 
set of its fixed points will be denoted
by $\mi{fix}(\mu)$, and 
$\msf{fix}(\mu) =\sharp\mi{fix}(\mu)$
is its cardinality. 
Similarly, we write 
$\mi{trans}(\mu)$ 
for the set of transpositions of $\mu$, and 
$\msf{trans}(\mu) =\sharp\mi{trans}(\mu)$
for its cardinality. 
Each involution
$\mu$ will be given the valuation
\[
	\nu_{x,y}(\mu) 
	= x^{\msf{fix}(\mu)}
	y^{2 \, \msf{trans}(\mu)},
\]
and the homogeneous generating polynomial 
for involutions of order $n$ is
\[
	\mc{H}_n(x,y) =
	\sum
	\big\{\,
	\nu_{x,y}(\mu)\,;\,
	\mu \in \mf{I}[n] 
	\,\big\},
\]
our combinatorial version
of the classical Hermite polynomials.
Specifically, for any pair $(A,B)$ of 
disjoint finite sets the set $\mf{H}[A,B]$
of \emph{Hermite configurations} is the set
\[
	\mf{H}[A,B] =
	\big\{\, 
	\mu \in \mf{I}[A \uplus B]\,;\,
	\mathit{fix}(\mu)=A
	\,\big\},
\]
so $\mu \in \mf{H}[A,B]$ 
is essentially given by $A$ (as a set) and
a fixed-point free involution on $B$.
For $\mf{M}[B]$ to be non-empty, the
cardinality of $B$ must be even, 
and for a set $B$ of cardinality $2k$ one has 
\begin{equation}
\label{eqn:match}
	m_{k}=\sharp \mf{M}[B]
	=
	\begin{cases}
	1 \cdot 3 \cdot 5 
	\cdots (2m+1)
	=\displaystyle
	\frac{(2m)!}{2^m\, m!},
	&\text{if}~k=2m,
	\cr
	0,
	&\text{if}~k~\text{is odd}.
	\end{cases}
\end{equation}
Thus
\begin{align*}
	\mathcal{H}_n(x,y)
	&=
	\sum_{A \uplus B={[n]}}
	\sum
	\big\{\,
	\nu_{x,y}(\mu)
	\,;\,
	\mu \in \mf{H}[A,B]
	\,\big\}
\cr
&=
	\sum_{0\leq k \leq n}
	\binom{n}{k}\, m_k \,
	x^{n-k} \,
	y^{k}
\cr
&=
	\sum_{0 \leq 2k \leq n}
	\binom{n}{2k}\, 
	m_{2k}\, 
	x^{n-2k}\,y^{2k}
\cr
&=
	\sum_{0 \leq 2k \leq n}
	\frac{n!}{k!\, (n-2k)!\, 2^k}
	\, x^{n-2k}\,y^{2k}.
\end{align*}
In hypergeometric terms,
\[
	\mathcal{H}_n(x,y) =
	x^n 
	\cdot
	\hg{2}{0}{-n/2\,,\,1-n/2}{-}
	{\frac{2y^2}{x^2}},
\]
and it is easy to obtain the 
exponential generating function
\[
	\sum_{n \geq 0}
	\frac{1}{n!}\,
	\mathcal{H}_n(x,y)
	=
	e^{x+y^2/2}. 
\]
As a special case, for $x=0$ one has
\[
	\sum_{n \geq 0}
	\frac{1}{n!} \mathcal{H}_n(0,y) 
	=\sum_{n \geq 0} 
	\frac{y^{2n}}{(2n)!} \, m_{2n}
	=
	e^{y^2/2}.
\]
Referring to the standard notation 
$H_n(x)$ for the Hermite polynomials, 
as given for instance in the NIST Handbook \cite{NI10}, 
one observes
\[
	H_n(t) = 
	\mathcal{H}_n(2\,t,i\,\sqrt{2}),
	\hskip5mm
	\mathcal{H}_n(x,y)
	=
	(\frac{-i \,y}{\sqrt{2}})^n 
	H_n\left(
	\frac{i\, x}{\sqrt{2}\, y}
	\right).
%\hskip5mm
%\mathcal{H}_n(x,iy)=
%(\frac{y}{\sqrt{2}})^n 
%H_n\left(\frac{x}{\sqrt{2}y}\right)
\]

\subsection{Laguerre configurations}

As for the combinatorial  version of the
Laguerre polynomials, it is also preferable 
to use a homogeneous version in two variables.

For disjoint finite sets
$X,Y$ let $\mf{L}[X,Y]$ 
denote the set of all 
\emph{injective} functions 
$\lambda:X \to X \uplus Y$, 
henceforth called 
\emph{Laguerre configurations}.
Also put 
$\mf{L}[N]
=\bigcup_{X \uplus Y=N} 
\mf{L}[X,Y]$, 
which can be seen as the set of 
\emph{injective partial functions}~on $N$.
 
The connected components of such a Laguerre
configuration $\lambda$ are of two types:
\begin{itemize}
\item[--]
	$\lambda$-\emph{cycles},
	contained in $X$,
	of some length $\ell \geq 1$,
\[
	a_0 \stackrel{\lambda}{\to} 
	a_1 \stackrel{\lambda}{\to} 
	a_2 \stackrel{\lambda}{\to} 
	\ldots 
	\stackrel{\lambda}{\to} 
	a_{\ell-1} 
	\stackrel{\lambda}{\to} a_0,
\]
\item[--]
	$\lambda$-\emph{chains}
	beginning in $X$ and ending in 
	$Y$, of some length 
	$\ell \geq 0$, 
\[
	a_0 \stackrel{\lambda}{\to} 
	a_1 \stackrel{\lambda}{\to} 
	a_2 \stackrel{\lambda}{\to} 
	\ldots 
	\stackrel{\lambda}{\to} 
	a_{\ell-1} 
	\stackrel{\lambda}{\to} b,
\]
with
$a_0,\ldots,a_{\ell-1} \in X$
and $b \in Y$.  
Here the case
$\ell=0$ means nothing but
$b \not \in \lambda(X)$.
\end{itemize}

Figure~\ref{fig:laguerre1}
shows a typical Laguerre configuration 
$\lambda$ with three cycles and four chains,
one of which is simply a vertex of $Y$ 
which is not an endpoint of a proper chain.
Note the following special cases:
\begin{itemize}
\item[--]
	$\mf{L}[X,\emptyset]$ is 
	the family of permutations of $X$,
\item[--]
	$\mf{L}[\emptyset,Y]$ is $\{Y\}$, i.e. the
	set $Y$ taken as a singleton
	set of structures.
\end{itemize} 


For Laguerre configurations the
following valuation will be employed:
\[
	\omega_{x,y}^\alpha(\lambda) 
	= (1+\alpha)^{\msf{cyc}(\lambda)}
	x^{\sharp X} y^{\sharp Y}
	\in \mathbb{Z}[\alpha,x,y],
\]
where 
$\msf{cyc}(\lambda)$ 
is the
number of $\lambda$-cycles\footnote{%
Taking $1+\alpha$ instead of
$\alpha$ as a counter for cycles
is a matter of convenience, 
because it conforms with the
traditional definition of
generalized Laguerre polynomials.
Specializing $\alpha \to 0$
means ``cycles allowed, 
but no bookkeeping is done for the
number of cycles'' and
$\alpha \to -1$ means 
``cycles are forbidden''.},
and it is then easily checked that
\[
	\sum 
	\big\{\, 
		\omega_{x,y}^\alpha(\lambda)
	\,;\, 
		\lambda \in \mf{L}[X,Y] 
	\,\big\}
	=
	(1+\alpha+\sharp Y)_{\sharp X},
\]
where 
$(\gamma)_n= \gamma\cdot (\gamma+1) 
\cdots (\gamma+n-1)$
is the rising factorial or 
\emph{Pochhammer symbol}.

\begin{figure}[htbp]
	\centering
	\includegraphics[width=2in]
	{lagconfig-a.pdf} 
	\caption{A typical Laguerre 
	configuration $\lambda$ with weight
	$\omega_{x,y}^\alpha(\lambda)=
	(1+\alpha)^3\, x^{17}y^4$}
\label{fig:laguerre1}
\end{figure}


Now the combinatorial (generalized)  
Laguerre polynomials are,
for any set $N$ of cardinality $n$,
\begin{align*}
	\mathcal{L}_n^{(\alpha)}(x,y)
	&=
	\sum 
	\big\{\, 
		\omega_{x,y}^\alpha(\lambda)
		\,;\,
		\lambda \in \mf{L}[N]
	\,\big\}
	\cr
	&=
	\sum_{X \uplus Y = [N]}
	\sum 
	\big\{\, 
		\omega_{x,y}^\alpha(\lambda)
		\,;\, 
		\lambda \in \mf{L}[X,Y] 
	\,\big\}
	\cr
	&=
	\sum_{0 \leq k \leq n} 
		\binom{n}{k}
		(1+\alpha+k)_{n-k} \, 
		x^{n-k} \, y^k
	\cr
	&=
	x^n 
	\cdot
		\hg{1}{1}{-n}{1+\alpha}
		{-\frac{y}{x}}.
\end{align*}
This relates to the usual conventions 
for the Laguerre polynomials simply by
\[
	L_n^{(\alpha)}(y) = 
	\frac{1}{n!}\,
	\mathcal{L}^{(\alpha)}_n(1,-y),
	\hskip5mm
	\mathcal{L}_n^{(\alpha)}(x,y) =
	n!\,x^n\,L_n^{(\alpha)}(-y/x).
\]
In the case $\alpha=0$ the standard notation 
$L_n(y)$ for the traditional Laguerre
polynomials will be used instead of
$L_n^{(0)}(y)$, and consequently
also 
$\mathcal{L}_n(x,y)$ 
is used in place of
$\mathcal{L}_n^{(0)}(x,y)$.

\medskip

A standard combinatorial reasoning,
taking the two types of connected
components into account, immediately
shows that the exponential generating
function for Laguerre configurations is
\[
	\sum_{n \geq 0}
	\frac{1}{n!}\,
	\mathcal{L}_n^{(\alpha)}(x,y)=
	(1-x)^{-(1+\alpha)}e^{y/(1-x)},
\]
where the first factor on the right
takes care of the cycles 
(thus counting permutations), 
and the second one represents the set of 
chains of elements of $X$ ending in 
an element of $Y$. 

A slight extension of this combinatorial 
model that is sometimes handy and that 
will be used in 
Section~\ref{sec:natural},
is as follows:
consider three mutually disjoint finite
sets $X,Y,Z$, and let
\[
	\mf{L}[X,Y;Z] = 
	\mf{L}[X,Y \uplus Z], 
\]
taking as valuation for
these objects
\[
	\omega_{x,y,z}^\alpha(\lambda)
	= (1+\alpha)^{\msf{cyc}(\lambda)}
	x^{\sharp X}
	y^{\sharp Y}
	z^{\sharp Z}.
\] 
Then the generating polynomial is
\[
	\sum 
	\big\{\, 
	\omega_{x,y,z}^\alpha(\lambda)
	\,;\, 
	\lambda \in
	\mf{L}[X,Y;Z] 
	\,\big\}
	=
	(1+\alpha 
	+ \sharp Z 
	+ \sharp Y)_{\sharp X}\,
	x^{\sharp X} y^{\sharp Y}
	z^{\sharp{Z}},
\]
and for any set $N$ of cardinality $n$,
keeping the ``extra'' set $Z$ fixed,
\begin{align*}
	\sum_{X \uplus Y=N} 	
	\sum
	\big\{\, 
	\omega_{x,y,z}^{\alpha}
	(\lambda) \,;\, 
	\lambda \in \mf{L}[X,Y;Z]
	\,\big\} 
	= 
	\mathcal{L}_n^{(
	\alpha+\sharp Z)}(x,y)\,z^{\sharp Z}.
\end{align*}

A familiar special case occurs when 
the set $Y$ is copy of $X$, say $Y=X'$. 
Then the Laguerre configurations
$\lambda \in \mf{L}[X,X';Z]$ 
can be interpreted as matchings of the 
complete bipartite graph 
$K_{X, X' \uplus Z}$
with vertex sets
$X$ and $X' \uplus Z$, 
where the pairs 
$(a,\lambda(a)) \in X \times 
(X' \uplus Z)$ 
are the selected edges. 
Let $\sharp X=n$
and $\sharp Z=m$. 
The polynomial
\[
	\mc{L}_n^{(m)}(x,1) =
	\sum_{k=0}^n
	\binom{n}{k}
	\binom{n+m}{k} \,x^k
	=
	\hg{2}{1}{-n,-n-m}{1}{x} 
\]
is (essentially) what is known as the 
\emph{matching polynomial}
(\cite{LP86})
of the complete bipartite graph $K_{n,n+m}$, 
also known as \emph{rook polynomial} 
(\cite{Ri58}) 
of a rectangle of size $n \times (n+m)$.
See Figure~\ref{fig:bipartite}
for an illustration of how the 
coefficients of 
\[
	\mathcal{L}_4^{(2)}(x,y)
	=
	y^4 + 24 x y^3 +
	180 x^2 y^2 +480 x^3 y
	+ 360 x^4
\]
can be seen as counters for 
matchings in $K_{4,6}$.

\begin{figure}[htbp]
	\hskip-0.5cm
	\begin{tabular}{rcccc}
	\raisebox{1.5cm}[]{type}
	&\includegraphics[width=1in]
	{K46match1.pdf}
	&
	\includegraphics[width=1in]
	{K46match2.pdf}
	&
	\includegraphics[width=1in]
	{K46match3.pdf}
	&
	\includegraphics[width=1in]
	{K46match4.pdf}
	\cr
	$\sharp$\,cases
	&
	$\binom{4}{1}\binom{6}{1} 1! = 64$
	&
	$\binom{4}{2}\binom{6}{2} 2! = 180$
	&
	$\binom{4}{3}\binom{6}{3} 3! = 480$
	&
	$\binom{4}{4}\binom{6}{4} 4! = 360$
	\end{tabular}
	\caption{The coefficients of
	$\mc{L}_4^{(2)}(x,y)$ 
	by counting matchings in $K_{4,6}$}
\label{fig:bipartite}
\end{figure}

\subsection{Other work}
\label{ssec:other}

A lot more could be said about Laguerre 
polynomials (or, more generally, classical 
orthogonal polynomials) and combinatorics. 
There are various models,
like derangements, words, lattice paths,
rook configurations, matchings, etc.,
that have been used for exploring
properties of these families of polynomials.
Since these developments, interesting and
important as they are, will not be used
in the remainder of this article, I will
confine myself to shortly mention three areas
of activity from the the period between
the 1970's and the early 1990's.

\begin{itemize}
\item[--] The general notion of a
	\emph{reluctant function}
	was introduced by Mullin and Rota
	in \cite{MR70} in the context of
	binomial enumeration, see also
	\cite{KRY09} for a recent reference.
	The particular subfamily of \emph{injective}
	reluctant function is relevant for us:
	these are precisely the functions 
	enumerated by the polynomials
	$\mathcal{L}_n^{(-1)}(x,y)$, i.e., 
	Laguerre configurations in the present sense,
	but with $\alpha=-1$, which means that
	no cycles, only chains are allowed\footnote{%
	Note that the Rota school uses a different
	convention for the generalized Laguerre
	polynomials: what Rota denotes 
	$L_n^{(\alpha)}(x)$
	is $L_n^{(\alpha-1)}(x)$ 
	according to standard terminology.}. 
	The chains also appear in other models,
	e.g., as \emph{tubes} in \cite{GR80}. 
	Laguerre polynomials are featuring as 
	a prominent example in Rota's
	\emph{finite operator calculus}, respectively
	\emph{umbral calculus}, see, e.g.,
	\cite{Ro84} and \cite{RKO73}.
	
\item[--]
	Starting with articles 
	\cite{EG76} by Even and Gillis
	and \cite{Ja76} by Jackson, the
	exploration of the combinatorial aspects
	of the \emph{linearization coefficients}
	for classical orthogonal polynomials
	has been a ``hot topic''
	for quite some time, with Laguerre
	polynomials being of particular interest,
	see, e.g., the work \cite{FZ88}
	by Foata and Zeilberger. 
	Finally, 
	Gessel \cite{Ge89} and 
	Zeng \cite{Ze92}, besides substantial results, offer a systematic view on these achievements.
	
\item[--] 
	In the field of algorithmics and 
	algorithm analysis orthogonal polynomials 
	made their appearance when studying 
	the dynamic behavior
	of simple data structures
	(like lists, queues, dictionaries)
	under insertions, searches, and deletions,
	see \cite{FFV80} as an authoritative paper
	in this direction.
	The deeper reason for this application
	of orthogonal polynomials to discrete
	structures is the modeling via lattice paths
	and their relation to continued fractions,
	as put forward, e.g., by Flajolet 
	in \cite{Fl80} . 
	A combinatorial theory of orthogonal 
	polynomials based on this lattice path model 
	(where the \emph{moment sequences} 
	of these polynomials are of central 
	importance) has been worked out by 
	Viennot.
	It has been presented at a colloquium 
	which was held in honor of 
	Edmond Nicolas Laguerre 
	at the occasion of his 150th birthday 
	in his birthplace Bar-le-Duc (France),
	see \cite{Vi84}.
\end{itemize}
 

\section{Examples for the
		use of the combinatorial models}
\label{sec:examples}

The purpose of this section is to illustrate the 
combinatorial reasoning with Hermite and Laguerre
configurations by discussing typical examples. 

\subsection{Hermite configurations}
\label{ssec:hermiteconfig}


Let $N$ denote a set of cardinality $2n$. 
Here we will examine pairs $(\mu,S)$
where $\mu \in \mf{M}[N]$
and where $S \subseteq N$.
For convenience, put 
$R=N\setminus S$, and let $r=\sharp R$,  
$s = \sharp S= 2n-r$.

For any $\mu \in \mf{M}[N]$ define
\begin{itemize}
\item[--] 
	$\mu_R$ : 
	the set of all
	$\mu$-transpositions 
	contained in $R$,\\
	$A$ : the subset of $R$
	on which $\mu_R$ acts, with
	$\sharp A= 2a$;
\item[--] 
	$\mu_S$ : 
	the set of all
	$\mu$-transpositions 
	contained in $S$,\\
	$C$ : the subset of $S$
	on which $\mu_S$ acts, with
	$\sharp C=2c$;
\item[--] 
	$\beta$ : 
	the remaining transpositions
	of $\mu$,
	which can be considered as
	an element of 
	$\mf{B}[B',B'']$,
	the set of bijections between
	$B'=R\setminus A$ and 
	$B''=S \setminus C$,
	both being
	sets of cardinality $b=n-a-c$.
\end{itemize}
Figure~\ref{fig:laguerre2}
shows the objects $\mu$ and
$S$ separately, in
Figure~\ref{fig:laguerre3}
the decomposition of
$\mu$ using $S$ is displayed.

\begin{figure}[htbp]
	\centering
	\includegraphics[width=4in]
	{matchident-ab.pdf}
	\caption{A perfect matching
	$\mu \in \mf{M}[18]$ and
	a bipartition 
	$R \uplus S =[18]$}
\label{fig:laguerre2}
\end{figure}

\begin{figure}[htbp]
	\centering
	\includegraphics[width=4in]
	{matchident-cd.pdf}
	\caption{Decomposing the perfect
	matching $\mu$ using the
	bipartition $R \uplus S$}
\label{fig:laguerre3}
\end{figure}

We have then the bijective mapping
\[
	\mf{M}[N] \to
	\bigcup_{
	\genfrac{}{}{0pt}{1}{A \uplus B'=R}{ 
	B'' \uplus C=S}}
	\mf{M}[A]\times
	\mf{B}[B',B'']
	\times \mf{M}[C]
	~:~
	\mu \mapsto (\mu_R,\beta,\mu_S),
\]
a quantitative version of which is given by
\begin{align*}
	m_{2n} &= 
	\sum_{2a+b=r} \binom{r}{2a}
	\sum_{2c+b=s} \binom{s}{2c}\,
	m_{2a} \, b! \,
	m_{2c}
	\cr
	&=
	\sum_{2a+b=r} 
	\sum_{2c+b=s}
	\binom{r}{b}\binom{s}{b}
	m_{2a} \, b! \,
	m_{2c}.
\end{align*}	
If we let run $S$ over all subsets of $N$
of cardinality $s$, we get
\[
	m_{2n} \binom{2n}{s}
	=
	(2n)!
	\sum_{2a+b=r} 
	\sum_{2c+b=s}
	\frac{1}{(2a)!\,b!\,(2c)!}
	m_{2a} \, m_{2c},
\]
which can be easily turned into
\[
	m_{2n} \binom{2n}{s}
	=
	\sum_{a+d=n}
	\binom{2n}{2a,2d}\,
	m_{2a} \, m_{2d}\,
	2^{2d-s}\,
	\binom{d}{s-d}
\]
by simple manipulations. 
But this identity also has a simple
combinatorial meaning, now starting reading
from the right side:
for any $\mu \in \mf{H}[N]$
\begin{itemize}
\item[--]  
	we partition the transpositions
	of $\mu$ into two subsets,
	thus obtaining perfect matchings 
	$\mu_A$ on a subset
	$A \subseteq N$ of 
	cardinality $2a$, and
	$\mu_D$ on the set
	$D = N \setminus A$
	of cardinality $2d=2n-2a$;
\item[--]
	we partition the $d$ 
	transpositions of $\mu_D$ into two 
	subsets, thus obtaining perfect 
	matchings $\mu_C$ on a set $C$ 
	of cardinality $2c$ with
	$c=s-d$ respectively 
	$\mu_B$ on a set $B$ of 
	cardinality $2b$ with $b=2d-s$,
	containing $s-d$ respectively
	$2d-s$ transpositions;
\item[--]
	from each transposition
	of $\mu_B$ we select 
	one of the points: this
	defines $B' \subset B$
	and $B''=B \setminus B'$,
	both of cardinality $b=2d-s$,
	and the transpositions
	of $\mu_B$ 
	establishes a bijection
	between $B'$ and $B''$.
\end{itemize}
So we are back to the first
description of $\mf{M}$ given
above, where now 
$S=B''\uplus C$
is indeed of cardinality
$2c+b=2(s-d)+(2d-s)=s$.

This kind of reasoning will be
used below in 
Section~\ref{sec:motivated}.

\subsection{Laguerre configurations}
\label{ssec:laguerreconfig}

As a first illustration for the use of 
Laguerre configurations, I will mention 
a very simple, but useful technique, 
that will be employed later on.

For	three mutually disjoint finite sets 
$X,Y,Z$ one has
\begin{equation}
\label{eqn:laglemma}
	\mf{L}[X \uplus Y, Z]
	\simeq
	\mf{L}[X,Y\uplus Z] \times 
	\mf{L}[Y,Z],
\end{equation}
where ``$\simeq$'' means: 
``there is a 
cycle-count-preserving bijection'' 
between the sets of combinatorial
objects on both sides.   

To be precise, take 
$g \in \mf{L}(X,Y\uplus Z)$
and 
$h \in \mf{L}(Y,Z)$. 
Then the union $g \cup h$ 
(seen as a relation) is not necessarily
an injective mapping:
it may happen that for some 
$z \in Y \uplus Z$
one has
$z=g(x)=h(y)$ for some $x \in X$ 
and some $y \in Y$, but if this
happens, then $x$ and $y$ are
uniquely determined.
In this situation, leave $g$ as it is 
and map $y$ to the starting point of the 
unique $g$-chain that ends in $z$. 
This defines an injective function 
$f=g \star h$ from $X \uplus Y$
into $X \uplus Y \uplus Z$, so 
$f \in \mf{L}(X\uplus Y,Z)$,
and this construction is reversible.
Furthermore 
\[
	\msf{cyc}(g \star h)=
	\msf{cyc}(g)+\msf{cyc}(h).
\] 
The quantitative
counterpart of 
Eq.~(\ref{eqn:laglemma}) 
is nothing but factoring
\[
	(1+\alpha+m)_{k+\ell} =
	(1+\alpha+\ell+m)_k \cdot 
	(1+\alpha+m)_\ell.
\]
This construction, which can also be read 
inversely as a decomposition
of $f \in \mf{L}[X \uplus Y,Z]$
into 
$g \in \mf{L}(X,Y\uplus Z)$
and $h \in \mf{L}(Y,Z)$,
is illustrated in 
Figures~\ref{fig:laguerre4},
\ref{fig:laguerre5}
and
\ref{fig:laguerre6}.

\begin{figure}[htbp]
\centering
	\includegraphics[width=2in]
	{lagconfig-d.pdf}
	\includegraphics[width=2in]
	{lagconfig-c.pdf} 
	\caption{$g \in \mf{L}[X,Y \uplus Z]$ 
		(left) and
		$h \in \mf{L}[Y,Z]$ (right)}
\label{fig:laguerre4}
\end{figure}

\begin{figure}[htbp]
\centering
	\includegraphics[width=2in]
	{lagconfig-b2.pdf}
	\includegraphics[width=2in]
	{lagconfig-b1.pdf} 
	\caption{Superposition of $g$ and $h$ 
		with collisions (left) and with 
		resolved collisions (right)}
\label{fig:laguerre5}
\end{figure}

\begin{figure}[htbp]
\centering
	\includegraphics[width=2in]
	{lagconfig-b.pdf}
	%\includegraphics[width=2in]
	%{Marne-2014/Moll/lagconfig-a.pdf} 
	\caption{$f = g \star h \in 
		\mf{L}[X \uplus Y,Z]$}
\label{fig:laguerre6}
\end{figure}

In terms of the Laguerre polynomials 
the property just mentioned translates into
\begin{equation}
\label{eqn:umbral}
	\mc{L}_n^{(\alpha)}
	(x+y,z) = 
	\mc{L}_n^{(\alpha)}
	(x,\mc{L}^{(\alpha)}(y,z)),
\end{equation}
where the expression on the
right has to be read as an
\emph{umbral} substitution:
\[
	\mc{L}_n^{(\alpha)}
	(x,\mc{L}^{(\alpha)}(y,z))
	=
	\left.
	\mathsf{expand}
	(\mathcal{L}_n^{(\alpha)}(x,w))
	\right|_{w^k \mapsto 
	\mathcal{L}_k^{(\alpha)}(y,z)}.
\]

This umbral property of the Laguerre polynomials
can also be neatly illustrated by using the model 
of matchings on complete bipartite graphs.
Let $M,N$ be disjoint finite sets 
with $\sharp M =m, \sharp N = n$,
and let $\overline{N}$ be a copy of $N$.
For the complete bipartite graph 
$K_{n,n+m} \simeq N \times 
(\overline{N} \uplus M)$
a 2-sorted matching is a pair
$(\sigma,\tau)$ of matchings of $K_{n,n+m}$,
considered as edge sets 
(with $\sigma$, respectively $\tau$ consisting of
red, respectively blue edges), such that
$\sigma \uplus \tau$ is
again a matching of $K_{n,n+m}$.
The weight of such a pair 
$(\sigma,\tau)$ is defined as
\[
	\phi_{x,y,z}(\sigma,\tau)=
	x^{\sharp \sigma} 
	y^{\sharp \tau} 
	z^{n-\sharp \sigma - \sharp \tau},
\]
see Figure~\ref{fig:bipartite2}
for an illustration.
\begin{figure}[htbp]
\centering
	\includegraphics[width=4in]
	{bipartite.pdf} 
	\caption{A 2-sorted matching
	$(\sigma,\tau)$ of $K_{7,10}$
	of weight $x^3 y^2 z^2$ ($\sigma$ in red, 
	$\tau$ in blue, uncovered vertices 
	of $N$ in yellow)}
\label{fig:bipartite2}
\end{figure}

Then $\mc{L}_n^{(m)}(x+y,z)$
is the generating polynomial
for 2-sorted matchings 
$(\sigma,\tau)$ of
$K_{n,n+m}$ w.r.t. $\phi_{x,y,z}$.
But each pair $(\sigma,\tau)$
is specified by
\begin{itemize}
\item[--]
	the number $s = \sharp \sigma$
	with $0 \leq s \leq n$,
\item[--]
	subsets $S \subseteq N$ and
	$S' \subseteq 
	\overline{N}\uplus M$ with
	$\sharp S = \sharp S' = s$,
\item[--]
	a bijection between 
	$S$ and $S'$,
	which is the restriction of 
	$\sigma$ to $S \times S'$,
\item[--]
	a matching of
	$(N \setminus S)
	\times ((\overline{N} 
	\uplus M)\setminus S')$, 
	i.e.,
	the restriction of $\nu$ to 
	$N \setminus S$ and 
	$(\overline{N} \uplus M)\setminus S'$.
\end{itemize}
For any $s$, there are
$\binom{n}{s} \binom{n+m}{s}$
possibilities for 
choosing $(S,S')$ and then
$s!$ possibilities for
the restriction of $\sigma$
which thus contribute a total of
$\mc{L}_s^{(0)}(x,0)= s! x^s$.
Finally, the possibilities for $\tau$
are the counted by
$\mathcal{L}_{n-s}^{(m)}(y,z)$.
As a result:
\[
	\mc{L}_n^{(m)}(x+y,z)
	=
	\sum_{0\leq s \leq n}
	\binom{n}{s}
	\binom{n+m}{s}
	\mc{L}_s^{(0)}(x,0)\,
	\mc{L}_{n-s}^{(m)}(y,z),
\] 
which is equivalent to 
Eq.~(\ref{eqn:umbral}).
This will be used later in Section~\ref{sec:binomial}.



\section{Differential operators
		for Laguerre configurations}
\label{sec:differential}

It is interesting to see how familiar 
differential (or difference) formulas
for the Laguerre polynomials
can be interpreted (or deduced)
from a combinatorial perspective.

For fixed $n\in \mathbb{N}$,
let 
\[
	\mf{L}_n =
	\bigcup_{A \oplus B = [n]}
	\mf{L}[A,B]
\]
denote the set of all Laguerre configurations 
of order $n$, and for $0 \leq k \leq n$
\[
	\mf{L}_{n,k}= 
	\bigcup_{
	\genfrac{}{}{0pt}{1}{A \oplus B = [n]}
	{\sharp A = k}}
	\mf{L}[A,B].
\]
Then, as mentioned before,
$\mf{L}_{n,0}$ 
is a singleton set, consisting of the function 
$\lambda_\emptyset$
with empty domain $\emptyset$, and
$\mf{L}_{n,n}$ is nothing but the set of 
all permutations of $[n]$. 
The corresponding generating polynomials are
\[
	\mathcal{L}_{n,0}^{(\alpha)}(x,y)
	= y^n,
	\hskip1cm
	\mathcal{L}_{n,n}^{(\alpha)}(x,y)=
	(1+\alpha)_n \,x^n.
\]
The set of all Laguerre configurations on $[n]$
can be constructed iteratively by starting with 
$\lambda_\emptyset$
on level $k=0$ by  
``adding $n$ functional arrows'', 
one at a time, thus passing from
$\mf{L}_{n,k}$ to $\mf{L}_{n,k+1}$
for $0 \leq k < n$, as follows:
\begin{itemize}
\item[--]
	take $\lambda \in \mf{L}[A,B]$, 
	where $\sharp A=k$,
\item[--]
	pick one element $b \in B$ and 
	one element $c \not\in \lambda(A)$,
\item[--] 
	add to $\lambda$ the 
	new arrow $b \to c$.
\end{itemize}
Then 
$\lambda'=\lambda \cup \{b\to c\}
\in \mf{L}[A',B']$, where
$A'=A \cup \{b\}$ and
$B'=B \setminus \{b\}$.
Among all the $n-k$ possible choices
for $c$ (given one of the $n-k$
possible choices for $b$) there is
precisely one which leads to the
creation of a new cycle, namely 
when $c$ is the start vertex of the (unique) 
$\lambda$-chain that ends in $b$.
Note that for recovering $\lambda$ from
$\lambda'$ one needs to know which 
of the $k+1$ arrows from $\lambda'$
was added last.

Taking all possibilities into consideration, 
and expressing the choices by differential 
``pointing'' operators, one sees that
\begin{equation}
\label{eqn:lagdiff}
	(1+\alpha + y\, \partial_y)
	(x\, \partial_y)\,
	\mathcal{L}_{n,k}^{(\alpha)}(x,y)
	= (k+1)\,
	\mathcal{L}_{n,k+1}^{(\alpha)}(x,y)
	= (x\, \partial_x)\, 
	\mathcal{L}_{n,k+1}^{(\alpha)}(x,y).
\end{equation}
Note that $(x \partial_y)$ 
randomly selects in $\lambda$
a point $b$ from $B$ (variable $y$)
and turns it into
a point of $A'$ (variable $x$).
Then $c$ is chosen as the start
vertex of a $\lambda$-chain, viz.,
\begin{itemize}
\item[--]
	either of the unique $\lambda$-chain 
	ending in $b$, thus
	forming a $\lambda'$-cycle 
	(which gets valuation $1+\alpha$),
\item[--]
	or by selecting (by using 
	$y\partial_y$)
	any of the remaining
	points from $B\setminus\{b\}$ .
\end{itemize}
Thus one gets by induction
\begin{align*}
	\frac{\left[
	(1+\alpha + y\, \partial_y)
	(x\, \partial_y)
	\right]^k}{k!}\,
	\mathcal{L}_{n,0}^{(\alpha)}(x,y)
	=
	\frac{\left[
	(1+\alpha + y\, \partial_y)
	(x\, \partial_y)
	\right]^k}{k!}\, 
	y^n
	=
	\mathcal{L}_{n,k}^{(\alpha)}(x,y),
\end{align*}
and, by summing over $k$,
\[
	\exp\left[(1+\alpha+y\, \partial_y)
	(x \,\partial_y)\right] y^n
	=
	\mathcal{L}_n^{(\alpha)}(x,y),
\]
which should be compared to
Eq.~(1.5) in \cite{BDGP16}.

Summing identity (\ref{eqn:lagdiff})
over $k$, we get
\[
	(1+\alpha + y\, \partial_y)(x\, \partial_y)\,
	\mathcal{L}_{n}^{(\alpha)}(x,y)
	= (x\, \partial_x) \,
	\mathcal{L}_{n}^{(\alpha)}(x,y),
\]
which is nothing but the hypergeometric
differential equation for the Laguerre 
polynomials in homogeneous form.

More examples of a combinatorially inspired
use of differential operators in the context 
of Laguerre and Jacobi polynomials
can be found in 
\cite{LS84}.


\section{An natural approach
	to lacunary Laguerre series}
\label{sec:natural}

The technique of 
Section~\ref{ssec:laguerreconfig}
can be used for obtaining lacunary Laguerre 
series in a very natural setting.
The idea is that the Laguerre configurations
counted by 
$\mc{L}_{2n}(x,y)$
can be seen as configurations on a set 
$\overline{N}=N \uplus N'$,
where $N$ is a set of cardinality $n$,
and where $N'$ is a copy of $N$
with a natural bijection (perfect matching) 
between $N$ and $N'$. 

	
The lacunary Laguerre
series (3.11) in \cite{BDGP16}, viz.
\begin{equation}
\label{eqn:natural0}
	\sum_{n \geq 0}
	t^n\, 
	L_{2n}(x) =
	\frac{1}{1-t} 
	\sum_{r \geq 0}
	\frac{L_r^{(r)}({x/2})}{(1/2)_r}
	\left[
	- \frac{t\,x}{2(1-t)}
	\right]^r,
\end{equation} 
is the special case for $\alpha \to 0$ of
\begin{equation}
\label{eqn:natural1}
	\sum_{n \geq 0}
	\frac{(1/2)_n \,t^n}{
	((1+\alpha)/2)_n}\, 
	 L_{2n}^{(\alpha)}(x) =
	\frac{1}{(1-t)^{(1+\alpha/2)}} 
	\sum_{r \geq 0}
	\frac{L_r^{(r+\alpha)}
	(x/2)}{((1+\alpha)/2)_r}
	\left[
	- \frac{t\,x}{2(1-t)}
	\right]^r.
\end{equation}
By using the binomial series and comparison 
of coefficients for $t^n$, one gets
\begin{equation}
\label{eqn:natural2}
	(2n)!\, L_{2n}^{(\alpha)}(x)
	=
	\sum_{0 \leq r \leq n}
	\binom{n}{r} \,r!\,
	2^r\, L_r^{(r+\alpha)}
	({x/2})\,
	(1+2r+\alpha)_{2n-2r}
	(-x)^r,
\end{equation}	
or, in our notation,
\begin{equation}
\label{eqn:double}
	\mathcal{L}_{2n}^{(\alpha)}(x,y) =
	\sum_{0\leq r \leq n}
	\binom{n}{r}\,
	(1+\alpha+2r)_{2n-2r}\,
	\mathcal{L}_r^{(\alpha+r)}(2x,y)\,
	x^{2n-2r} \,y^r.
\end{equation}

Before delving into combinatorics, 
a short remark about these identities 
is in order. By using
\[
	\frac{((1+\alpha)/2)_n\,
	(1+\alpha/2)_n}
	{((1+\alpha)/2)_r\,
	(1+\alpha/2)_r}=
	(1+\alpha+2r)_{2n-2r} 4^{r-n},
\]
Eq.~(\ref{eqn:natural2})
is easily seen to be equivalent to
\begin{equation}
	\frac{(1/2)_n}{
	((1+\alpha)/2)_n(1+\alpha/2)_n}
	L_{2n}^{(\alpha)}(x) =
	\sum_{0\leq r \leq n}
	\frac{(-x/2)^r}{
	((1+\alpha)/2)_r(1+\alpha/2)_r}
	L_r^{(r+\alpha)}(x/2)  
	\frac{1}{(n-r)!},
\end{equation}
which leads to the generating function of 
Eq.~(\ref{eqn:natural1}).  
By exchanging the roles of $((1+\alpha)/2)_n$ 
and $(1+\alpha/2)_n$ when passing to the 
generating function one may also obtain
\begin{equation}
\label{eqn:natural3}
	\sum_{n \geq 0}
	\frac{(1/2)_n\,t^n}{
	(1+\alpha/2)_n}
	L_{2n}^{(\alpha)}(x)
	=
	\frac{1}{(1-t)^{
	(1+\alpha)/2}}
	\sum_{r \geq 0}
	\frac{1}{(1+\alpha/2)_r}
	L_r^{(\alpha+r)}
	({x/2})\,
	\left[\frac{-x\,t}{2(1-t)}\right]^r.
\end{equation}
Identities (\ref{eqn:natural1})
and (\ref{eqn:natural3})
look deceptively similar, yet
they are not quite the same 
(although they may be considered equivalent 
in view of the preceding argument).
From (\ref{eqn:natural1})
on gets (\ref{eqn:natural0})
by a simple specialization
$\alpha \to 0$, but the same 
substitution leads from
(\ref{eqn:natural3}) to
\begin{equation}
\label{eqn:natural4}
	\sum_{n \geq 0}
	\binom{2n}{n}
	\left(\frac{t}{4}\right)^n
	L_{2n}(x)
	=\frac{1}{(1-t)^{1/2}}
	\sum_{r \geq 0}
	\frac{1}{r!}
	L_r^{(r)}({x/2})\,
	\left[\frac{-x\,t}{2(1-t)}\right]^r.
\end{equation}
Remark that the identity in
Eq.~(\ref{eqn:natural3}) 
occurs as 
Eq.~(4.6) of \cite{BDGP16},
see also my remarks reproduced
in Appendix A of that article. 
Here this result will show up
again in Section~\ref{sec:binomial}. 

\medskip

We now proceed towards a combinatorial
proof of (\ref{eqn:double}).
Let $N$ be a set of cardinality
$n$ and let $N_1,N_2$ be two
copies of $N$, and 
$\overline{N}=N_1 \uplus N_2$.
There is a natural bijection
$\rho =N_1 \leftrightarrow N_2$, 
for $\xi \in \ol{N}$
we write $\xi'=\rho(\xi)$.
For a subset $A \subseteq \ol{N}$ put
$A'=\rho(A)$ and
$A_i = A \cap N_i~(i \in \{1,2\})$.

From the bipartition
$\ol{N}=N_1 \uplus N_2$ 
one naturally gets, for any bipartition
$\ol{N}=X \uplus Y$,
a 4-partition
$\ol{N}=A \uplus B \uplus C \uplus D$ 
as follows:
\[
	\text{for}~~\xi \in \ol{N} ~:~\xi \in
	\begin{cases}
	A, &\text{if}~ (\xi,\xi') \in 
	X \times X, 
	\cr
	B, & \text{if}~ (\xi,\xi') \in 
	X \times Y,
	\cr
	C, &
	\text{if}~ (\xi,\xi') \in 
	Y \times X,
	\cr
	D, &
	\text{if}~ (\xi,\xi') \in 
	Y \times Y.
	\end{cases}
\]
Then $X = A \uplus B, Y = C \uplus D$ 
and the partition
$(A,B,C,D)$ 
satisfies
\begin{equation}
\label{eqn:conds}
A = A', B_1=C_2', B_2=C_1',D=D'.
\end{equation}
Schematically 
(see Figure~\ref{fig:laguerre7},
with bold contour lines indicating the regions 
where arrows are defined)
\begin{figure}[htbp]
	\centering
	\includegraphics[width=2.5in]
	{double-1a.pdf} 
	\caption{The scheme for
	$\mf{L}[X,Y]$ before decomposition}
\label{fig:laguerre7}
\end{figure}

Looking at the corresponding
Laguerre configurations, one gets	
\begin{align*}
	\mf{L}[X,Y]
	&=
	\mf{L}[A \uplus B,
	C \uplus D]
	\cr
	&\simeq
	\mf{L}[A,B 
	\uplus C\uplus D] 
	\times
	\mf{L}[B, C \uplus D]
	\cr
	&\simeq
	\mf{L}[A,B \uplus
	C\uplus D]
	\times
	\mf{L}[B,D_1\,;\,
	C_1 \uplus C_2 \uplus D_2]
	\cr
	&=
	\mf{L}[A,N \setminus A]
	\times
	\mf{L}[B,D_1\,;\,(N \setminus A)_2],
	\end{align*}
where the decomposition property, 
as discussed in 
Section~\ref{ssec:laguerreconfig},
see Eq.~(\ref{eqn:laglemma}),
has been used.
The situation for the two Laguerre-factors 
(omitting arrows) is now as 
depicted in 
Figure~\ref{fig:laguerre8}:
\begin{figure}[htbp]
	\centering
	\includegraphics[width=3.5in]
	{double-1b.pdf} 
	\caption{The scheme for
	$\mf{L}[X,Y]$ after decomposition}
\label{fig:laguerre8}
\end{figure}

We obtain
\begin{align*}
	\mathcal{L}_{2n}^{(\alpha)}(x,y)
	&=
	\textstyle\sum_{X \uplus Y = \ol{N}}
	\sum 
	\big\{
	\omega_{x,y}^{
	(\alpha)}(f)\,;\,
	f \in \mf{L}[X,Y]
	\big\}
	\cr
	&=
	{\textstyle\sum'}_{
	A \uplus B 
	\uplus C \uplus D
	=\overline{N}}{}
	\textstyle\sum\big\{ 
	\omega_{x,1}(g)\,;\,
	g \in \mf{L}[A,\ol{N}
	\setminus A]
	\big\} \times
	\cr
	&\hskip1.5cm \times
	\textstyle\sum 
	\big\{ 
	\omega_{x,y,y}(h)\,;\,
	h \in 
	\mf{L}[
	B_1 \uplus C_1,D_1\,;\,
	(N\setminus A)_2]
	\big\},
	\end{align*}
where $\sum'$ means that one sums over 
partitions $(A,B,C,D)$ of $\ol{N}$
that satisfy Eq.~(\ref{eqn:conds}).	
Then one realizes:
\begin{itemize}
\item[--] 
	For each $0 \leq a \leq n$
	there are $\binom{n}{a}$
	choices for the $A$-part.
\item[--] 
	For each $A$-part
	the contribution from the 
	$g \in \mf{L}
	[A,\ol{N} \setminus A]$
	is $(1+\alpha+2b)_{2a}
	x^{2a}$, where $b=n-a$.
\item[--]
	For each $A$, 
	the contribution coming
	from all the
	$h \in 
	\mf{L}[B,D_1\,;\,
	 (N \setminus A)_2]$
	looks if it should be 
	$\mc{L}_b^{\alpha+b}(x,y)\,y^b$, 
	because
	$\sharp B +\sharp D_1=
	\sharp C +\sharp D_2=n-a=b$,
	but in addition 
	the multiplicity from
	partitioning $B$ into
	$B_1$ and $B_2$ in all
	possible ways (which all
	lead to the same contribution)
	has to be taken into account.
	This multiplicity is 
	$2^{\sharp B}$, which
	is accommodated
	by simply replacing
	the variable $x$ by $2x$.
 
\end{itemize}
If we put all this together 
this gives us
Eq.~(\ref{eqn:double}), 
which we now write as
\begin{equation}
\label{eqn:double2}
	\mathcal{L}_{2n}^{(\alpha)}(x,y) =
	\sum_{a+b=n}
	\binom{n}{a,b}\,
	(1+\alpha+2b)_{2a}\,
	x^{2a}
	\cdot
	\mathcal{L}_b^{(\alpha+b)}(2x,y)\,y^b.
\end{equation}
	

A surplus of the proof just given is that 
it immediately tells you what happens for
a triple lacunary series, see identity (3.12) of 
\cite{BDGP16}, 
by looking at the combinatorial picture
by stacking three copies of a base set $N$ 
on top of each other, and adapting the
definitions of $A$, $B$, $C$ 
and $D$, see 
Figure~\ref{fig:laguerre8a} for 
a schematic illustration.

\begin{figure}[htbp]
	\centering
	\includegraphics[width=5in]
	{triple.pdf} 
	\caption{The scheme for
	$\mf{L}[X,Y]$ in the triple lacunary case, 
	again with $A$ in red, $B$ in green,
	$C$ in cyan, $D$ in yellow.}
\label{fig:laguerre8a}
\end{figure}
The result is
\begin{multline*}
	\mathcal{L}_{3n}^{(\alpha)}(x,y)
	\\=
	\sum_{a+b+c=n}
	\binom{n}{a,b,c}
	(1+\alpha+b+3c)_{3a+2b}\,
	\binom{3}{1}^b\,x^{3a+2b}
	\cdot
	\mathcal{L}_c^{(\alpha+b+2c)}(3x,y)\,
	y^{b+2c}.
\end{multline*}
	
A completely analogous approach
for a quadruple lacunary series gives	
\begin{multline*}
	\mathcal{L}_{4n}^{(\alpha)}
	(x,y)
	=
	\sum_{a+b+c+d=n}
	\binom{n}{a,b,c,d}
	(1+\alpha+b+2c+4d)_{4a+3b+2c}
	\binom{4}{1}^b
	\binom{4}{2}^c
	\times
	\\
	\times 
	 x^{4a+3b+2c}
	\mathcal{L}_d^{
	(1+\alpha+b+2c+3d)}(4x,y)\,
	y^{b+2c+3d}.
\end{multline*}
The general pattern should now be clear.



\section{The simplest lacunary Laguerre series}
\label{sec:simplest}

In this section a different approach to 
lacunary Laguerre series will be employed,
namely correlating Laguerre configurations 
with arbitrary perfect matchings on a ground
set.
 
Identity (3.5) from 
\cite{BDGP16} 
reads 
\begin{equation}
\label{eqn:lacunary1}
	\sum_{n \geq 0}
	\frac{t^n}{n!}
	L_{2n}(x) =
	e^t \cdot \sum_{r \geq 0} 
	\frac{(i x \sqrt{t})^r}{r!^2}
	H_r(i \sqrt{t}).
\end{equation}
The particular feature of this identity is 
that the $n$-th term on the l.h.s. comes
with the Laguerre polynomial
$L_{2n}(x)$, but with $n!$
(instead of $(2n)!$), as one would expect) 
in the denominator.
If we force $(2n)!$ to appear in the denominator 
and make the innocuous substitution 
$t \to t^2/2$, we get an interesting factor: 
\[
	\sum_{n \geq 0}
	\frac{t^{2n}}{(2n)!}
	\frac{(2n)!}{n! \, 2^n}
	L_{2n}(x)
	=
	\sum_{n \geq 0}
	\frac{t^{2n}}{(2n)!}\,
	m_{2n} \,L_{2n}(x)
	=
	\sum_{n \geq 0}
	\frac{t^{n}}{n!}\,
	m_{n}\, L_{n}(x).
\]
The matching numbers $m_n$ from 
Section~\ref{ssec:hermite} appear!
This suggests a combinatorial meaning: 
consider it as an exponential 
generating function for pairs 
$(\mu,\lambda) \in \mf{M}[A] \times
\mf{L}[A]$, i.e.,
$\mu$ is a perfect matching and 
$\lambda$ is a Laguerre configuration on 
the same vertex set $A$, where $A$ must have 
even cardinality by the perfectness of 
$\mu$.
 
Rewriting Eq.~(\ref{eqn:lacunary1})
with $t \to t^2/2$ and $x \to -y$ 
in terms of our``combinatorial'' Laguerre 
and Hermite polynomials, we are led to
\[
	\sum_{n \geq 0}
	\frac{t^{2n}}{(2n)!}
	\frac{(2n)!}{n!2^n}
	\frac{1}{(2n)!}
	\mathcal{L}_{2n}^{(0)}(1, y)
	 =e^{t^2/2} \cdot \sum_{n \geq 0}
	\frac{(yt)^n}{n!^2}
	\mathcal{H}_n(t,1),
\]
and then the substitutions 
$yt \to y$ and $t \to x$
give us
\begin{equation}
\label{eqn:lacunary2}
	\sum_{n \geq 0}
	\frac{m_{2n}}{(2n)!}
	\frac{1}{(2n)!} 
	\mathcal{L}_{2n}^{(0)}(x,y)
	 =e^{x^2/2} \cdot \sum_{n \geq 0}
	\frac{1}{n!^2}
	\mathcal{H}_n(x\,y, y).
\end{equation}
This will now be proven by a
combinatorial counting argument.
First note that all terms on both sides of 
(\ref{eqn:lacunary2})
indeed have an even total degree in $x,y$. 
Therefore it suffices to consider the
contributions for a fixed 
total degree $2n$ in $x,y$
on both sides by writing
\begin{equation}
\label{eqn:lacunary3}
	m_{2n} \cdot 
	\mathcal{L}_{2n}^{(0)}(x,y)
	=
	(2n)!^2
	\left[
	e^{x^2/2} 
	\cdot
	\sum_{s \geq 0} 
	\frac{1}{s!^2} 
	\mathcal{H}_s(x\,y,y)
	\right]^{\langle 2n \rangle},
\end{equation}
where 
$[\ldots]^{\langle 2n \rangle}$
denotes the sum of the terms
of total degree $2n$ in 
$[ \ldots ]$.

Let $N$ denote a set of cardinality $2n$. 
The left-hand side of 
(\ref{eqn:lacunary3})
enumerates pairs 
$(\mu,\lambda) \in \mf{M}(N)\times \mf{L}(N)$. 
This can be evaluated explicitly and shown to
be equal to the right-hand side.

Fix a partition 
$R \uplus S=N$ of the base set $N$,
let $r=\sharp R$ and 
$s = \sharp S= 2n-r$. 
The following argument gives the contribution
coming from the 
$(\mu,\lambda)$ with 
$\lambda \in \mf{L}[R,S]$. 
Actually, this contribution depends only 
on the cardinalities of $R$ and $S$, 
not on the functional structure of 
$\lambda$ !
  
Now take the bijection considered in 
Section~\ref{ssec:hermiteconfig}, 
\[
	\mf{M}[N] \to
	\bigcup_{
	\genfrac{}{}{0pt}{1}{A \uplus B'=R}
	{B'' \uplus C=S}}
	\mf{M}[A]\times
	\mf{B}[B',B'']
	\times \mf{M}[C]
	:
	\mu \mapsto 
	(\mu_R,\beta,\mu_S),
\]
with 
$r=\sharp R=2a+b$ and 
$s=\sharp S = 2c+b$.
Furthermore note that $\mu_S$ 
can be considered as an element of 
$\mf{H}[B'',C]$.
Now let us count:
\begin{itemize}
\item[--]
	For fixed $(A,B',B'',C)$
	the number of 
	relevant $(\mu_R,\beta,\mu_S)$
	is, by construction,
	$m_{2a} \cdot b! \cdot m_{2c}.$
\item[--]
	The number of choices
	for $(A,B',B'',C)$ for fixed
	$(a,b,c)$ is
	$\binom{r}{2a} \binom{s}{2c}$.
\item[--]
	For fixed $(R,S)$ with 
	cardinalities $(r,s)$ there are\\
	$\sharp \mf{L}[R,S] = 
	(1+s)_r={(2n)!/s!}$ 
	Laguerre configurations.
\item[--]
	There are
	$\binom{2n}{s}$
	choices of the ordered pair
	$(R,S)$ for given $(r,s)$,
	which leads to a valuation
	$\omega_{x,y}^0(\lambda)=x^r y^s$
	of the Laguerre
	configurations,
	cycles are (not yet) counted.
\end{itemize}	

To summarize, the l.h.s. of 
Eq.~(\ref{eqn:lacunary3})
can be written as
\begin{align*}
	\sum_{r+s=2n}&
	\binom{2n}{s}\,
	\frac{(2n)!}{s!}\,
	x^r y^{s}\,
	\sum_{2a+b=r} \binom{r}{2a}
	\sum_{2c+b=s} \binom{s}{2c}\,
	m_{2a} \, b! \,
	m_{2c}
\cr
	&=
	\sum_{r+s=2n}\!
	\frac{(2n)!}{r!s!}
	\frac{(2n)!}{s!}
	\sum_{2a+b=r}\!\!
	\frac{r!}{(2a)!b!}
	m_{2a} \,x^{2a}
	\sum_{2c+b=s}
	\binom{s}{2c}
	 b! \, m_{2c}\,
	(x\,y)^b y^{2c}
\cr
	&=
	(2n)!^2
	\sum_{r+s=2n}
	\sum_{2a+b=r}
	\frac{m_{2a}}{(2a)!} \,x^{2a}
	\frac{1}{s!^2}
	\mathcal{H}_s(x\,y,y)
\cr
	&=
	(2n)!^2
	\left[
	\sum_{a\geq 0}
	 m_{2a}\frac{x^{2a}}{(2a)!}
	\sum_{s \geq 0}
	\frac{1}{s!^2} \,
	\mathcal{H}_s(x\,y,y)
	\right]^{\langle 2n \rangle} 
\cr
	&=
	(2n)!^2
	\left[
	e^{x^2/2}
	\sum_{s \geq 0}
	\frac{1}{s!^2} \,
	\mathcal{H}_s(x\,y,y)
	\right]^{\langle 2n \rangle}.
\end{align*}
	
The combinatorial proof of 
Eq.~(\ref{eqn:lacunary3}) 
and hence of 
Eq.~(\ref{eqn:lacunary1}) 
is now complete. 
One could easily add cycle counting
with a parameter $\alpha$
to this proof, thus obtaining a 
combinatorial proof of identity (3.6) of 
\cite{BDGP16}.
But much more can be done by extending the 
combinatorial perspective.
Instead of pairing Laguerre configurations
with \emph{perfect} matchings, one
can pair them with \emph{arbitrary}
matchings on the same ground set.
This will be done in the next section, 
and the $\alpha$ for cycle counting
will also be included in this generalization. 


\section{An extension
		motivated by combinatorics}
\label{sec:motivated}

The combinatorial picture presented in the
foregoing 
Section~\ref{sec:simplest}
leads immediately to the following idea for
an extension: 
play the same game, but now with arbitrary 
involutions (Hermite configurations) 
instead of perfect matchings! 
Note that the use of perfect matchings
forced terms occurring on the left of 
(\ref{eqn:lacunary2}) 
to have an even total degree --- 
hence the lacunarity of the series expansion! 
If we replace 
$\mf{M}\times\mf{L}$ by
$\mf{I}\times\mf{L}$, then
lacunarity gets lost, but otherwise
one can hope that a similar counting 
argument would go through. 
This is is indeed the case and, interestingly,
now the functional structure of the Laguerre 
configurations plays a role, whereas in the 
previous proof only the underlying pair of sets 
$(X,Y)$ was relevant.
In addition, in this enlarged set-up also the
cycle counting for the Laguerre configurations
will be tracked by the parameter $\alpha$.

The generating function identity to be proven 
in this section, written in terms of the
combinatorial Hermite and Laguerre polynomials,
is
\begin{equation}
\label{eqn:extension1}
	\sum_{n\geq 0} 
	\frac{\mathcal{H}_n(u,v)}{n!} \, 
	\frac{\mathcal{L}_{n}^{(\alpha)}(x,y)}
	{(1+\alpha)_n} =
	\mathcal{M}(x\,v)
	\sum_{s,p \geq 0}
	\frac{\mathcal{H}_s(x\,y\,v^2,y\,v)}{s!}
	\frac{\mathcal{L}_p^{(\alpha+s)}(x\,u,y\,u)}
	{p!\, (1+\alpha)_{s+p}}.
\end{equation}

Before delving into the details,
I would like to stress that
--- at least from my personal perspective ---
it would be difficult to imagine such an identity 
without being guided by combinatorial imagination.

By considering the contributions
of total degree $n$ on both sides,
one finds that identity
(\ref{eqn:extension1})
is equivalent to
\begin{multline}
\label{eqn:extension2}
	\mathcal{H}_n(u,v) \cdot
	\mathcal{L}_n^{(\alpha)}(x,y)
	\\=
	\sum_{r+s+p=n}\!\!
	\binom{n}{r,s,p}\,
	r! \,(1+\alpha+s+p)_r
	\!\cdot\!
	\left[
	 e^{(x\,v)^2/2}
	\!\cdot\! 
	\mathcal{H}_s(x\,y\,v^2,y\,v)
	\!\cdot\! 
	\mathcal{L}_p^{(\alpha+s)}
	(x\,u,y\,u)
	\right]^{\langle n\rangle}\!,
\end{multline}
where again
$[\ldots]^{\langle n \rangle}$
means that the homogeneous part of degree $n$ 
(in one of the variable pairs $\{x,y\}$ 
or $\{u,v\}$, for the other pair
this follows automatically) 
has to be taken.

\begin{figure}[h]
	\centering
	\includegraphics[width=12cm]
	{hermite+laguerre.pdf}
	\caption{$\sigma \in \mathcal{H}[U,V]$ 
	and $\lambda \in \mf{L}[X,Y]$ 
	separately}
\label{fig:laguerre9}
\end{figure}

The combinatorial argument used here directly 
generalizes the approach taken in 
Section~\ref{sec:simplest}.
For a set $N$ of cardinality $n$ take any
$(\sigma,\lambda) \in 
\mf{H}[N] \times 
\mf{L}[N]$,
more precisely, 
$\sigma \in \mf{H}[U,V]$
and 
$\lambda \in \mf{L}[X,Y]$,
so that
$N=U \uplus V$ and $N=X \uplus Y$ 
are two bipartitions of $N$.
To shorten the notation somewhat, we will use 
$AB \equiv A \cap B$ for any two sets $A,B$ 
in the sequel.

\begin{figure}
	\centering
	\includegraphics[width=12cm]
	{super.pdf}
	\caption{Superposition
	$(\sigma,\lambda) \in 
	\mf{H}[U,V] \times \mf{L}[X,Y]$}
\label{fig:laguerre10}
\end{figure}


\begin{figure}
	\centering
	\includegraphics[width=12cm]
	{all.pdf}
	\caption{Superposition
	$(\sigma,\lambda) \in 
	\mf{H}[U,V] \times \mf{L}[X,Y]$ 
	with matching set $W$ and 
	matching between $WX$ and $WY$.}
\label{fig:laguerre11}
\end{figure}



\begin{figure}
	\centering
	\includegraphics[width=12cm]
	{final.pdf}
	\caption{
	Final configuration after changing
	the critical arrows:
	$\sigma_{VX} \in 
	\mf{H}[\emptyset,VX \setminus WX]$,
	$\beta \in \mathcal{B}[WY,WX]$, 
	$\sigma_{VY} \in \mf{H}[WY,VY \setminus WY]$,
	$\lambda_{VX} \in \mf{L}[VX,UX \uplus Y]$, 
	$\lambda_{UX} \in \mf{L}[UX,Y]$
\label{fig:laguerre12}
}

\end{figure}

	Let $\sharp U=p$,
	$\sharp V=q=n-p$,
	$\sharp X =i$, 	 
	$\sharp Y=j=n-i$.
	The two bipartitions of
	$N$ define 
\begin{itemize}
\item[--] 
	a bipartition
	$UX \uplus UY$  of $U$,
	with $\sharp UX = k$,
	$\sharp UY = \ell$,
\item[--] 
	a bipartition
	$VX \uplus VY$  of $V$,
	with $\sharp VX = r,
	\sharp VY = s$.
\end{itemize}	
Now 
$\sigma \big|_V$ is
a perfect matching of $V$, 
so that the ideas of 
Section~\ref{ssec:hermiteconfig}
can be applied w.r.t. the bipartition of 
$V=VX \uplus VY$.
This defines a set 
$W\subseteq V$ 
which contains precisely the transpositions of 
$\sigma \big|_V$
which ``cross the border'' 
between $VX$ and $VY$.
This gives a 4-partition  
\[
	V=(VX \setminus WX) 
	\uplus WX \uplus 
	WY \uplus (VY\setminus WY)
\] 
with 
$\sharp (VX \setminus WX) = 2a, 
\sharp WX = \sharp WY= b, 
\sharp (VY \setminus WY)= 2c$.

Then 	
\begin{itemize}
\item[--]
	$\sigma_{VX}=
	\sigma|_{VX\setminus WX} 
	\in \mf{M}[VX\setminus WX]$
\item[--]
	$\sigma_{VY} \in 
	\mf{H}[WY,VY\setminus WY]
	\text{ with }
	\sigma_{VY}
	\big|_{VY \setminus WY} \in 
	\mf{M}[VY \setminus WY]
	\text{ and }
	\\  
	\msf{fix}(\sigma_{VY})=WY$,
\item[--]
	$\beta=
	\sigma\big|_{WX \uplus WY}
	\in \mf{B}[WX,WY]$.
\end{itemize}
\medskip
%	Note that $2a+2b+2c= 
%	\sharp Q=q$,
%	so that $a+b+c=q/2$ is
%	the number of transpositions of 
%	$\sigma$. 
We have
$\sharp VX=r$ and 
$\sharp VY=s$,
so that in particular
	\[
	k+\ell = p,~ 
	 r+s = 2(a+b+c) = q,
	~k+r=i,~s+\ell=j.
	\]
As for 
$\lambda \in \mf{L}[X,Y]$, 
due to 
$X = UX \uplus VX$,
and using the decomposition of
Laguerre configurations
as in (\ref{eqn:laglemma}),
we have the equivalence
\[
	\mf{L}[UX \uplus VX,Y]
	\ni\lambda
	\leftrightarrow
	(\lambda_{VX},\lambda_{UX}) \in 
	\mf{L}[VX,UX \uplus Y] \times
	\mf{L}[UX,Y],
\]
and, furthermore,
\[
	\msf{cyc}(\lambda)
	= 
	\msf{cyc}(\lambda_{UX})+
	\msf{cyc}(\lambda_{VX}).
\]
For fixed $U,V,X,Y$ and hence for fixed 
$UX,UY,VX,VY$
the transformation
\[
	(\sigma,\lambda) \mapsto
	(\sigma_{VX},
	\beta,\sigma_{VY},
	\lambda_{VX},
	\lambda_{UX})
\]
is a bijection which
preserves cycle counting between
\[
	\mf{H}[U,V] \times \mf{L}[X,Y]
\]
and the union of
\[
	%\bigcup_{
	%\genfrac{}{}{0pt}{1}
	%{(VX \setminus WX)\uplus WX=VX} 
	%{(VY \setminus WY)  \uplus WY=VY}}
	\mf{M}[VX \setminus WX] \times
	\mf{B}[WX,WY] \times
	\mf{H}[WY,VY \setminus WY] \times
	\mf{L}[VX,UX \uplus Y] \times
	\mf{L}[UX, Y],
\]
running over all bipartitions
$(VX \setminus WX)\uplus WX=VX$ and  
$(VY \setminus WY)  \uplus WY=VY$.
The correspondence is indeed literally:
\[
	\begin{array}{ccccc}
	\sigma_{VX} & \beta & \sigma_{VY} &
	\lambda_{VX} & \lambda_{UX}
	\cr
	\updownarrow &
	\updownarrow &
	\updownarrow &
	\updownarrow &
	\updownarrow 
	\cr
	\mf{M}[VX \setminus WX] &
	\mf{B}[WX,WY] &
	\mf{H}[WY,VY \setminus WY] &
	\mf{L}[VX,UX \uplus Y] &
	\mf{L}[UX, Y]
	\end{array}\\
\]
Note that the cycle counting part from 
$\lambda$ splits into the 
corresponding parts of 
$\lambda'$ and $\lambda''$:
\[
	(1+\alpha+j)_i =
	(1+\alpha+j)_k \cdot
	(1+\alpha+j+k)_r =
	(1+\alpha+j)_k \cdot
	(1+\alpha+s+p)_r
\]
Summing now over all possible partitions
\[
(VX\setminus WX) 
\uplus WX 
\uplus WY 
\uplus (VY\setminus WY)
\uplus UX \uplus UY
\] of $N$,
and using the weight function
\[
	\nu_{u,v}(\sigma) \cdot
	\omega_{x,y}^{\alpha}(\lambda),
\]
we obtain the expression
\[
	\sum_{r+s+p=n}
	\binom{n}{r,s,p}\,
	r! \,
	(1+\alpha+s+p)_r
	\cdot
	\left[
	 e^{(x\,v)^2/2}
	\!\cdot\! 
	\mathcal{H}_s(x\,y\,v^2,y\,v)
	\!\cdot\! 
	\mathcal{L}_p^{(\alpha+s)}(x\,u,y\,u)
	\right]^{\langle n\rangle},
\]
where the contribution
\begin{itemize}
\item[--] 
	from
		$\sigma_{VX} \in 
		\mf{M}[VX\setminus WX]$
		goes into $\mc{M}(x\,v)=
		e^{(x\,v)^2/2}$,
\item[--]  
	from
		$(\beta,\sigma_{VY}) \in
		\mf{B}[WX,WY] \times 
		\mf{H}[WY,VY\setminus WY]$
		goes into
		$\mc{H}_s(x\, y\, v^2,y\, v)$,
\item[--]  
	from
		$\lambda_{VX} \in 
		\mf{L}[VX,UX \uplus Y]$
		%= \mf{L}[K,L \uplus S]$
		goes into
		$\mc{L}_p^{(\alpha + s)}(x\, u,y\, u)$,
\item[--]  
	from
		$\lambda_{UX} \in 
		\mf{L}[UX,Y]$ 
		goes into the
		term $(1+\alpha+s+p)_r$.
\end{itemize}
This proves 
Eq.~(\ref{eqn:extension2})
and hence 
Eq.~(\ref{eqn:extension1}).
\medskip

Specializing the result 
(\ref{eqn:extension1}) 
by setting $v=1$ (for convenience)
and extracting the coefficient
of $u^k$ (for fixed $k$) 
on both sides, we obtain a whole range
of lacunary Laguerre series:
\[
	\sum_{m \geq 0}
	\frac{\mathcal{L}_{2m+k}^{(\alpha)}(x,y)}{
	2^m\, m! \, (1+\alpha)_{2m+k}}
	=
	\mathcal{M}(x)
	\sum_{s \geq 0}
	\frac{\mathcal{H}_s(x\,y,y)}{s!}
	\frac{\mathcal{L}_k^{(\alpha+s)}(x,y)}
	{(1+\alpha)_{s+k}}.
\]
For the proof, just note that 
for having a term $u^k$ to appear in 
$\mathcal{H}_n(u,1)$
on the left-hand side of the main result 
one must have that $n-k$ is even, so put
$n=2m+k$. 
In this case the coefficient is
\[
	h_{n,m} 
	= \frac{n!}{k! \, m! \, 2^m}.
\]
On the other hand, on the right-hand side
of the main result the variable $u$
appears only in the term
$\mathcal{L}_p^{(\alpha + s)}(xu,yu)$,
which is homogeneous of degree $p$,
so that it can be written as
$\mathcal{L}_p^{(\alpha + s)}(x,y)\, u^p$. 
This shows that the summation over $p$ collapses 
into the single contribution for $p=k$.


\section{An extension featuring
		balls-into-boxes combinatorics}
\label{sec:another}

Recall that in 
Section~\ref{sec:simplest}
we showed combinatorially that
\begin{equation}
\label{eqn:lacunary11}
	\sum_{n \geq 0}
	\frac{t^n}{n!}
	L_{2n}(x) =
	e^t \cdot \sum_{r \geq 0} 
	\frac{(i\, x\, \sqrt{t})^r}{r!^2}
	H_r(i\, \sqrt{t}).
\end{equation}
This is the case $k=0$ of
\begin{equation}
\label{EQ2.8}
	\sum_{n=0}^{\infty} 
	\frac{t^n}{n!} 
	L_{2 n}^{(k)}({x}) 
	= e^{t} \cdot
	\sum_{r=0}^{\infty} 
	\frac{p_{2 k}(r; {1, -x}, t)}
	{r! (r + 3 k)!} 
	({i \,x}\, \sqrt{t})^r 
	H_{r}(i\, \sqrt{t}),
\end{equation}
where 
$p_{2k}(r;x,y;t)$
is a homogeneous polynomial of degree $2k$
in $\{x,y\}$ and also of degree $2k$ in $r$,
with integer coefficients. 
It can be argued algebraically
that such polynomials must exists,
and one can use computer algebra
to determine the first cases.
Indeed, the authors of \cite{BDGP16}
have done this for the cases $k=1$ and $k=2$,
see their identities (3.7), (3.8) and (3.9). 
Here is what their results are:
\begin{align}
\label{15/01/2015-5}
	p_{2}(r; x, y, t) & 
	= (1 + 2 t {x}^2) r^2 
	+ (5  {+}  4 x y t + 10 t {x}^2) r
\\
	\nonumber 
	&\kern1cm + (6 + 12t {x}^2 {+} 12 x y t 
	+ 2 t {y}^2), \label{15/01/2015-4} 
\\
	p_{4}(r; x, y, t) & 
	= (2 + 10 t {x}^{2} 
	+ 4 t^{2} {x}^{4}) r^{4} 
\\
	\nonumber
	&\kern1cm+ [36 + (180 {x}^{2} 
	{+} 20 y x) t 
	+ (72 {x}^{4} 
	{+} 16 {x}^{3} {y})t^{2}] r^{3}  
\\
	\nonumber
	&\kern1cm + [238 + (10 {y}^{2} 
	+ 1190 {x}^{2} {+} 300 y x) t 
\\
	\nonumber 
	&\kern2cm+ (240 {x}^{3} {y} 
	+ 24 {x}^{2} {y}^{2} 
	+ 476 {x}^{4}) t^{2}] r^{2}  
\\
	\nonumber
	&\kern1cm 
	+ [684 + (110 {y}^{2} {+} 1480 y x 
	+ 3420 {x}^{2}) t  
\\
	\nonumber
	&\kern2cm + (1184 {x}^{3} {y} 
	+ 264 y^{2} x^{2} 
	{+} 16 {x y}^{3} 
	+ 1368 {x}^{4}) t^{2}] r 
\\
	\nonumber 
	&\kern1cm + [720 + 
	(2400 y x + 3600 {x}^{2} 
	+ 300 {y}^{2}) t   
\\
	\nonumber
	&\kern2cm + (1920 {x}^{3} {y} 
	{+} 96 {x y}^{3} 
	+ 720 y^{2} x^{2} 
	+ 1440 {x}^{4} 
	+ 4 {y}^{4}) t^{2}].
\end{align} 
Presented as such this does not really 
look inspiring.
I went further and did the computation for $k=3$, 
and again, at first glance the result, presented in
Figure~\ref{fig:thebig} 
does not look inviting:
\begin{figure}[b]
	\begin{align*}
	p_6(r;x,1,t)&=
	\left( 8\,{t}^{3}
	+48\,{t}^{2}
	+54\,t
	+6 \right) {r}^{6}
	\cr
	&\kern17pt+ \left( 48\,x{t}^{3}
	+312\,{t}^{3}
	+192\,x{t}^{2}
	+1872\,{t}^{2}
	+108\,xt+2106\,t
	+234
	 \right) {r}^{5}
	\cr
	&\kern17pt+ \left( 120\,{x}^{2}{t}^{3}
	+1680\,x{t}^{3}
	+288\,{x}^{2}{t}^{2}
	+5000\,{t}^{3}
	+6720\,x{t}^{2}
	+54\,{x}^{2}t \right.
	\cr
	&\kern29pt\left. +30000\,{t}^{2}
	+3780\,xt
	+33750\,t
	+3750\right) 
	{r}^{4}
	\cr
	&\kern17pt+ \left( 160\,{x}^{3}{t}^{3}
	+3600\,{x}^{2}{t}^{3}
	+192\,{x}^{3}{t}^{2}
	+23280\,x{t}^{3}
	+8640\,{x}^{2}
	{t}^{2}
	+42120\,{t}^{3}\right.
	\cr
	&\kern29pt\left.
	+93120\,x{t}^{2}
	+1620\,{x}^{2}t
	+252720\,{t}^{2}
	+52380\,xt
	+284310\,t
	+31590 
	\right) {r}^{3}
	\cr
	&\kern17pt+ \left( 
	120\,{x}^{4}{t}^{3}
	+3840\,{x}^{3}{t}^{3}
	+48\,{x}^{4}{t}^{2}
	+40200\,{x}^{2}{t}^{3}
	+4608\,{x}^{3}{t}^{2}
	+159600\,x{t}^{3}
	\right.
	\cr
	&\kern29pt+96480\,{x}^{2}{t}^{2}
	+196592\,{t}^{3}
	+638400\,x{t}^{2}
	+18090\,{x}^{2}t
	\cr
	&\kern29pt\left.
	+1179552\,{t}^{2}
	+359100\,xt
	+1326996\,t
	+147444 
	\right) {r}^{2}
	\cr
	&\kern20pt+ \left( 
	48\,{x}^{5}{t}^{3}
	+2040\,{x}^{4}{t}^{3}
	+30560\,{x}^{3}{t}^{3}
	+816\,{x}^{4}{t}^{2}
	+198000\,{x}^{2}{t}^{3}
	\right.
	\cr
	&\kern29pt+36672\,{x}^{3}{t}^{2}
	+541152\,x{t}^{3}
	+475200\,{x}^{2}{t}^{2}
	+481728\,{t}^{3}
	+2164608\,x{t}^{2}
	\cr
	&\kern29pt\left.
	+89100\,{x}^{2}t
	+2890368\,{t}^{2}
	+1217592\,xt
	+3251664\,t
	+361296 
	\right) r
	\cr
	&\kern29pt+8\,{x}^{6}{t}^{3}
	+432\,{x}^{5}{t}^{3}
	+8640\,{x}^{4}{t}^{3}
	+80640\,{x}^{3}{t}^{3}
	+3456\,{x}^{4}{t}^{2}
	+362880
	\,{x}^{2}{t}^{3}
	\cr
	&\kern29pt+96768\,{x}^{3}{t}^{2}
	+725760\,x{t}^{3}
	+870912\,{x}^{2}{t}^{2}
	+483840\,{t}^{3}
	+2903040\,x{t}^{2}
	\cr
	&\kern29pt+163296\,{x}^{2}t
	+2903040\,{t}^{2}
	+1632960\,xt
	+3265920\,t
	+362880
\end{align*}
\caption{The polynomial
$p_6(r;x,1,t)$}
\label{fig:thebig}
\end{figure}
Indeed, this expression does
not seem to simplify in any 
reasonable way.
But change of the priority
of the variables leads to
a simplified expression that
definitely looks attractive:
\begin{align*}
	p_6(r;x,1,t)
	&=
	8\,{x}^{6}{t}^{3}
\cr
	&\hskip8mm	+48\,{x}^{5}{t}^{3} 
		\left( 5\,t+2 \right)
		\left( r+9 \right)
\cr 
	&\hskip8mm +24\,{x}^{4}{t}^{2}
	 	\left( r+9 \right)  
		\left( r+8 \right)   
\cr
	&\hskip8mm +32\, {x}^{3}{t}^{2}
		\left( 5\,t+6 \right) 
		\left( r+9 \right)  
		\left( r+8 \right)  
		\left( r+7 \right)  
\cr
	&\hskip8mm +6\,{x}^{2}t 
		\left( 20\,{t}^{2}+48\,t+
	9 \right)  
		\left( r+9 \right)  
		\left( r+8 \right)  
		\left( r+7 \right) 
	    \left( r+6 \right) 
\cr
	&\hskip8mm +12\,x\,t 
		\left( 4\,{t}^{2}+16\,t+9 \right) 
	 	\left( r+5 \right)  
		\left( r+9 \right)  
		\left( r+8 \right)  
		\left( r+7 \right)  
		\left( r+6 \right)
\cr
	&\hskip8mm +(8\, {t}^{3}+
		48\,{t}^{2}+
		54\,t+
		6)
		\left( r+9 \right)  
		\left( r+8 \right)  
		\left( r+7 \right)  
		\left( r+6 \right)  
		\left( r+5 \right) 
	    \left( r+4 \right) .
\end{align*}
This encourages one to look back
to the expressions given
in the cases $k=1$,
\begin{align*}
	p_2(r;x,1,t)
	&=
		2\,{x}^{2}t+4\,xt 
		\left( r+3 \right) 
		+(2\,t+1) 
		\left( r+3 \right)  
		\left( r+2 \right) 
\cr
	&=
	\sum_{i=0}^2
		\sum_{j=0}^1
		x^i \,  t^j 
		\binom{2j}{i} 
		\frac{(r+3)!}{(r+1+i)!} a_{1,j},
\hskip5mm 
		\text{with}~~(a_{1,0}, a_{1,1})=(1,2),
\end{align*}
and $k=2$,
\begin{align*}
		p_4(r;x,1;t)
		&= 4\,{x}^{4}{t}^{2}
\cr 
		&\kern1cm +16\,{x}^{3}{t}^{2} 
		\left( r+6 \right)
\cr 		
		&\kern1cm +2\,{x}^{2}\,t
		\left( 12\,t+5 \right) 
		\left( r+6 \right)  
		\left( r+5 \right)  
\cr
		&\kern1cm +4\,x\,t\,(4t+5)
		\left( r+6 \right)
	 	\left( r+5 \right)  
	 	\left( r+4 \right)  
\cr
		&\kern1cm+(4\,{t}^{2}+10\,t+2)
		\left( r+6 \right)
		\left( r+5 \right)  
		\left( r+4 \right)  
		\left( r+3 \right)  
\cr		
		&= \sum_{i=0}^4
		\sum_{j=0}^2
		x^i \,  t^j 
		\binom{2j}{i} 
		\frac{(r+6)!}{(r+2+i)!} a_{2,j},
 \hskip5mm
		\hskip5mm\text{with}~~
		(a_{2,0},a_{2,1},a_{2,2})
		=(2,10,4).
\end{align*}
This suggests that in general one 
should have
\begin{equation}
\label{eqn:ballsboxes-main}
	\sum_{n \geq 0}
	L_{2n}^{(k)}(x)
	\frac{t^n}{n!}
	=
	e^t \,
	\sum_{r \geq 0}
	\frac{\tilde{p}_{2k}(r;-x,t)}{r!}
	\,
	(i\,x\,\sqrt{t})^r \, 
	H_r(i \,\sqrt{t}),
\end{equation}
	where
\[
	\tilde{p}_{2k}(r;x,t)
	=
	\sum_{0 \leq i \leq 2k}
	\sum_{0\leq j \leq k}
	x^i \,  t^j \binom{2j}{i} 
	\frac{1}{(r+k+i)!} \, a_{k,j},
\]
with (positive integer) coefficients 
$(a_{k,j})_{0 \leq j \leq k}$.
Note that in this notation
the term $(r+3)!$ (for $k=1$)
and $(r+6)!$ (for $k=2$) 
disappears from the identity. 
This change is indicated by writing 
$\tilde{p}_{2k}(r;x,t)$
instead of $p_{2k}(r;x,t)$.
Now $\tilde{p}_{2k}(r;x,t)$
is no longer a polynomial in $r$,
but the advantage is that the
term $(r+\text{something})!$
cancels and we do not need
to know what ``something'' is.

\bigskip

Computing the first values of the
$a_{k,\ell}$, we get
\[
	\begin{array}{r|rrrrrrr}
	k \backslash j & 0 & 1 & 2 & 3 & 4 & 5 & 6 
	\\ \hline
	0 & 1 &&&&&&\cr
	1 & 1 &2 &&&&& \cr
	2 & 2  & 10 & 4 &&&& \cr
	3 & 6  & 54 & 48 & 8 &&& \cr
	4 & 24 & 336 & 492 & 176 & 16 && \cr
	5 & 120 & 2400 & 5100 & 2920 & 560 & 32 & \cr
	6 & 720 & 19440 & 55800 & 45240 & 13680 & 1632 & 64
	\end{array}
\]
This clearly suggests a linear recurrence
\[
	a_{k,\ell} = 2 a_{k-1,\ell-1}+(k+2\ell)\,a_{k-1,\ell},
\]
which would show that the 
numbers $a_{k,\ell}/2^\ell$
are integers.
Based on this conjectured recurrence
one could derive various generating 
functions, but it seems more interesting
to look at the numbers and 
generating polynomials
\[
	\overline{a}_{k,\ell}
	= a_{k,\ell}\,
	\genfrac{}{}{}{0}{\ell!}{k!}
	\hskip5mm
	\text{and}
	\hskip5mm
	\overline{a}_k(t) = 
	\sum_{0\leq \ell \leq k} 
	\overline{a}_{k,\ell}  
	t^\ell.
\]
Then the recurrence reads
\[
	k \,\overline{a}_{k,\ell}
	=
	2 \,\ell\, 
	\overline{a}_{k-1,\ell-1}
	+
	(k+2 \ell)\, 
	\overline{a}_{k-1,\ell},
\]
and the 
$\overline{a}_k(t)~(k \geq 0)$
have a very simple rational
generating function:
\[
	\sum_{k \geq 0} 
	\overline{a}_k(t) \,z^k
	= 
	\frac{1-z}{1-2(1+t)z
	+(1+t)z^2 }.
\]
The vertical generating functions of the 
$\overline{a}_{k,\ell}$
are given by
\begin{align*}
	\sum_{k \geq \ell} 
	\overline{a}_{k,\ell} \,z^k &=
	\frac{1}{1-z}
	\left(
	\frac{z(2-z)}{(1-z)^2}\right)^\ell
	\cr
	&=
	\frac{1}{1-z}
	\left( \frac{1-(1-z)^2}{(1-z)^2}
	\right)^\ell
	\cr
	&=
	\frac{(-1)^\ell}{1-z}
	\cdot
	\left(
	1- \frac{1}{(1-z)^2}
	\right)^\ell.
\end{align*}
An exponential generating function for the 
$\overline{a}_k(t)~(k \geq 0)$
can be obtained, but it does not
have a particularly nice form.

Here is a table of first values of the 
$\overline{a}_{k,\ell}$:
	\[
	\begin{array}{r|rrrrrrr}
	k \backslash \ell & 0 & 1 & 2 & 3 & 4 & 5 & 6 
	\\ \hline
	0 & 1 &&&&&&\cr
	1 & 1 &2 &&&&& \cr
	2 & 1  & 5 & 4 &&&& \cr
	3 & 1  & 9 & 16 & 8 &&& \cr
	4 & 1 & 14 & 41 & 44 & 16 && \cr
	5 & 1 & 20 & 85 & 146 & 112 & 32 & \cr
	6 & 1 & 27 & 155 & 377 & 456 & 272 & 64
	\end{array}
	\]
These numbers are known to the 
\emph{Online Encyclopedia of Integer Sequences} 
\cite{OEIS}
as entry A056242. 
They were apparently first considered by
Hwang and Mallows \cite{HM95}
in counting 
\emph{order-consecutive partitions}, 
but in the present context another
combinatorial interpretation
of the balls-into-boxes type
is better suited.

\begin{itemize}
\item[--]
	For integers $k,\ell$ with
	$0 \leq \ell \leq k$ consider 
	\begin{itemize}
	\item
		$k$ (ordered) singleton
		boxes, each of which 
		can contain at most one ball,
	\item 
		$\ell$ (ordered)
		twin boxes, each of which
		can contain at most
		one ball in each of 
		the two twin compartments.
	\end{itemize} 
\item[--] 
	Then
	$\overline{a}_{k,\ell}$
	is the number of distributions
	of balls into the boxes
	s.th.
	\begin{itemize}
	\item 
	each twin box contains 
	at least one ball,
	\item 
	the total number of balls
	in singleton boxes equals the total
	number of balls in twin boxes.
	\end{itemize}
\end{itemize}
In Figure~\ref{fig:lag-balls}	this
model is illustrated for
$k=3$:
\begin{itemize}
\item[--] 
	The first row shows 
	that without any twin
	box ($\ell=0$) 
	there is just 
	one possible configuration,
	so $\ol{a}_{3,0}=1$;
\item[--] 
	The second and the third
	row show representatives 
	for the	case $\ell=1$, 
	the second row (one ball)
	giving 6~possibilities,
	the third row (two balls)
	giving 3~possibilities,
	so $\ol{a}_{3,1}=9$,
\item[--] 
	The fourth and the fifth
	row show representatives 
	for the	case $\ell=2$, 
	the fourth row (two balls)
	giving 12~possibilities,
	the third row (three balls)
	giving 4~possibilities,
	so $\ol{a}_{3,2}=16$,
\item[--] 
	The sixth
	row shows a representative 
	for the	case $\ell=3$, 
	where only three balls
	are necessary.
	This gives 8 possibilities,
	so $\ol{a}_{3,3}=8$.
\end{itemize}
\begin{figure}[htbp]
	\centering
	\includegraphics[width=2.5in]
	{balls.pdf} 
	\caption{Balls-into-boxes 
	for $k=3$ and $0 \leq \ell \leq 3$}
\label{fig:lag-balls}
\end{figure}	

Expansion of the main identity
(\ref{eqn:ballsboxes-main})
gives 
\[
	m_{2n} \binom{2n}{s} \binom{2n+k}{k}
	=
	\sum_{2a+2b+i+j=2n}
	\binom{2n}{2a,2b,i,j}\,
	m_{2a}\,
	\beta_{s-i,b}\,
	m_{i+j}\,
	\overline{a}_{k,(i+j)/2},
\]
where
\[
	\beta_{r,b} = 
	\binom{2b}{r} 
	\binom{r}{b} \,
	b! \, 
	2^{b-r}
	=
	m_{2b} \,
	\binom{b}{r-b} \,
	2^{2b-r},
\]
so that
\begin{multline}
\label{eqn:balls-general}
	m_{2n} \binom{2n}{s} \binom{2n+k}{k}
	\cr
	=
	\sum_{2a+2b+i+j=2n}
	\binom{2n}{2a,2b,i,j}
	m_{2a}\,
	m_{2b}\,
	m_{2c}\,
	2^{2b-s+i}
	\binom{b}{s-i-b}
	\overline{a}_{k,(i+j)/2}
	\cr
	=
	\sum_{a+b+c=n}
	\binom{2n}{2a,2b,2c}
	m_{2a}\,
	m_{2b}\,
	m_{2c}\,
	\overline{a}_{k,c}
	\sum_{i+j=2c}
	\binom{2c}{i,j}
	\binom{b}{2b-s+i} 2^{2b-s+i}.
\end{multline}
	

There are two interesting 
special cases:
\begin{itemize}
\item[--] Case $k=0$:
\[
	m_{2n} \binom{2n}{s}
	=
	\sum_{a+b=n}
	\binom{2n}{2a,2b}
	m_{2a}\,
	m_{2b}\,
	2^{2b-s}
	\binom{b}{s-b}
\]
We know this already!
This is the numerical consequence
from the combinatorial
proof given in Section~\ref{sec:simplest}.
\medskip
	
\item[--] Case $s=0$:
\begin{equation}
\label{eqn:balls-special}
	m_{2n} \binom{2n+k}{k}
	=
	\sum_{a+c=n}
	\binom{2n}{2a,2c}
	m_{2a}\,
	m_{2c}\,
	\overline{a}_{k,c}
\end{equation}
In this case the relevance of the
balls-into-boxes argument becomes obvious:
\begin{itemize}
\item[--]
	Consider a set $N$ of
	cardinality $2n$
	and a set $K$ of cardinality
	$k$, disjoint from $N$.
\item[--]
	The left-hand side of
	(\ref{eqn:balls-special})
	counts the pairs $(\mu,S)$,
	where $\mu \in \mf{M}[N]$
	and $S \subset N \uplus K$,
	with $\sharp S = k$.
\item[--]
	The right-hand side of
	(\ref{eqn:balls-special})
	counts pairs 
	$(\mu_A,\mu_C) \in 
	\mf{M}[A] \times \mf{M}[C]$
	for bipartitions
	$N = A \uplus C$, 
	together with a balls-into-boxes 
	configuration on 
	$K \times \mi{trans}(\mu_C)$,
	the elements of $K$ being the
	singleton boxes and the transpositions 
	of $\mu_C$
	being the ``twin boxes''.\newline
	For
	$\mf{M}[A] \times \mf{M}[C]$
	to be nonempty, the cardinalities 
	of $A$ and $C$ must be even, so 
	$\sharp A = 2a$ and
	$\sharp C = 2c$ with $a+c=n$.
	\item[--] 
	The balls-into-boxes 
	configuration configuration
	just mentioned
	contains $\ell$ balls, say, where 
	$c \leq \ell \leq 2c$.
	The $\ell$ balls placed on
	$\mi{trans}(\mu_B)$ together
	with the $k-\ell$ empty
	singleton boxes in $K$
	make a $k$-subset $S$ of
	$N \uplus K$, $\mu_A$ and 
	$\mu_B$ together give an
	element $\mu \in \mf{M}[N]$.
\item[--] 
	The argument just outlined is
	perfectly reversible.
	\end{itemize}
	This situation is illustrated
	in Figure~\ref{fig:balls-example} 
	in a situation where 
	$n=8$, $k=10$, $a=c=4$, $\ell=6$.
\end{itemize}

\begin{figure}[htbp]
	\centering
	\includegraphics[width=10cm]
	{specialcase.pdf}
	\caption{Illustration of
	the second special case, where
	balls-into-boxes appear 
	(the balls are the red and
	blue vertices).}
\label{fig:balls-example}
\end{figure}

The general case of 
Eq.~(\ref{eqn:balls-general})
can be illustrated
by amalgamating
these combinatorial views
for the special cases.

\bigskip

\section{More extensions: 
balls-into-boxes with parameter 
$\alpha$, and a triple lacunary
Laguerre series}
\label{sec:moreext}

In this section two extension of 
the results given in 
Section~\ref{sec:another}
will be presented, but 
the details will only be sketched.


\subsection{The $\alpha$-extension}
\label{ssec:alphaext}

Identity 
(\ref{eqn:balls-special}) 
can be generalized into
\[
	m_{2n} \cdot (1+\alpha+2n)_k
	=
	\sum_{2a+2c=2n}
	\binom{2n}{2a,2c}\,
	m_{2a}\,
	m_{2c}\,
	\overline{aa}_{k,c}^{(\alpha)},
\]
where now the coefficients
$\overline{aa}_{k,c}^{(\alpha)}$
are defined by
\[
	\overline{aa}_{k,\ell}
	^{(\alpha)}
	=
	2 \ell \cdot
	\overline{aa}_{k-1,\ell-1}
	^{(\alpha)}
	+
	(\alpha+k+2\ell) \cdot
	\overline{aa}_{k-1,\ell}
	^{(\alpha)},
	~~~~\overline{aa}_{0,0}
	^{(\alpha)}=1.
\]
This leads to
\begin{multline*}
	m_{2n} \binom{2n}{s} 
	(1+\alpha+2n)_k
	\cr
	=
	\sum_{a+b+c=n}\hskip-1mm
	\binom{2n}{2a,2b,2c}
	m_{2a}\,
	m_{2b}\,
	m_{2c}\,
	\overline{aa}_{k,c}^{(\alpha)}
	\sum_{i+j=2c}\hskip-1mm
	\binom{2c}{i,j}
	\binom{b}{2b-s+i} 2^{2b-s+i},
\end{multline*}
which is the same as
\begin{align*}
	m_{2n}\,
	\mathcal{L}_{2n}
	^{(\alpha+k)}(1,x)
	&=
	(1+\alpha)_{2n}
	\sum_{0 \leq s \leq 2n}
	\frac{x^s}{(1+\alpha)_{k+s}}
	\sum_{a+b+c=n}
	\binom{2n}{2a,2b,2c}
	m_{2a}\,
	m_{2b}\,
	m_{2c}\,
	\overline{aa}_{k,c}^{(\alpha)}
\cr	&\kern3cm
	\times
	\sum_{i+j=2c}
	\binom{2c}{i,j}
	\binom{b}{2b-s+i} 2^{2b-s+i}
\cr
	&=
	(1+\alpha)_{2n}
	\sum_{a+b+c=n}
	\binom{2n}{2a,2b,2c}
	m_{2a}\,
	m_{2c}\,
	\overline{aa}_{k,c}^{(\alpha)}
\cr &\kern3cm
	\times \sum_{0 \leq s \leq 2n}
	\frac{x^{s}}{(1+\alpha)_{k+s}}
	\sum_{i+j=2c}
	\binom{2c}{i}
	\frac{(2b)!}{(s-i)!}\,
	[t^{2b}]\,
	\mathcal{H}_{s-i}(t^2,t).
\end{align*}	
With
\[
	p_k^{(\alpha)}(r,x,t)=
	\sum_{0 \leq i \leq 2k}
	\sum_{0 \leq j \leq k}
	x^i t^j \binom{2j}{i} 
	\frac{1}{(\alpha)_{r+k+i}}\, 
	a_{k,j}^{(\alpha)},
\]
where 
$a_{k,j}^{(\alpha)}
=\overline{aa}_{k,j}^{(\alpha)}/j!$,
one gets	
\[
	m_{2n}\,
	\mathcal{L}_{2n}
	^{(\alpha+k)}(1,x)
	= (2n)! \, (\alpha)_{2n}\,
	[t^{2n}]\,
	e^{t^2/2}
	\sum_{r \geq 0}
	\frac{x^r}{r!}
	\, p_k^{(\alpha)}(r,x,t^2/2)
	\, \mathcal{H}_r(t^2,t),
\]
and hence
\[
	\sum_{n \geq 0}
	\frac{t^{2n}}{2^n \, n!\, (\alpha)_{2n}}
	\mathcal{L}_{2n}^{(\alpha+k)}(1,x)
	=
	e^{t^2/2}
	\sum_{r \geq 0}
	\frac{x^r}{r!}
	\, p_k^{(\alpha)}(r,x,t^2/2)
	\, \mathcal{H}_r(t^2,t),
\]
which in conventional notation reads
\begin{equation*}
	\sum_{n \geq 0}
	\frac{t^{2n}}{n!}\, 
	\frac{(2n)!}{(1+\alpha)_{2n}}
	L_{2n}^{(\alpha+k)}(x)
	=
	e^{t}
	\sum_{r \geq 0}
	\frac{1}{r!}
	\, p_k^{(\alpha)}(r,-x,t)\,
	(i\,x\, \sqrt{t})^r
	\, H_r(i \,\sqrt{t}),
\end{equation*} 
where the polynomials 
$p_k^{(\alpha)}(r,x,t)$
have a nice combinatorial meaning.

\subsection{A triple lacunary 
	Laguerre series}
\label{ssec:tripleext}

In analogy to 
Eq.~(\ref{EQ2.8})
one may consider the case of triple 
lacunary Laguerre series of the form
\begin{equation}
\label{eqn:triple}
	\sum_{n\geq 0}
	\frac{t^n}{n!} 
	L_{3n}^{(k)}(x) 
	=
	e^t \cdot
	\sum_{r \geq 0}
	\frac{x^r\,q_{3k}(r;x,t)}{(r+4k!)}
	\sum_{0 \leq s \leq \lfloor r/3 \rfloor}
	\frac{(-t)^s\,
	(i\, \sqrt{3t})^{r-3s}}
	{(r-3s)!\,s!}
	H_{r-3s}(i\, \sqrt{3t}/2),
\end{equation}
	with polynomial factors
	$q_{3k}(r;-x,t)$. The case
	$k=1$ has been worked out
	in \cite{BDGP16}, see
	identity (4.4) and the following line, 
	which reads
\begin{multline*}
	q_{3}(r; x, t) 
	= (1 + 3\, t)\, r^{3} 
	+ (9 + 27 \,t - 9 t \,x) \,r^{2} 
	+ (26 + 78 \,t - 63 \,t \,x + 9\, t\, x^{2})\, r \\
	+ (24 + 72\, t - 108 t\, x 
	+ 36\, t \,x^{2} - 3 \,t \,x^{3}),
\end{multline*}
but without any hint what these
integer coefficients might count.
Indeed, we have the general
form
\[
	q_{3k}(r;x,t)=
	\sum_{0 \leq i \leq 3k} 
	\sum_{0 \leq j \leq k}
	(-x)^i\, t^j \binom{3j}{i}
	\frac{(r+4k)!}{(r+k+i)!}\, b_{k,j},
\]
where the generating polynomials
\[
	b_k(t) = \sum_{0 \leq \ell \leq k}
	b_{k,\ell}\, t^\ell
\]
are defined via the linear recurrence
\[
	b_{k,\ell} = 3\, b_{k-1,\ell-1}+
	(k+3\ell) \,b_{k-1,\ell},
\]
with exponential generating function
\[
	\sum_{k \geq 0}
	\sum_{0 \leq \ell \leq k}
	b_{k,\ell}\, t^\ell\,
	\frac{z^k}{k!}
	=
	\frac{e^{t/(1-z)^2}}{(1-z)\,e^t}.
\]
The first values for the $b_{k,\ell}$ are
\[
	\begin{array}{r|rrrrrr}
	k\backslash \ell & 0 &1 & 2 & 3 & 4 & 5\\\hline
	0 & 1 &  &  &  &  &  \\
 	1 &1 & 3 &  &  &  &  \\
	2 & 2 & 18 & 9 &  &  &  \\
	3 & 6 & 114 & 135 & 27 &  &  \\
	4 & 24 & 816 & 1692 & 756 & 81 & \\
	5 & 120 & 6600 & 21060 & 15660 &
   3645 & 243 \\
\end{array}
\]
Again, the numbers 
$\ol{b}_{k,\ell}= b_{k,\ell}\cdot\ell!/k!$ 
are integers, which satisfy the recurrence
\[
	k\,\ol{b}_{k,\ell} = 
	3\,\ell\, \ol{b}_{k-1,\ell-1}+
	(k+3\ell) \,\ol{b}_{k-1,\ell}.
\]
The first values (not yet in the OEIS) are
\[
\begin{array}{r|rrrrrr}
	k \backslash\ell&0&1&2&3&4&4\\\hline
	0& 1 & 0 & 0 & 0 & 0 & 0 \\
	1& 1 & 3 & 0 & 0 & 0 & 0 \\
	2&1 & 9 & 9 & 0 & 0 & 0 \\
	3& 1 & 19 & 45 & 27 & 0 & 0 \\
	4& 1 & 34 & 141 & 189 & 81 & 0\\
	5& 1 & 55 & 351 & 783 & 729 &
   243 \\
\end{array}
\]
The straightforward
combinatorial interpretation
for $\ol{b}_{k,\ell}$
is a balls-into-boxes
situation as before, but
now with $k$ singleton boxes
and $\ell$ triple boxes and a
corresponding occupancy rule.

With this information at hand
it is not difficult to
obtain a combinatorial proof
of Eq.~(\ref{eqn:triple}) along
the lines presented
in Section~\ref{sec:another}.


 
\section{A lacunary Charlier series}
\label{sec:charlier}

In this section we consider 
the lacunary Laguerre series identity
\begin{equation}
\label{eqn:cha1}
	\sum_{n \geq 0}
	t^n L_{2n}^{(\alpha-2n)}(x,y) =
	(1-t\, x^2)^{\alpha/2}
	\cosh \left(
	\sqrt{t}\, y + i \,
	\alpha \arcsin
	\left(\frac{\sqrt{t}\,x}{\sqrt{t\,x^2-1}}
	\right)\right),
\end{equation}
which is Eq.~(3.16) in
\cite{BDGP16}.
It is convenient to replace $t$ by $t^2$
and  $\alpha$ by $-\alpha$, 
so that in terms of the combinatorial 
version of the Laguerre polynomials
with variables $x,y$ the identity reads
\begin{equation}
\label{eqn:cha2}
	\sum_{n \geq 0}
	\frac{t^{2n}}{(2n)!} 
	\mathcal{L}_{2n}^{
	(-\alpha-2n)}(x,y)
	=
	(1-(t\,x)^2)^{-\alpha/2}
	\cosh
	\left(\!
	t\,y-i\, \alpha \arcsin
	\left(\frac{t\,x}{
	\sqrt{(t\,x)^2-1}}\right)\right).
\end{equation}
As usual, the variable $t$ can be dropped, 
so that after setting $t=-1$ we get
\begin{equation}
\label{eqn:cha3a}
	\sum_{n \geq 0}
	\frac{1}{(2n)!} 
	\mathcal{L}_{2n}^{
	(-\alpha-2n)}(-x,y)
	=
	(1-x^2)^{-\alpha/2}
	\cosh
	\left(
	y+i\, \alpha \arcsin
	\left(\frac{x}{\sqrt{x^2-1}}
	\right)\right).
\end{equation}

It should be stressed that the polynomials 
\[
	\mathcal{L}_{2n}^{
	(-\alpha-2n)}(x,y)
\]
are not really Laguerre polynomials 
(because their cycle-counting
parameter $-\alpha-2n$ depends on $n$).
Instead, they are essentially homogeneous
versions of the Charlier polynomials,
which can be seen from
\begin{align*}
	\mathcal{L}_{n}^{(-\alpha-n)}
	(-x,y)
	&= 
	\sum_{0 \leq k \leq n}
	\binom{n}{k}
	(1-\alpha-n+n-k)_k \, 
	(-x)^k \, y^{n-k}
	\cr
	&= 
	\sum_{0 \leq k \leq n}
	\binom{n}{k}
	(\alpha)_k \, 
	x^k \,y^{n-k}
	\cr
	&=
	y^n \cdot 
	\hg{1}{0}{-n,\alpha}{-}
	{\frac{x}{y}},
\end{align*}
so that
\[
	\mathcal{L}_{2n}^{
	(-\alpha-2n)}(-x,y)
	=
	\sum_{0 \leq k \leq 2n}
	\binom{2n}{k}
	(\alpha)_k \, x^k \,y^{2n-k}.
\]
Obviously, these polynomials are 
the enumerating polynomials
for those Laguerre configurations on 
$X \uplus Y = \{1,2,\ldots,2n\}$
which consist, apart from the singletons 
in $Y$, of permutations of $X$ only, 
and with a weight $\alpha$ 
put on each cycle.
Those structures will be called 
\emph{Charlier configurations}
for short. 
	
As for the factor
$(1-x^2)^{-\alpha/2}$ 
in Eq.~(\ref{eqn:cha3a}), 
this is nothing but the exponential 
generating functions for permutations
consisting of cycles of {\it even} 
length only, with weight $\alpha$
put on each cycle. 
Therefore it suffices to show that 
\begin{equation}
\label{eqn:cha4}
	\cosh
	\left(
	y+i\, \alpha \arcsin
	(\frac{x}{\sqrt{x^2-1}}\right)
\end{equation}
is the exponential generating
function for Charlier configurations 
of {\it even} order, 
where all cycles are of
{\it odd\/} length.
	
For this purpose, consider the familiar series
\[
	\arcsin ( \frac{x}{\sqrt{x^2-1}})
	= - i 
	\left( x + \frac{x^3}{3} 
	+ \frac{x^5}{5} 
	+ \cdots \right).
\]
This shows that 
\[
	i\,\alpha 
	\arcsin(
	\frac{x}{\sqrt{x^2-1}})
	=
	\alpha \left(
	x + 2! \frac{x^3}{3!}
	+ 4! \frac{x^5}{5!} 
	+ \ldots
	\right)
\]
is the exponential generating function
for cyclic permutations of 
{\it odd\/} length only.
By general principles,
\[
	\exp\left(y+i\,\alpha 
	\arcsin(x/\sqrt{x^2-1})\right)
\]
is the exponential generating
function for structures 
which are composed of an
arbitrary number of
\begin{itemize}
\item[--] 
	singletons with weight $y$,
\item[--] 
	cycles of odd length 
	$2 \ell +1$
	($\ell \geq 1$) with weight 
	$\alpha\,x^{2 \ell +1}$
	for each cycle.
\end{itemize}

Now we restrict attention to only 
those compound structures of 
{\it even}  order, 
i.e., for which the total weight
(product over all component weights) 
is even as a monomial in $x$ and $y$,
which is achieved if and only
if the number of components is even.
But this means that instead of
substituting into the exponential series
\[
	e^z = \sum_{n\geq 0} 
	\frac{z^n}{n!},
\] 
we have to substitute into
the $\cosh$-series
\[
	\cosh(z) =\sum_{n\geq 0} 
	\frac{z^{2n}}{(2n)!}.
\]
Thus Eq.~(\ref{eqn:cha4})
is indeed the exponential generating 
function of Charlier configurations of 
{\it even} order composed of 
cycles of {\it odd\/} length 
(variable $x$) and singletons 
(variable $y$, cycle count $\alpha$), 
as required.
	
\bigskip

\section{Binomial identities,
	umbral substitution, 
	and a combinatorial puzzle}

\label{sec:binomial}

In Section~4 of 
\cite{BDGP16}, Eqs.~(4.6)~ff.,
the authors derive an interesting
lacunary Laguerre series in terms of 
Bessel functions by using their proper 
methods.
We have already met this generating 
function here as 
Eq.~(\ref{eqn:natural4}).
I have pointed out to the authors of 
\cite{BDGP16}
that this result can be deduced
from a mixed bilateral generating function
for products of Laguerre and Gegenbauer 
polynomials. 
My hint is reproduced
in Appendix A of \cite{BDGP16}.
In this last section, I want to take a 
closer look on this result, 
with combinatorics in mind.

For convenience, I write 
Eq.~(\ref{eqn:natural4})
in the following form:
\begin{equation}
\label{eqn:final1}
	\sum_{n \geq 0}
	\frac{(1/2)_n}{(1+\alpha)_n} 
	L_{2n}^{(2\alpha)}(2y)
	\,
	t^n
	=
	\frac{1}{(1-t)^{\alpha+1/2}}
	e^{-2y\,t/(1-t)}
	{}_0F_1
	\left[
	\genfrac{}{}{0pt}{0}{ -}{ 1+\alpha };
	\frac{y^2\,t}{(1-t)^2}
	\right].
\end{equation}
The right-hand side
is reminiscent of the
well-known Hille--Hardy identity,
see \cite[Theorem~69, p.~212]{Ra66},
which has received a combinatorial proof,
including a combinatorially motivated 
multivariate extension in 
\cite{FS83},
see also \cite{FS81} for an analytic proof:	
\begin{equation}
\label{eqn:hillehardy}
	\sum_{n \geq 0}
	\frac{n!}{(1+\alpha)_n}
	L_n^{(\alpha)}(x)
	L_n^{(\alpha)}(y)\,t^n
	=
	\frac{1}{(1-t)^{\alpha+1}}
	e^{-(x+y)t/(1-t)}
	{}_0F_1 \left[ 
	\genfrac{}{}{0pt}{0}{-}{ 1+\alpha};
	\frac{x\,y\,t}{(1-t)^2}
	\right].
\end{equation}
By setting $x=y$, one gets	 
\begin{equation}
\label{eqn:final2}
	\sum_{n \geq 0}
	\frac{n!}{(1+\alpha)_n}
	L_n^{(\alpha)}(y)
	L_n^{(\alpha)}(y)\,t^n
	=
	\frac{1}{(1-t)^{\alpha+1}}
	e^{-2y\,t/(1-t)}
	{}_0F_1 \left[ 
	\genfrac{}{}{0pt}{0}{-}{1+\alpha};
	\frac{y^2\,t}{(1-t)^2}
	\right]
\end{equation}
and hence, by comparison of
(\ref{eqn:final1}) and 
(\ref{eqn:final2}), one has
\[
	\sum_{n \geq 0}
	\frac{n!}{(1+\alpha)_n}
	L_n^{(\alpha)}(y)^2\,t^n
	=
	\frac{1}{(1-t)^{1/2}}
	\sum_{n \geq 0}
	\frac{(1/2)_n}{(1+\alpha)_n} 
	L_{2n}^{(2\alpha)}(2y)
	\,
	t^n,
\]
or, equivalently,
\[
	\frac{n!}{(1+\alpha)_n}
	L_n^{(\alpha)}(y)^2
	=
	\sum_{0\leq k \leq n}
	\frac{(1/2)_k}{k!}
	\frac{(1/2)_{n-k}}{(1+\alpha)_{n-k}}\,
	L_{2n-2k}^{(2\alpha)}(2y).
\]
Written in terms of the combinatorial 
Laguerre polynomials, this reads
\begin{align}
\label{eqn:main1}
	\mc{L}_n^{(\alpha)}(2x,y)^2
	&=
	\sum_{0 \leq k \leq n}
	\binom{n}{k}
	\frac{(2k)!}{k!}
	\frac{(1+\alpha)_{n}}
	{(1+\alpha)_{n-k}}\,
	x^{2k}
	\mc{L}_{2n-2k}^{(2\alpha)}(x,y)
	\cr
	&=
	\sum_{0 \leq k \leq n}
	\binom{n}{k}
	\binom{\alpha+n}{k} 
	(2k)! \, x^{2k} \,
	\mathcal{L}_{2n-2k}^{(2\alpha)} (x,y).
\end{align}

As a side remark: 
the Hille--Hardy identity itself
can be written as
\[
	\mc{L}_n^{(\alpha)}(x,y)\,
	\mc{L}_n^{(\alpha)}(x,z)
	=
	\sum_{0 \leq k \leq n}
	\binom{n}{k}
	(1+\alpha+k)_{n-k}
	(y\,z)^k
	\mc{L}_{n-k}^{(\alpha+2k)}
	(x^2,x\,y+x\,z),
\]
(Bateman project 
\cite[Sec.~10.12, Eq.~(42)]{Er81}).
So we have both
\begin{align*}
	\mc{L}_n^{(\alpha)}(x,y)^2 &=
	\sum_{0 \leq k \leq n}
	\binom{n}{k}
	\binom{\alpha+n}{n-k} (n-k)!\,
	x^{n-k}\,
	y^{2k}\,
	\mc{L}_{n-k}^{(\alpha+2k)}(x,2y),
	\cr
	\mc{L}_n^{(\alpha)}(x,y)^2 &=
	\frac{1}{4^n}
	\sum_{0 \leq k \leq n}
	\binom{n}{k}
	\binom{\alpha+n}{k}
	(2k)!\,
	x^{2k}\,
	\mc{L}_{2n-2k}^{(2\alpha)}(x,2y).
\end{align*}
 
Back to the main identity 
Eq.~(\ref{eqn:main1}).
Written as a family of binomial
identities, it can be stated 
for $0 \leq m \leq 2n$ as
\begin{equation}
\label{eqn:main2}
	2^m \sum_k 
	\frac{\binom{n}{k}
	\binom{n+\alpha}{k}
	\binom{n}{m-k}
	\binom{n+\alpha}{m-k}}{\binom{m}{k}}
	=
	\sum_k
	\frac{\binom{n}{k}
	\binom{n+\alpha}{k}
	\binom{2n-2k}{m-2k}
	\binom{2n-2k+2\alpha}{m-2k}}{\binom{m}{2k}}.
\end{equation}


One has to be careful with the range 
of summation! The cases 
$0 \leq m\leq n$ and 
$n \leq m \leq 2n$
should be considered separately!
For $0 \leq m \leq n$
the summation $\sum_k$ runs on the 
left-hand side effectively from
$k=0$ to $k=m$; 
for $n\leq m \leq 2n$ 
the summation $\sum_k$ runs effectively
from $k=m-n$ to $k=n$.

In the case $\alpha=0$,
Eqs.~(\ref{eqn:main1})
respectively (\ref{eqn:main2}) 
simplify to 
\begin{equation}
\label{eqn:main3}
	\mathcal{L}_n (2x,y)^2
	=
	\sum_{0 \leq k \leq n}
	\binom{n}{k}^2
	(2k)! \, x^{2k} \,
	\mathcal{L}_{2n-2k} (x,y),
	\end{equation}
	respectively
	\begin{equation}
	\label{eqn:main4}
	2^m 
	\sum_{0 \leq k \leq n} 
	\frac{\binom{n}{k}^2
	\binom{n}{m-k}^2}{\binom{m}{k}}
	=
	\sum_{0 \leq k \leq n}
	\frac{\binom{n}{k}^2
	\binom{2n-2k}{m-2k}^2}{\binom{m}{2k}}
	~~~~~(0 \leq m \leq 2n).
\end{equation}

\medskip

Two particular cases are
worth mentioning:
\begin{itemize}
\item[--] 
	For $m=2n$, 
	Eq.~(\ref{eqn:main4})
	reduces to the well-known
	\[
	4^n =
	\sum_{0 \leq k \leq n}
	\binom{2k}{k}
	\binom{2n-2k}{n-k},
	\] 
	for which several combinatorial 
	proofs (e.g., counting
	lattice paths) are known.
\item[--] 
	For $m=n$ one gets from
	(\ref{eqn:main4}):
\begin{align}
	\label{eqn:franel-1}
	2^n 
	\sum_{0 \leq k \leq n}  
	\binom{n}{k}^3
	&=
	\sum_{0 \leq k \leq n}
	\binom{n}{k}^2
	\binom{2n-2k}{n-2k}^2
	(2k)!(n-2k)!
	\cr
	&=
	\sum_{0 \leq k \leq n}
	\binom{2k}{k}
	\binom{2n-2k}{n-k}
	\frac{(2n-2k)!}{(n-2k)!}
	\cr
	&=
	\sum_{0 \leq k \leq n}
	\binom{2k}{k}
	\binom{2n-2k}{n-k} \binom{2k}{n}.
\end{align}
This is an interesting identity,
because it features the
\emph{Franel numbers} 
$f_n=\sum_{k=0}^n \binom{n}{k}^3$, 
which have an intimate relation
with the more famous
\emph{Ap\'ery numbers} $a_n$, viz.,
\[
	a_n=
	\sum_{0 \leq k \leq n}
	\binom{n}{k}^2\binom{n+k}{k}^2
	=
	\sum_{0 \leq k \leq n}
	\binom{n}{k}\binom{n+k}{k} f_n,
\]
see \cite{St94} for comprehensive
information about this
intriguing identity, 
which surprisingly can be seen as a 
descendant of Bailey's bilinear 
generating function for the Jacobi
polynomials, for which I have
given a combinatorial proof a
long time ago in my habilitation thesis 
\cite{St90}.   
Incidentally, there
is another formula which
looks deceptively similar to
(\ref{eqn:franel-1}) ---
watch the last binomial
coefficient of the right of both formulas! ---, 
but which is not the same:
\begin{equation}
\label{eqn:franel-2}
	\sum_{0 \leq k \leq n}  
	\binom{n}{k}^3
	=
	\sum_{0 \leq k \leq n} 
	\binom{2k}{k}\binom{2n-2k}{n-k}\binom{n}{2k}.
\end{equation}
The equivalence of the two summations of 
Eq.~(\ref{eqn:franel-1})
and 
Eq.~(\ref{eqn:franel-2})
is not obvious! It amounts to 
show the hypergeometric identity
\[
	\frac{1}{2^n}
	\binom{2n}{n}
	\hg{3}{2}{1/2,1/2-n/2,-n/2}{1/2-n,1/2-n}{1}
	=
	\hg{3}{2}{-n,1/2-n/2,-n/2}{1,1/2-n}{1},
\]
which does not seem to fall
under one of the standard 
hypergeometric transformations ---
but see a remark on this below.
\end{itemize}
Identity (\ref{eqn:main2}), as well 
as the particular cases mentioned, can 
be verified algorithmically
(independently from the derivation 
given here, which after all is based on 
two nontrivial results about 
generating functions) by
\begin{itemize}
\item[a)] using
	Doron Zeilberger's method
	for determining recurrence 
	operators for hypergeometric 
	expressions, see e.g.\ 
	\cite{PWZ96}, which
	I have executed myself, but
	I will not present here details about 
	the operators and the
	proof certificates; 
\item[b)] using
	Christian Krattenthaler's
	program HYP for
	verifying and/or discovering
	hypergeometric transformation
	identities --- which 
	Christian has done 
	successfully in \cite{Kr14}.
\end{itemize}


After this hypergeometric digression, 
we turn to the identity of
Eq.~(\ref{eqn:main1}) 
again. In the sequel it will be assumed 
for convenience that $\alpha=0$, 
thus writing now $\mc{L}(x,y)$
in place of $\mc{L}^{(0)}(x,y)$.
We then have
\begin{equation}
\label{eqn:main5}
	\mc{L}_n(2x,y)^2
	=
	\sum_{0 \leq k \leq n}
	\binom{n}{k}^2 
	(2k)! \, x^{2k} \,
	\mathcal{L}_{2n-2k} (x,y).
\end{equation}
From the umbral property 
(\ref{eqn:umbral})
we can write
\begin{align*}
	\mc{L}_n(2x,y) &= 
	\mc{L}_n(x,\mc{L}(x,y))
	\cr
	&=
	\sum_{0 \leq k \leq n} 
	\binom{n}{k}
	(1+n-k)_k x^k 
	\mc{L}_{n-k}(x,y)
	\cr
	&=
	\sum_{0 \leq k \leq n}
	\binom{n}{k}^2 k! \,  x^k 
	\mc{L}_{n-k}(x,y)
	\cr
	&=
	\sum_{0 \leq k \leq n}
	\binom{n}{k}^2 \mc{L}_k(x,0) 
	\mc{L}_{n-k}(x,y).
\end{align*}
If we now introduce
\[
	\mc{P}_n(x,y)= 
	\sum_{0 \leq k \leq n}
	\binom{n}{k}^2 x^k y^{n-k}
\]
as the 
\emph{homogeneous Legendre polynomials}, 
then, using the umbral substitution
\[
	\Lambda : 
	\begin{cases}
	x^k \to \mc{L}_k(x,0) &(k \geq 0),
	\cr
	y^\ell \to \mc{L}_\ell(x,y)
	&(\ell \geq 0),
	\end{cases}
\]
and writing it in compositional form,  
we turn the preceding identity into
\[
	\mc{L}_n(2x,y) =
	\Lambda \circ
	\mc{P}(x,y).
\]
On the other hand, the right-hand
side of (\ref{eqn:main5}) is just
\begin{align*}
	\sum_{0 \leq k \leq n}
	\binom{n}{k}^2 
	(2k)! \, x^{2k} \,
	\mc{L}_{2n-2k} (x,y)
	&=
	\sum_{0 \leq k \leq n}
	\binom{n}{k}^2 
	\mc{L}_{2k}(x,0)\,
	\mc{L}_{2n-2k} (x,y)
	\cr
	&=
	\Lambda \circ \mc{P}(x^2,y^2),
	\end{align*}
so we end up with a very pleasing version
of (\ref{eqn:main1}): 
\[
	\left[\,
	\Lambda \circ \mc{P}(x,y)\, \right]^2
	=
	\Lambda \circ \mc{P}(x^2,y^2).
\]
One can even show that the combinatorial 
Legendre polynomials are the only 
(nontrivial)
homogeneous polynomials which satisfy 
this umbral substitution property
w.r.t. $\Lambda$.

\medskip

Back to combinatorics.
Write 
(\ref{eqn:main1}) as
\begin{equation}
\label{eqn:main6}
	\mathcal{L}_n(2x,1)^2 =
	\sum_{0 \leq k \leq n} 
	\binom{n}{k}^2
	(2k)! \, x^{2k} \, 
	\mathcal{L}_{2n-2k}(x,1).
\end{equation}
Then, in view of the interpretation of 
the Laguerre polynomials
$\mc{L}_n^{(0)}(x,y)$
as matching polynomials of the complete 
bipartite graph $K_{n,n}$, both sides of 
Eq.~(\ref{eqn:main6}) 
count matchings 
(not necessarily perfect ones),
the factor~2 on the left giving 
rise to 2-sorted matchings, as 
mentioned in
Section~\ref{ssec:laguerreconfig}.
\begin{itemize}
\item[--] 
	On the left:
	pairs of 2-sorted
	(red and blue edges)
	matchings of $K_{n,n}$,
	as shown in 
	Figure~\ref{fig:finala}
	for $n=5$, with 
	two independent $K_{5,5}$'s
	(in green and magenta);
\begin{figure}[htbp]
  	 \centering
   	\includegraphics[width=4in]	
	{Kgraphs-1a.pdf}
	\caption{A configuration
	for $n=5$,
	counted by $\mc{L}_5(2x+1)^2$}
\label{fig:finala}
\end{figure}

\item[--] 
	On the right:
	matchings of $K_{2n,2n}$ having a
	perfect kernel  
	$K_{2k,2k}$ $K_{2k,2k}$
	and an ordinary
	matching for the complementary
	$K_{2n-2k,2n-2k}$ (in green), 
	as shown in
	Figure~\ref{fig:finalb}.
\begin{figure}[htbp]
  	\centering
   	\includegraphics[width=4in]	
	{Kgraphs-2.pdf}
	\caption{A configuration
	for $n=5, k=4$,
	counted by
	$\binom{5}{2}^2\,
	4!\, x^4\, \mc{L}_6(x,1)$}
\label{fig:finalb} 
\end{figure}
\end{itemize}

One would think that such an
explicit description of
two families of matchings 
should make a bijective proof
feasible, but I have not
been able to achieve this ---
so I leave it as a puzzle.


\vskip8mm

{\bf Acknowledgements.}
I would like to thank 
Dominique Foata, 
Christian Krattenthaler,
and Karol A. Penson 
and his collaborators
for comments, suggestions 
and discussions. 

\vskip5mm

\begin{thebibliography}{12}
\setlength{\itemsep}{1.5mm}
\bibitem{BDGP12}
	D. Babusci, 
	G. Dattoli,
	K. G\'orska,
	and 
	K.A. Penson,
	\emph{Generating functions for 
	Laguerre polynomials: New
	identities for lacunary series},
{\tt ar$\chi$iv:1210.3710}.
	
\bibitem{BDGP16}
	D. Babusci,
	G. Dattoli,
	K. G\'orska,
	and
	K.A. Penson,
	\emph{Lacunary generating
	functions for the Laguerre
	polynomials}, 
	S\'eminaire Lotharingien
	Combin. {\bf 76} (2017), 
	Article~B76b.

\bibitem{BLL98}
	F. Bergeron,
	G. Labelle, and
	P. Leroux,
	\emph{Combinatorial
	Species and Tree-like Structures},
	Encyclopedia of Mathematics and its
	Applications
	{\bf 67},
	Cambridge University Press
	1998.
	
\bibitem{Co74}
	L. Comtet,
	\emph{Advanced Combinatorics},
	D.~Reidel Publ. Comp.,
	1974.

\bibitem{Er81}
	A. Erd\'elyi (ed.),
	\emph{Higher Transcendental Functions} 
	(The Bateman
	Manuscript Project),
	R.E.~Krieger Pub. Comp.,
	1981.
	
\bibitem{EG76}
	S. Even and
	J. Gillis,
	\emph{Derangements and Laguerre polynomials},
	Math. Proc. Camb. Phil. Soc. {\bf 79} (1976),
	135--143.
	
\bibitem{Fl80}
	P. Flajolet,
	\emph{Combinatorial aspects of continued
	fractions},
	Discrete Math. {\bf 32} (1980),
	125--161.
	
\bibitem{FFV80}
	P. Flajolet,
	J. Fran\c con and
	J. Vuillemin,
	\emph{Sequence of operations analysis
	for dynamic data structures},
	J. Algorithms {\bf 1} (1980), 111--141.
		
\bibitem{FS09}
	P. Flajolet and
	R. Sedgewick,
	\emph{Analytic Combinatorics},
	Cambridge University Press, 2009.
	
\bibitem{Fo74}
	D. Foata,
	\emph{La s\'erie
	g\'en\'eratrice exponentielle
	dans les probl\`emes
	d'\'enum\'eration},
	Presses de l'Universit\'e
	de Montr\'eal,
	1974.
	
\bibitem{Fo78}
	D. Foata,
	\emph{A combinatorial proof
	of the Mehler formula},
	J. Combin. Theory Ser.~A 
	{\bf 24} 
	(1978), 367--376.
	
\bibitem{FG79}
	D. Foata and 
	A. M. Garsia,
	\emph{A combinatorial approach
	to the Mehler formulas 
	for the Hermite polynomials},
	Relations between
	Combinatorics
	and other parts of 
	Mathematics
	(Proc. of Symposia in
	Pure Math., vol.~34;
	D.K.~Ray-Chaudhuri, Ed.),
	Amer. Math. Soc.,
	Providence, R.I.,
	1979, 163--179.
	
\bibitem{Fo81}
	D. Foata,
	\emph{Some Hermite 
	polynomial identities and their 
	combinatorics},
	Adv. Appl. Math. {\bf 2} 
	(1981),
	250--259.
		
\bibitem{FS81}
	D. Foata et 
	V. Strehl,
	\emph{Une extension multilin\'eaire 
	de la formule d'Erd\'elyi pour les
	produits de fonctions
	hyperg\'eom\'etriques confluentes},
	C.~R. Acad. Sci. Paris {\bf 293}
	(1981), 517--520.
	
\bibitem{FS83}
	D. Foata 
	and V. Strehl,
	\emph{Combinatorics of Laguerre polynomials},
	in: Enumeration and Design, 
	D.M.~Jackson
	and 
	S.A.~Vanstone 
	(eds.),
	Waterloo, 1982,
	Academic Press, Toronto, 1984,
	pp.~123--140.

\bibitem{FL83}
	D. Foata and
	P. Leroux,
	\emph{Polyn\^omes de Jacobi,
	interpr\'etation combinatoire
	et fonction g\'en\'eratrice},
	Proc. Amer. Math. Soc.
	{\bf 87} (1983), 47--53. 
	
\bibitem{Fo84}
	D. Foata,
	\emph{Combinatoire des identit\'es sur les
	polyn\^omes orthogonaux},
	Proc. Internat. Congress
	of Mathematics, Warsaw,
	Aug.~16--24, 1983,
	Polish Scientific Publications and
	North-Holland, 1984,
	pp.~1541--1553.
	
\bibitem{FZ88}
	D. Foata and
	D. Zeilberger,
	\emph{Laguerre polynomials, weighted 
	derangements and positivity},
	SIAM J. Discrete Math. {\bf 1} (1988),
	425--433.
		
\bibitem{GR80}
	A.M. Garsia and J. Remmel,
	\emph{A combinatorial interpretation of 
	$q$-derangement and $q$-Laguerre numbers},
	Europ. J. Combin.
	{\bf 1} (1980), 47--59.
	
\bibitem{Ge89}
	I.M. Gessel,
	\emph{Generalized rook polynomials and
	orthogonal polynomials}, in:
	$q$-Series and Partitions,
	D.~Stanton (ed.),
	IMA Volumes in Mathematics and its
	Applications, vol.~18,
	Springer--Verlag 1989.
	
\bibitem{GJ83}
	I.P. Goulden and
	D.M. Jackson,
	\emph{Combinatorial
	Enumeration},
	Wiley--Interscience, 1983.
	
\bibitem{HM95}
	F.K. Hwang and 
	C.L. Mallows,
	\emph{Enumerating nested and 
	consecutive partitions}, 
	J. Combin. Theory Ser.~A {\bf 70} 
	(1995), 323-333.

\bibitem{Ja76}
	D. Jackson,
	\emph{Laguerre polynomials and derangements},
	Math. Proc. Camb. Phil. Soc. {\bf 80} (1976),
	213--214.
	
\bibitem{Kr14}
	C. Krattenthaler,
	\emph{private communication},
	27.10.2014.
	
\bibitem{KRY09}
	J.P.S. Kung,
	G.-C- Rota, and
	C.H. Yan,
	\emph{Combinatorics: The Rota Way},
	Cambridge University Press, 2009.
	
\bibitem{LS84}
	P. Leroux and 
	V. Strehl,
	\emph{Jacobi polynomials:
	combinatorics of the basic identities},
	Discrete Math.
	{\bf 57} (1985),
	167--187.
	
\bibitem{LP86}
	L. Lov\'asz and
	M.D. Plummer,
	\emph{Matching Theory},
	Annals of Discrete Mathematics 
	{\bf 29},
	North-Holland, 1986.
	
\bibitem{MR70}
	R. Mullin and
	G.-C Rota,
	\emph{On the foundations of combinatorial
	theory: III. Theory of binomial enumeration},
	in:
	Graph Theory and its Applications,
	B.~Harris (ed.),
	Academic Press,
	New York and London, 1970, pp.~167--213.
	
\bibitem{NI10}
	\emph{NIST Handbook of 
	Mathematical Functions},
	F.W.J.~Olver et al. (eds.),
	Cambridge University 
	Press, 2010.
	
\bibitem{OEIS}
	OEIS: \emph{The On-Line Encyclopedia of Integer Sequences}, available electronically at 
        {\tt http://oeis.org}, 2017.

\bibitem{PWZ96}
	M. Petko\v{v}sek,
	H.S. Wilf, and 
	D. Zeilberger,
	\emph{A=B},
	A.K.~Peters, Ltd., 1996.
		
\bibitem{Ra66}
	E.D. Rainville,
	\emph{Special Functions},
	Chelsea, Bronx,
	1971.
	
\bibitem{Ri58}
	J. Riordan,
	\emph{An Introduction to Combinatorial 
	Analysis},
	J.~Wiley and Sons, 
	1958.
	
\bibitem{Ro84}
	S. Roman,
	\emph{The Umbral Calculus},
	Academic Press, 1984.
	
\bibitem{RKO73}
	G.-C. Rota,
	D. Kahaner, and
	A. Odlyzko,
	\emph{On the foundations of
	combinatorial theory: VIII.
	Finite operator calculus},
	J. Math. Anal. Appl. {\bf 42} (1973),
	684--760. 
		
\bibitem{St90}
	V. Strehl,
	\emph{Zykel-Enumeration bei
	lokal-strukturierten Endofunktionen},
	Habilitations\-schrift,
	Universit\"at 
	Erlangen--N\"urnberg, 1990. 
	
\bibitem{St94}
	V. Strehl,
	\emph{Binomial identities ---
	combinatorial and algorithmic aspects},
	Discrete Math. {\bf 136}
	(1994), 309--346.
	
\bibitem{Vi84}
	G. Viennot,
	\emph{A combinatorial theory for
	general orthogonal polynomials
	with extensions and applications}, in:
	P\^olynomes Orthogonaux et Applications,
	Bar-le-Duc 1984, C.~Brezinski et al. (eds.),
	Lecture Notes in Mathematics, vol.~1171,
	Springer--Verlag 1985.
	
\bibitem{Wi90}
	H.S. Wilf,
	\emph{generatingfunctionology},
	Academic Press, 1990.
	
\bibitem{Ze92}
	J. Zeng,
	\emph{Weighted derangements and the
	linearization coefficients of
	orthogonal Sheffer polynomials},
	Proc. London Math. Soc. {\bf 65} (1992),
	1--22.

\end{thebibliography}

\end{document}