\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amscd}
\parindent=0pt
\textheight 250mm
\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}

%%%%%%%%%%%%%%%%%%%%%%
% \'Enonc\'es
%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{expl}{Example}[section]
\newtheorem{theorem}[expl]{Theorem}
\newtheorem{corollary}[expl]{Corollary}
\newtheorem{definition}[expl]{Definition}
\newtheorem{prop}[expl]{Proposition}
\newtheorem{algorithm}[expl]{Algorithm}
\newtheorem{lemma}[expl]{Lemma}
\newtheorem{rem}[expl]{Remark}
\newtheorem{note}[expl]{Note}
\newtheorem{appli}[expl]{Applications}

\def\Proof{\medskip\noindent {\it Proof --- \ }}
\def\cqfd{\hfill $\clubsuit$ \bigskip}


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

\def\A{{\sym A}}
\def\B{{\cal B}}
\def\Cl{{\cal C}}
\def\C{\mathb{C}}
\def\E{{\cal E}}
\def\ES{{\cal ES}}
\def\F{{\cal F}}
\def\I{{\cal I}}
\def\N{{\sym N}}
\def\M{{\cal M}}
\def\Q{\mathbb{Q}}
\def\R{{\sym R}}
\def\ba{{\mathbf a}}
\def\L{{\mathbf L}}
\def\V{{\mathbf V}}
\def\T{{\cal T}}
\def\sbs{{\sym Subs}}
\def\fst{{\bf F\hspace{-1mm}St}}
\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\scal#1#2{\langle #1| #2\rangle}
\def\ul#1{\underline{#1}}
\def\ol#1{\overline{#1}}


%%%%%%%%%%%%%%%
%Greek letters
%%%%%%%%%%%%%%%

\def\al{{\alpha}}
\def\be{{\beta}}
\def\si{\sigma}
\def\om{\omega}
\def\ep{\epsilon}



\begin{document}
\noindent

\vspace{1cm}
\hfill{\it Paris, le 16 F\'evier 2005, 18h21}

\ss
{\it Please, don't spread before discussion}


\section{A version of the exponential formula}\label{expf}

Applying the exponential paradigm one can feel sometimes incomfortable wondering whether ``one has the right'' to do 
so (as for example for coloured structures). The following is aimed at giving a rather large framework where this 
formula holds.

\ss
Exponential formula can be traced back to works by Touchard and Ridell \& Uhlenbeck \cite{To,RU}. 
For an other exposition see for example \cite{Jo,St}.
 
We are interested to compute various examples of EGF for combinatorial objects having 
(a finite set of) nodes (i.e. their set-theoretical support) so we use as central concept the mapping $\sigma$ which 
associates to every structure, its set of nodes.\\
We need to draw what could be called ``square-free decomposable objects'' (SFD). This version is suited to our needs 
for the ``exponential formula''. It is sufficiently general to contain, as a particular case, the case of multivariate series. 
\\
Let $\fst$ the category of finite sets and $\Cl$ be a class of (combinatorial) objects endowed with a mapping $\si\ :\ \Cl\mapsto \fst$. The setting 
$(\Cl,\si)$ will be called (SFD) if it fulfills the two following conditions.

\bs
(DS) {\it Direct sum}\pointir There is a (partial) binary law $\oplus$ on $\Cl$, defined for couples of objects 
$(\om_1,\om_2)$ such that $\si(\om_1)\cap \si(\om_2)=\emptyset$, which is associative, commutative and such that  
\begin{equation}\label{plus}
\Cl_{F_1}\times \Cl_{F_2}\stackrel{\oplus}{\ra} \Cl_{F_1\cup F_2}
\end{equation}
is into.\\
Moreover, $\Cl_\emptyset$ consists in a single element $\{\ep\}$ which is neutral in the sense that, identically 
\begin{equation}
\ep\oplus \om=\om \oplus \ep=\om
\end{equation}
(LP) {\it Levi's property}\pointir Let $\om=\om_1\oplus \om_2=\om^1\oplus \om^2$ be two decompositions. 
Then it can be found a four terms decomposition $\om=\oplus_{i,j=1,2}\om_j^i$ refining the original data in the sense 
that the maginal sums give the factors of the decompositions i.e. 
\begin{equation}
\om_j=\om_j^1\oplus \om_j^2\  {\rm and}\ \om^i=\om_1^i\oplus \om_2^i;\ i,j=1,2
\end{equation}

\begin{note}
Condition \mref{plus} implies that $\si(\om_1\oplus \om_2)=\si(\om_1)\sqcup \si(\om_2)$.
\end{note}

Now, an {\it atom} is any object $\om\not=\ep$ which cannot be split, formally 
\begin{equation}
\om=\om_1\oplus \om_2\Longrightarrow \ep\in \{\om_1,\om_2\}
\end{equation}

\begin{expl}
As example of this setting we have:\\
\begin{enumerate}\label{ex1}
\item\label{intsf} the positive square-free integers $\si(n)$ being the set of primes which divide $n$, the atoms being the 
primes.
\item\label{int} the positive integers $\si(n)$ being the set of primes which divide $n$, the atoms being the 
primes.
\item\label{graphs} graphs, hypergraphs, (finitely) coloured, weighted graphs, $\si(G)$ being the set of nodes and $\oplus$ the 
juxtaposition, here the atoms are connected graphs.
\item\label{endof} the class of endofunctions $f$ with $\si(f)=dom(f)$
\item\label{ex13} the (multivariate) polynomials in $\N[X]$ with $\si=Alph$ and $\oplus=+$.
\item\label{ex14} the square-free monic (for a given order on the variables) polynomials ; $\si(P)$ being the set of irreducible 
monic divisors of $P$ and $\oplus$ being the multiplication.
\item\label{ex15} complex algebraic curves ; $\si(V)$ being the set of monic irreducible bivariate polynomials vanishing 
on an infinite subset of $V$.
\end{enumerate}
\end{expl}

The prescriptions (DS,LP) imply that decomposition of objects into atoms always exists and is unique. 
\begin{prop}
Let $\om\in \Cl$ then $\om=\om_1\oplus\om_2\oplus\cdots\oplus\om_l$ the $\om_i$ being (dinstinct) atoms and the set 
$\{\om_1,\om_2\cdots\om_l\}$ depends only on $\om$.
\end{prop}

In the class $\Cl$, objects are conceived to be  ``measured'' by different parameters (data in statistical language). So, to get 
a general purpose tool, we suppose that the statistics takes it's values iin a ring $K$ which contains $\Q$ (as, to write 
EGFs it is convenient to have no trouble with the fractions $\frac{1}{n!}$). Let then $c: \Cl\ra K$ be the 
given statistic. In order to write generating series, we need 
\begin{enumerate}
\item that the sum $c_F=\sum_{\om \in \Cl_F}c(w)$ exists 
\item that $F\ra c_F$ should depend only of the cardinality of $F$.
\item $c(\om_1\oplus\om_2)=c(\om_1).c(\om_2)$
\end{enumerate}
We formalize it in 

\bs
(LF) {\it Local finiteness}\pointir For each finite set $F$, the subclass 
\begin{equation}
\Cl_F=\{\om\in \Cl| \si(\om)=F\}
\end{equation}
is a finite set.\\
(Eq) {\it Equivariance}\pointir 
\begin{equation}
|F_1|=|F_2|\Longrightarrow c_{F_1}=c_{F_2}
\end{equation}
(Mu) {\it Multiplicativity}\pointir 
\begin{equation}
c(\om_1\oplus\om_2)=c(\om_1).c(\om_2)
\end{equation}

\begin{note}
a) In fact, (LF) is a property of the class $\Cl$, while (Eq) is a property of the statistics. 
In practice, we choose $\Cl$ which is locally finite and choose equivariant statistics for instance
$$
c(\om)=x^{\rm (number\ of\ cycles)}y^{\rm (number\ of\ fixed\ points)}
$$ 
for some variables $x,y$.

\bs
b) More generally, it is typical to take integer-valued partial (additive) statistics $c_1, \cdots c_i,\cdots ,c_r$ 
(for every $\omega\in \Cl$, $c_i(\omega)\in \N$) and set
$c(\om)=x_1^{c_1(\omega)}x_2^{c_2(\omega)}\cdots x_r^{c_r(\omega)}$.

\bs 
c) The class of examples \ref{ex1}.\ref{int} is not locally finite, but other examples satisfy (LF): \ref{ex1}.\ref{graphs} 
if one asks that the number of arrows and weight is finite, \ref{ex1}.\ref{intsf} and  \ref{ex1}.\ref{ex13} to 
\ref{ex1}.\ref{ex15} in any case.
\end{note}

Now, we are in position to state the exponential formula as it will be used throughout the paper.

\begin{prop} Let $\Cl$ be a locally finite (SFD) and $c: \Cl\ra K$ an equivariant statistics on $\Cl$.  
For every subclass $\F$ one sets the following exponential generating series
\begin{equation}
E(\F;z)=\sum_{n=0}^\infty c(\F_{[1..n]}) \frac{z^n}{n!}
\end{equation}
Let $\Cl^a$ be the set of atoms of $\Cl$. Then, one has 
\begin{equation}
E(\Cl;z)=e^{E(\Cl^a;z)}
\end{equation}
\end{prop} 
\Proof  (First Step)\pointir We consider the subclasses of objects the atoms of which have a support of cardinality $n$ 
i.e.
\begin{equation}
\Cl[n]=\{\om\in \Cl| \om=\om_1\oplus\om_2\oplus\cdots \oplus\om_s=\om\ \textrm{ with } \om_i\in\Cl^a \textrm{ and } |\si(\om)|=n \textrm{ for } i=1..s\}
\end{equation}

These subclasses are closed under compositions (i.e. under $\oplus$) and decompositions and their 
atoms $\Cl^a[n]=\{\om\in  \Cl[n] \cap \Cl^a \}$. 
Now, one has, thanks to the partitions of $[1..n]$
\begin{eqnarray}
\Cl_{[1..n]}=\bigsqcup_{k\geq 0,\ 0<n_1<n_2<\cdots <n_k\atop n_1+n_2+\cdots n_k=n}
\bigsqcup_{|P_j|=n_j\atop  P_1\sqcup P_2\sqcup \cdots P_k=[1..n]} 
\Cl_{P_1}\oplus \Cl_{P_2}\oplus\cdots\oplus \Cl_{P_k}\\
c(\Cl_{[1..n]})=\sum_{k\geq 0}\sum_{0<n_1<n_2<\cdots <n_k\atop n_1+n_2+\cdots n_k=n}
\sum_{|P_j|=n_j\atop  P_1\sqcup P_2\sqcup \cdots P_k=[1..n]} 
c(\Cl_{P_1}) c(\Cl_{P_2})\cdots c(\Cl_{P_k})
\end{eqnarray}
as, for disjoint sets, it is easy to check that $c(\Cl_X\oplus \Cl_Y)=c(\Cl_X)c(\Cl_Y)$. Now, due to the equivariance of $c$ and to the 
fact that partitions $(P_1,P_2, \cdots ,P_k)$ such that $P_j=n_j$ and  $P_1\sqcup P_2\sqcup \cdots P_k=[1..n]$ are in number 
$$
\frac{n!}{n_1!n_2!\cdots n_k!}
$$
we get
\begin{equation}
c(\Cl_{[1..n]})=\sum_{k\geq 0}\sum_{0<n_1<n_2<\cdots <n_k\atop n_1+n_2+\cdots n_k=n}
\frac{n!}{n_1!n_2!\cdots n_k!}
c(\Cl_{[1..n_1]}) c(\Cl_{[1..n_2]})\cdots c(\Cl_{[1..n_k]})
\end{equation}
thus
\begin{equation}
E(\Cl)=\prod_{n>0}E(\Cl[n])
\end{equation}
We then compute the factors. 
\begin{equation}
E(\Cl[n])=\sum_{k\geq 0} c(\Cl[n]_{[1..nk]}) \frac{z^{nk}}{(nk)!}
\end{equation}
but 
\begin{equation}
E(\Cl^a[n])=c(\Cl^a_{[1..n]}) \frac{z^{n}}{n!}
\end{equation}
(one monomial) and
\begin{eqnarray*}
e^{E(\Cl^a[n])}=\sum_{k\geq 0}c(\Cl^a_{[1..n]})^k \frac{z^{nk}}{(n!)^kk!}=
\sum_{k\geq 0}c(\Cl^a_{[1..n]})^k \frac{z^{nk}}{(nk!)}\frac{(nk)!}{(n!)^kk!}=\\
\sum_{k\geq 0} c(\Cl[n]_{[1..nk]}) \frac{z^{nk}}{(nk)!}=E(\Cl[n])
\end{eqnarray*}
due to the fact that the number of (unordered) partitions of $[1..nk]$ into $k$ blocs of cardinality $n$ is $\frac{(nk)!}{(n!)^kk!}$. 
To end the proof, it suffices to remark that $\Cl^a=\sqcup_{n>0}\Cl^a[n]$ and then 
\begin{equation}
E(\Cl)=\prod_{n>0}E(\Cl[n])=\prod_{n>0}e^{E(\Cl^a[n])}=e^{\sum_{n>0}E(\Cl^a[n])}=e^{E(\Cl^a)}
\end{equation}
\cqfd

\begin{note}
The proof suggests us that it is fruitful to factor a class $\Cl$ into 
(full) subclasses i.e. that are generated by a partition of the atoms.
\end{note}


\begin{thebibliography}{ABC}
%
\bibitem{Co} Comtet L., {\it Analyse combinatoire}, PUF (1970)
%
\bibitem{Jo} Joyal A., {\it Species ??}, Advances in Math.
%
\bibitem{RU} Ridell R.J., Uhlenbeck G.E., {\it On the theory of the virial development of the equation of state of monomatomic gases}, 
 J. Chem. Phys. {\bf 21} (1953), 2056-2064. 
%
\bibitem{St} Stanley R., {\it Enumerative Combinatorics Vol I and II}, Cambridge. 
%
\bibitem{To} Touchard J., {\it Sur les cycles des permutations}, Acta Math. {\bf 70} (1939), 243-297.
%
\end{thebibliography}

\end{document} 