\documentclass[12pt]{article}
\parindent=0pt
\usepackage{frenchle}
\usepackage{times}
\pagestyle{empty}
\textheight 240mm
\textwidth 160mm
\hoffset -14mm
\voffset -26mm


%%%%%%%%%%%%%%%%%%%%%%
% Fontes
%%%%%%%%%%%%%%%%%%%%%%

 \font\twelvesym=msbm10 at 12pt
 \font\tensym=msbm10
 \font\sevensym=msbm7
 \font\fivesym=msbm5

 \font\twelvegoth=eufb10 at 12pt
 \font\tengoth=eufb10
 \font\sevengoth=eufb7
 \font\fivegoth=eufb5

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

\newfam\symfam
\textfont\symfam=\tensym
\scriptfont\symfam=\sevensym
\scriptscriptfont\symfam=\fivesym
\def\sym{\fam\symfam\tensym}
\def\fns{\footnotesize}

\newfam\gothfam
\textfont\gothfam=\tengoth
\scriptfont\gothfam=\sevengoth
\scriptscriptfont\gothfam=\fivegoth
\def\goth{\fam\gothfam\tengoth}

%%%%%%%%%%%%%%%%%%%%%%
% Sauts
%%%%%%%%%%%%%%%%%%%%%%

\def\hs{\hbox to 3mm{}}
\def\hhs{\hbox to 5cm{}}
\def\ss{\smallskip}
\def\ms{\smallskip}
\def\bs{\bigskip}
\def\bbss{\vskip 6mm}

%%%%%%%%%%%%%%%%%%%%%%
% Divers
%%%%%%%%%%%%%%%%%%%%%%

\def\A{{\sym A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\E{{\sym E}}
\def\F{{\sym F}}
\def\N{{\sym N}}
\def\M{{\cal M}}
\def\J{{\mathcal J}}
\def\ole{\overline{end}}
\def\op{\overline{perm}}
\def\ra{\rightarrow}
\def\binomial#1#2{\left(\,\matrix{#1 \cr #2}\,\right)}
\def\pointir{\unskip . --- \ignorespaces}
\def\mref#1{(\ref{#1})}
\def\cqfd{\hfill $\Box$ \bigskip}
\def\Box{\fbox{\hspace{0.5mm}}}
\def\rem{{\bf Remarque}\pointir }


\begin{document}
\noindent

\vspace{1cm}
\hfill{\it Paris, le 15 Mai 2003, 21h03}

{\bf 1) Endofunctions by number of cycles\pointir}

\ss
For $f : F\ra F$, we define $f^n=\underbrace{f\circ f\circ\cdots \circ f}_{n\ {\rm factors}}$. Let $p$ be a prime and set 
\begin{equation}
\J_p(n)=\# \{f : [[n]]\ra [[n]] s.t.\ f^{1+p}=f\}
\end{equation}
where $[[n]]:=[1..n]$. One has the following characterization $f^{1+p}=f$ iff every connected component of the graph 
has 
\begin{itemize}
\item a $1$- or a $p$-cycle
\item for all $x$, $f(x)$ is in the cycle
\end{itemize}

then the EGF for connected components with a  $1$-cycle is 
\begin{equation}\label{1cy}
\sum_{n\geq 1}\frac{nt^n}{n!}=te^t
\end{equation}
the EGF for connected components with a $p$-cycle is 
\begin{equation}\label{pcy}
\sum_{n\geq p}\binomial{n}{p}(p-1)!p^{(n-p)}\frac{t^n}{n!}t^n=\frac{t^p}{p}e^{pt}
\end{equation}
Hence, having analyzed the connected components, one gets, with the exponential formula, 
\begin{equation}
\sum_{n\geq 0} \J_p(n) \frac{t^n}{n!}=e^{te^t+\frac{t^p}{p}e^{pt}}
\end{equation}
If, one wants to count these endofonctions more finely, we can get the EGF again with the exponential formula.
with 
\begin{equation}\label{x1cy}
\sum_{n\geq 1}\frac{xnt^n}{n!}=xte^t
\end{equation}
instead of \mref{1cy} and
\begin{equation}\label{ypcy}
\sum_{n\geq p}y\binomial{n}{p}(p-1)!p^{(n-p)}\frac{t^n}{n!}t^n=y\frac{t^p}{p}e^{pt}
\end{equation}
instead of \mref{pcy}, we get
\begin{equation}\label{xypol}
\sum_{n\geq 0} \alpha_{k,l}^{(n)}x^ky^l \frac{t^n}{n!}=\sum_{n\geq 0} H^{(p)}_n(x,y) \frac{t^n}{n!}=
e^{xte^t+y\frac{t^p}{p}e^{pt}}
\end{equation}

\bs
{\bf 2) \'El\'ementary computation of the $\alpha_{k,l}^{(n)}$\pointir}

\ss
By elementary counting, we get 
\begin{equation}
\alpha_{k,l}^{(n)}=\binomial{n}{k}\binomial{n-k}{pl} \frac{(pl)!}{p^l l!}(k+pl)^{n-k-pl}
\end{equation}
and, from \mref{xypol}
\begin{equation}
H^{(p)}_n(x,y) =\sum_{k+3l\leq n}\alpha_{k,l}^{(n)}x^ky^l
\end{equation}

if we glue the two types of cycles, one gets the numbers $\J_p(n,k)$ which is the number of such endofunctions with $k$ 
cycles. These numbers fill a lower triangular matrix ($\J_p(n,k)=0$ for $k>n$). We have
\begin{equation}
\sum_{n\geq 0} \J_p{n,k}^{(n)}x^k \frac{t^n}{n!}=e^{x(te^t+\frac{t^p}{p}e^{pt})}
\end{equation}
and this proves that we are in presence of a {\it substitution matrix}.
\end{document} 