%matana.tex:
%%the edition to  Plain TeX file by Moa Apagodu, David Applegate, Neil Sloane, and Doron Zeilberger 
%Gift Exchange Problem

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%end macros

\centerline
{
\bf The Gift Exchange Problem, Part II
}

By Moa Apagodu, David Applegate, Neil Sloane, and Doron Zeilberger

So far we had a $k$-free (partial) recurrence for  
$E_\sigma(n,k)$ (for $\sigma=2,3$) (that implied recurrences for $G_\sigma$)
and the trivial
$n$-free (partial) recurrence, $(5)$, for the general $E_\sigma(n,k)$, It turns out that
$E_\sigma(n,k)$ satisfies a pure (ordinary) recurrence in $k$, and that
$G_\sigma(n)$ satisfies a linear recurrence with polynomial coefficients, in $n$, 
for {\it every} $\sigma$.

Indeed: we have
$$
\sum_{k} E_\sigma(n,k) {{y^k} \over {k!}}=
{{1} \over {n!}} \left ( \sum_{i=0}^{\sigma+1} {{y^i} \over {i!}} \right )^n
$$
Using the J.C.P.Miller ([Z1]) method we get the {\it pure recurrence} that enables us, for a given
$n$, to compute fast the numbers $E_\sigma(n,k)$ for a {\it fixed} $n$, without having
to use the $E_\sigma(n-1,k)$'s
$$
\sum_{i=0}^{\sigma} \left ( {{n} \over {i!}} - {{k} \over {(i+1)!}}+ {{1} \over {(i-1)!+i!}} \right ) E_\sigma(n,k-i) \,\, = 0
\,\, \quad .
$$

We also have, using Euler's integral representation for the factorial
$$
k!= \int_{0}^{\infty} e^{-y} y^k  \, dy \quad,
$$
that we have the integral representation
$$
G_\sigma(n)={{1} \over {n!}} \int_{0}^{\infty} e^{-y} 
\left ( \sum_{i=0}^{\sigma+1} {{y^i} \over {i!}} \right )^n \, dy .
$$
It follows from the (discrete) Almkvist-Zeilberger algorithm [AlZ] that $G_\sigma(n)$ satisfies
{\it some} homogeneous linear recurrence with polynomial (in $n$) coefficients , and it follows
from Theorem AZ of [ApZ] that its order is $\sigma+1$. The Maple package
{\tt DavidNeil} accompanying this article can easily compute these recurrences, and the
the recurrences for $1 \leq \sigma \leq 6$, together with the implied asymptotics
(using the Poincare-Birkhoff-Trijinksi method as exposited in [WiZ] and implemented in [Z2])
to the sixth-order, can be found in:

{\tt http://www.math.rutgers.edu/~zeilberg/tokhniot/oDavidNeil1} .

Regarding the {\it generating function}
$$
g_\sigma(x):=\sum_{n=0}^{\infty} G_\sigma(n) x^n ,
$$
it follows from the (discrete) Almkvist-Zeilberger algorithm [AlZ] that $g_\sigma(x)$ satisfies
{\it some} homogeneous linear differential equation with polynomial (in $x$) coefficients , and it follows
from the obvious analog of Theorem AZ of [ApZ] that its order is $\sigma+1$. 

See

{\tt http://www.math.rutgers.edu/~zeilberg/tokhniot/oDavidNeil2}

for the differential equations for $1 \leq \sigma \leq 6$.

These differential equations transcribe to linear recurrences in $G_\sigma(n)$, that
are {\it not} minimal-order, and for small $\sigma$ coincide with the ones obtained
above using Sister Celine's technique.



{\bf Additional References}

[AlZ] G. Almkvist and D. Zeilberger, The method of differentiating under the integral sign, J.
Symbolic Computation 10 (1990), 571-591.

[ApZ]  Moa Apagodu and Doron Zeilberger,
{\it Multi-Variable Zeilberger and Almkvist-Zeilberger Algorithms and the Sharpening of Wilf-Zeilberger Theory},
Adv. Appl. Math. {\bf 37}(2006), 139-152.

[WiZ] Jet Wimp and Doron Zeilberger,
{\it Resurrecting the asymptotics of linear recurrences}, J. Math. Anal. Appl. {\bf 111}(1985), 162-177.

[Z1] Doron Zeilbeger
{\it The J.C.P. Miller Recurrence for exponentiating a polynomial, and its q-Analog},
J. Difference Eqs. and Appls. {\bf 1}(1995), 57-60. 

[Z2] Doron Zeilbeger,
{\it AsyRec: A Maple package for Computing the Asymptotics of Solutions of Linear Recurrence Equations with Polynomial Coefficients},
The Personal Journal of Ekhad and Zeilberger, 
{\tt http://www.math.rutgers.edu/~zeilberg/pj.html}


\end






