\documentclass[12pt]{article}
\usepackage[latin1]{inputenc}
\usepackage{amsfonts}
%\usepackage[french]{babel}
\usepackage{frenchle}
\usepackage{maple2e}
\usepackage{times}
\def\emptyline{\vspace{12pt}}
\def\maplemultiline#1{\begin{eqnarray*}#1\end{eqnarray*}}
\DefineParaStyle{Maple Output}
\DefineParaStyle{Warning}
\DefineCharStyle{2D Math}
\DefineCharStyle{2D Output}
\textheight 240mm
\textwidth 160mm
\hoffset -14mm
\voffset -26mm
\parindent= 0pt

%%%%%%%%%%%%%%%%%%%%%%
% 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\mhs{\hbox to 1cm{}}
\def\hhs{\hbox to 5cm{}}
\def\sk{\smallskip}
\def\bs{\bigskip}

%%%%%%%%%%%%%%%%%%%%%%
% Fl\^eches et traits
%%%%%%%%%%%%%%%%%%%%%%

\def\ra{\rightarrow}
\def\da{\downarrow}
\def\sw{\swarrow}
\def\se{\searrow}
\def\ne{\nearrow}
\def\lra{\leftrightarrow}
\def\Lra{\Longrightarrow}
\def\ul#1{\underline #1}

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

\def\b{$\bullet\ $}
\def\mod{{\rm mod}}
\def\quo{{\rm quo}}
\def\irem{{\rm rem}}
\def\peb#1{\lfloor #1\rfloor}
\def\peh#1{\lceil #1\rceil}
\def\adots{\mathinner{\mkern2mu\raise1pt\hbox{.}
\mkern3mu\raise4pt\hbox{.}\mkern1mu\raise7pt\hbox{.}}}
\def\binomial#1#2{\left(\,\matrix{#1 \cr #2}\,\right)}
\def\que{{\bf Question}}
\def\rep{{\bf Reponse}}
\def\pointir{\unskip . --- \ignorespaces}
\def\nequiv{\equiv\hspace{-9pt}\slash\hspace{9pt}}
\def\ra{\rightarrow}
\def\lra{\leftrightarrow}
\def\mup{MuPAD}

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

\newtheorem{expl}{Exemple}[section]
\newtheorem{exercice}{Exercice}[section]
\newtheorem{note}[expl]{Note}
\newtheorem{exo}[expl]{Exercice}
\newtheorem{mexo}[expl]{Exercice Machine}
\newtheorem{exm}[expl]{Exerc. Machine}
\newtheorem{theo}[expl]{Th\'eor\`eme}
\newtheorem{corollaire}[expl]{Corollaire}
\newtheorem{definition}[expl]{D\'efinition}
\newtheorem{prop}[expl]{Proposition}
\newtheorem{prdef}[expl]{Proposition/Definition}
\newtheorem{algorithme}[expl]{Algorithme}
\newtheorem{lemme}[expl]{Lemme}
\newtheorem{rem}[expl]{Remarque}
\newtheorem{appli}[expl]{Applications}

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

%%%%%%%%%%%%%%%%%%%%%%
% Lettres
%%%%%%%%%%%%%%%%%%%%%%

\def\A{{\mathbb A}}
\def\B{{\mathbb B}}
\def\E{{\mathbb E}}
\def\F{{\mathbb F}}
\def\N{{\mathbb N}}
\def\C{{\mathbb C}}
\def\R{{\mathbb R}}
\def\Z{{\mathbb Z}}
\def\Q{{\mathbb Q}}
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\ep{\epsilon}
\def\S{{\Sigma}}
\def\Q{{\mathbb Q}}
\def\SG{{\goth S}}

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

\def\b{$\bullet\ $}
\def\hs{\hbox to 3mm{}}
\def\ra{\rightarrow}
\def\mod{{\rm mopt}}
\def\quo{{\rm quo}}
\def\irem{{\rm rem}}
\def\peb#1{\lfloor #1\rfloor}
\def\peh#1{\lceil #1\rceil}
\def\adots{\mathinner{\mkern2mu\raise1pt\hbox{.}
\mkern3mu\raise4pt\hbox{.}\mkern1mu\raise7pt\hbox{.}}}
\def\binomial#1#2{\left(\,\matrix{#1 \cr #2}\,\right)}
\def\la{\leftarrow}
\def\da{\downarrow}
\def\ua{\uparrow}
\def\sea{\searrow}
\def\swa{\swarrow}
\def\mref#1{(\ref{#1})}
\def\up#1{\raise 1ex\hbox{\fns#1}}
\def\cls{$\clubsuit$}
\def\sps{$\spadesuit$}
\def\hes{$\heartsuit$}
\def\dis{$\diamondsuit$}

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

\def\ss{\smallskip}
\def\ms{\medskip}
\def\bs{\bigskip}
\def\small{\footnotesize}
\def\b{$\Bullet\ $}
\def\gcr{\hfill\cr}
\def\hs{\hbox to 3mm{}}
\def\hhs{\hbox to 5cm{}}
\def\btu{\bigtriangleup}
\def\Box{\triangle}



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

\author{\sc G. H. E. Duchamp\footnote{Pri\`ere de signaler les erreurs \`a 
{\tt gd\_etu[at]yahoo.fr} en mettant {\sc Mada07} en objet.}}

\title{Exercices accompagnant le cours de ``Combinatoire algébrique, énumérative et fonctionnelle''.\\ 
Madacascar 2007-2008.}

\date{}
 
\begin{document}

\maketitle

\setcounter{section}{1}

\begin{exo}{\rm Une partition non-ordonnée $P$ d'un ensemble $X$ est une partie $P\subset
\mathfrak{P}(X)-\{\emptyset\}$\footnote{L'ensemble des parties de $X$ est noté 
$\mathfrak{P}(X)$ \cite{B_ST}.} (c'est un ensemble de blocs \cite{Comtet},
c'est à dire de parties non-vides de $X$) telle que
\begin{itemize}
    \item la réunion des blocs est $X$, soit
    $$\bigcup_{Y\in P}Y=X$$ 
    ($P$ est un recouvrement)
    \item $P$ est formé de parties disjointes deux à deux, soit
    $$(\forall\ Y_1,Y_2\in P)(Y_1\neq Y_2  \Longrightarrow Y_1\cap Y_2=\emptyset).$$
\end{itemize}

L'ensemble des partitions de $X$ en $k$ blocs est noté ici $\mathcal{S}(X,k)$. Son cardinal ne dépendant que  de celui de $X$, on pose $S_2(card(X),k)=card(\mathcal{S}(X,k))$ (nombre de Stirling de deuxième espèce).

\ss
1) Montrer que $\mathcal{S}(\emptyset,0)=\{\emptyset\}$ et $\mathcal{S}(\emptyset,k)=\emptyset$ si $k\neq 0$. En déduire les nombres $S_2(0,k)$.\\
2) Montrer que, pour $k\geq 1$, 
\begin{equation}\label{stirling_rec1}
S_2(n+1,k)=S_2(n,k-1)+kS_2(n,k).
\end{equation} 
{\small {\bf Indication.} Soit $X$ un ensemble à $n+1$ éléments et $x_0\in X$, définir une surjection  
$$
\mathcal{S}(X,k)\mapsto \mathcal{S}(X-\{x_0\},k)\cup \mathcal{S}(X-\{x_0\},k-1)
$$ 
en ``enlevant'' $x_0$ dans une partition. Analyser les fibres de cette surjection et conclure.}  

3) a) Montrer que, pour $n\geq 1$, $S_2(n,0)=0$.\\ 
b) Expliquez pourquoi la donnée des $S_2(n,0),\ S_2(0,k)$ (calculés précédemment) et de la récurrence \mref{stirling_rec1} permet de construire toute la matrice de Stirling $\big(S_2(n,k)\big)_{n,k\geq 0}$.\\
c) Montrer, \textit{avec les seules données du (b)}, que, pour tout $n$, $S_2(n,n)=1$ et $S_2(n,k)=0$ pour $k>n$.

4) Montrer que 
\begin{equation}\label{stirling_rec2}
S_2(n+1,k+1)=\sum_{j=0}^{n-k}\binomial{n}{j}S_2(n-j,k).
\end{equation} 
{\small {\bf Indication.} Même technique que ci-dessus, définir une bijection  
$$
\mathcal{S}(X,k+1)\mapsto \cup_{\{x_0\}\subset J\subset X} \mathcal{S}(X-J,k)
$$ 
cette fois en ``enlevant'' le bloc contenant $x_0$ dans une partition. Analyser l'image de cette bijection et conclure.}  

5) a) Soit $T=\sum_{n,k\geq 0}S_2(n,k) \frac{x^n}{n!}y^k$, la série génératrice mixte des nombres $S_2(n,k)$. Montrer, à l'aide de \mref{stirling_rec2} que 
\begin{equation}\label{stirling_diff1}
T\ e^x=\frac{1}{y}\frac{\partial}{\partial x}(T) 
\end{equation}  
b) En intégrant \mref{stirling_diff1} et en utilisant les conditions initiales, montrer que 
$$
T=e^{y(e^x-1)} \ .
$$
}
\end{exo}

\ss
\textbf{Familles sommables}\pointir

\ss
\begin{exo}
{\rm
Soit $F_n$ définie par $F_0=0,\ F_1=1,\ F_{n+2}=F_{n+1}+F_n$.\\
1) a) Montrer que 
$$
\sum_{n\geq 0}F_n z^n=\frac{z}{1-z-z^2}
$$
b) Montrer (avec soin) que la famille $\big(z(z+z^2)^n\big)_{n\geq 0}$ est sommable. Quelle est sa somme ? (justifiez)\\
2) a) Déduire de ce qui précède que, pour tout $n\in \N$ 
$$
F_n=\sum_{k\geq 0}\binomial{n-1-k}{k}
$$
b) Quel est le support de cette somme ? la réécrire avec les bornes les plus serrées possibles.  
}
\end{exo}
\begin{exo}
{\rm
Soit $M\in \C^{\N\times \N}$, une matrice infinie à coefficients complexes et $x,y$ deux indéterminées.\\
1) a) Montrer que la famille 
$$
\big(\big(\sum_{n\geq 0}M[n,k] x^n\big)y^k\big)_{k\geq 0}
$$
est sommable dans $\C[[x,y]]$.\\
b) De même montrer que  
$$
\big(\big(\sum_{k\geq 0}M[n,k] y^k\big)x^n\big)_{n\geq 0}
$$
est sommable dans $\C[[x,y]]$.\\
2) Montrer que 
$$
\sum_{n,k\geq 0}M[n,k]\ x^n\ y^k=\sum_{k\geq 0}\sum_{n\geq 0}M[n,k]\ x^n\ y^k=
\sum_{n\geq 0}\sum_{k\geq 0}M[n,k]\ x^n\ y^k
$$
3) Appliquer ces résultats pour montrer que, si l'on note $I(n,k)$ le nombre d'applications idempotentes $[1..n]\mapsto [1..n]$ qui ont $k$ points fixes, on a  
$$
\sum_{n,k\geq 0}I[n,k] \frac{x^n}{n!}\ y^k=e^{ye^x}
$$
}
\end{exo}
\begin{exo}
(``Tablettes de Chocolat'') Une tablette de chocolat sera ici un rectangle de $p\times q$ cases (largeur $p\geq 1$ et hauteur $q\geq 1$), elle est caractérisé par ces deux paramètres. Sa surface est $s=pq$ et son demi-périmètre sera $l=p+q-1$. On compte le nombre $a_{l,s}$ de tablettes de demi-périmètre $l$ (resp. surface $s$) donné et on considère la série génératrice 
\begin{equation}
	T:=\sum_{s, l\geq 1} a_{l,s}x^l y^s
\end{equation}
1) a) Montrer que, pour tous $l,s$, on a $a_{l,s}\leq 2$.\\
b) En déduire que la famille $(x^{p+q-1}y^{pq})_{p,q\geq 1}$ est sommable et de somme $T$.\\
2) Montrer que la famille
\begin{equation}
\Big(\frac{(xy)^q}{1-(xy^q)}\Big)_{q\geq 1} 	
\end{equation} 
est sommable dans $\C[[x,y]]$ et de somme $T$.\\
3) (Partie machine, intéressante à faire mais non exigible à l'examen).\\ 
a) Vérifier que Maple ne sait pas convertir la somme 
\begin{equation}
\sum_{q\geq 1}\frac{(xy)^q}{1-(xy^q)} 	
\end{equation} 
en une fonction standard.\\ 
b)Montrer que si l'on veut le terme $a_{l,s}$, il suffit de calculer la somme jusqu'à $q=s$. En désuire un algorithme de calcul de $a_{l,s}$.   
\end{exo}

%\tableofcontents
\begin{thebibliography}{ABC}
%
\bibitem{B_ST} {\sc Bourbaki, N.}, {\it Theorie des ensembles}, Hermann.
%
\bibitem{Comtet} {\sc Comtet, L.}, {\it Analyse Combinatoire}, PUF.
%
\end{thebibliography}
\end{document}