\documentclass{article}
\usepackage{titling}
\author{Laura \textsc{Gay} d'apr\`es Florien \textsc{Lemonnier}}
\include{preambule}

\newboxedtheorem{defi}{Définition}{compteur1}
\newboxedtheorem{prop}{Proposition}{compteur2}
\newboxedtheorem{lem}{Lemme}{}
\newboxedtheorem{coro}{Corollaire}{compteur3}
\newboxedtheorem{thm}{Théorème}{}
\newboxedtheorem{exe}{Exemple}{}


\renewenvironment{proof}[1][]{{\underline{\bfseries \proofname #1 :} }}{\hfill $\blacksquare$\\}
\usepackage{eurosym}

\begin{document}
\renewcommand{\proofname}{Preuve}
\begin{textblock*}{3cm}(10mm,12mm) 
\includegraphics[scale=0.10]{images/part.jpg} 
\end{textblock*}
\begin{spacing}{2}
\setlength {\shadowsize }{2pt}
\begin{center} \shadowbox{\begin{minipage}{15cm}
\centering     \begin{huge} 
\textsc{Partitions d'un entier en parts fixées}\end{huge}
\end{minipage}} \end{center}\end{spacing}
~\\



\underline{Référence :} \textsc{FGNan2} : exercice 3.15\\
\underline{Leçons :} 140, 243\footnote{Pour la leçon 243, il faut travailler avec des séries entières à la place des séries formelles. Leur rayon de convergence est systématiquement égal à 1 et les résultats obtenus sont valides pour $|z|<1$.}, 124, 126, 190, 230\\


\begin{thm}
Soient $a_1, \ldots, a_k \in \N^*$ premiers entre eux dans leur ensemble.\\
Pour $n \in \N^*$, on note $u_n = \text{Card} \left\{\left(x_1,\ldots,x_k\right) \in \N^k \middle| a_1x_1 + \ldots + a_kx_k = n\right\}$.\\
Alors on a : \[u_n \underset{n \rightarrow \infty}{\sim} \frac{1}{a_1 a_2 \ldots a_k} \frac{n^{k-1}}{(k-1)!} \]
\end{thm}
~\\
\begin{proof}
\begin{description}
\item[Étape 1 :] Considérons le produit de Cauchy\footnote{Le produit de Cauchy n'est pas trivial. Si on veut s'en convaincre on met $\sum \alpha_{\omega_i}X^{\omega_i}$ où $\alpha_{\omega_i}=0$ si $\omega_i$ n'est pas un multiple de $x_i$.}  des $k$ séries formelles $ \sum_{x_i=0}^\infty{X^{a_ix_i}}$, pour $i \in [\![1,k]\!]$.\\
      On note $f(X)$ ce produit de Cauchy ; on a les égalités suivantes :
			$$f(X) = \prod_{i=1}^k{\left(\sum_{x_i=0}^\infty{X^{a_ix_i}}\right)}= \sum_{n=0}^\infty{\left(\sum_{\substack{\left(x_1,\ldots,x_k\right) \in \N^k \\ a_1x_1+\ldots+a_kx_k=n}}{1}\right) X^n} = \sum_{n=0}^\infty{u_n X^n}$$
\item[Étape 2 :] Décomposons la fraction rationnelle $f(X)$ en éléments simples.\\
      La série formelle $f(X)$ est la série génératrice de la suite $\left(u_n\right)_{n \in \N}$. C'est une fraction rationnelle dont les pôles sont les racines $a_1^{\textrm{èmes}}$, \ldots, $a_k^{\textrm{èmes}}$ de l'unité car $f(X)= \prod_{i=1}^k{\frac{1}{1-X^{a_i}}}$.\\
			Le pôle $1$ est de multiplicité $k$.\\
			Regardons la multiplicité des autres pôles.\\
			Soit $\omega \neq 1$ un pôle de $f$. Comme $ \frac{1}{1-X^{a_i}}$, où $i \in [\![1,k]\!]$, n'a que des pôles simples, $\omega$ est de multiplicité inférieure ou égale à $k$. Par l'absurde, on suppose que $\omega$ soit un pôle de multiplicité $k$.\\
			On aurait alors : $\forall i \in [\![1,k]\!], \omega^{a_i} = 1$.\\
			Or, d'après le théorème de Bezout, les $\left(a_i\right)_{i \in [\![1,k]\!]}$ étant premiers entre eux dans leur ensemble :
			\[ \exists \left(u_1,\ldots,u_k\right) \in \Z^k, a_1u_1 + \ldots + a_ku_k = 1\]
			Alors $ \omega = \omega^{\sum\limits_{i=1}^k{a_iu_i}} = \prod_{i=1}^k{\left(\omega^{a_i}\right)^{u_i}} = 1$.\\
			Contradiction ! On en déduit donc que la multiplicité du pôle $\omega \neq 1$ est strictement inférieure à $k$.\\
			Notons $\mathcal{P} = \left\{\omega_1, \ldots, \omega_p\right\}$ l'ensemble des pôles de $f(X)$, avec $\omega_1 = 1$.\\
			Par décomposition en éléments simples, il existe $c_{i,j} \in \C$ pour $i \in [\![1,p]\!]$, $j \in [\![1,k-1]\!]$ et $\alpha \in \C$, tels que \footnote{On fait bien commencer la somme à $i=1$ car il n'y a pas que $(1-X)^k$ mais tous les $(1-X)^{``<k"}$} :
			\[f(X) = \frac{\alpha}{(1-X)^k} + \sum_{\substack{1 \leq i \leq p \\ 1 \leq j \leq k-1}}{\frac{c_{i,j}}{\left(\omega_i-X\right)^j}}\]
\item[Étape 3 :] Développons en série formelle les éléments simples de $f(X)$.\\
      En effet, pour $\omega \in \mathcal{P}$ et $j \in [\![1,k]\!]$, $ \frac{1}{(\omega-X)^j}$ est développable en série formelle. Ses coefficients s'obtiennent en dérivant $(j-1)$ fois le développement en série formelle de $ \frac{1}{\omega-X}$.\\
			On a : \[\frac{1}{\omega-X} = \frac{1}{\omega} \frac{1}{1-\frac{X}{\omega}}
			                            = \frac{1}{\omega} \sum_{n=0}^\infty{\left(\frac{X}{\omega}\right)^n}
																	= \sum_{n=0}^\infty{\frac{X^n}{\omega^{n+1}}}\]
			Puis, pour $j \in [\![1,k]\!]$, \[ \left(\frac{1}{\omega-X}\right)^{(j)}=\frac{(j-1)!}{(\omega-X)^j} = \sum_{n=j-1}^\infty{n (n-1) \ldots (n-j+2) \frac{X^{n-j+1}}{\omega^{n+1}}}\]
			Par conséquent, \[\frac{1}{(\omega-X)^j} = \sum_{n=j-1}^\infty{\frac{n!}{(j-1)! (n-j+1)!} \frac{X^{n-j+1}}{\omega^{n+1}}}
			                                         = \sum_{n=0}^\infty{\frac{(n+j-1)!}{(j-1)! n!} \frac{X^{n}}{\omega^{n+j}}}
																							 = \sum_{n=0}^\infty{\binom{n+j-1}{n} \frac{X^{n}}{\omega^{n+j}}} \]
		  Ainsi : \[f(X) = \alpha \sum_{n=0}^\infty{\binom{n+k-1}{n} X^n} 
			               + \sum_{\substack{1 \leq i \leq p \\ 1 \leq j \leq k-1}}{c_{i,j} \left(\sum_{n=0}^\infty{\binom{n+j-1}{n} \frac{X^{n}}{\omega^{n+j}}}\right)}\]
\item[Étape 4 :] Déduisons-en un équivalent de $u_n$ en l'infini.\\
      La dernière expression de $f(X)$ nous fournit, par unicité du développement en série formelle :
			\[u_n = \alpha \binom{n+k-1}{n} + \sum_{\substack{1 \leq i \leq p \\ 1 \leq j \leq k-1}}{c_{i,j} \binom{n+j-1}{n} \frac{1}{\omega^{n+j}}}\]
			Or, pour $r \in \N^*$, on a : $ \binom{n+r-1}{n} = \frac{(n+r-1) \ldots (n+1)}{(r-1)!} \underset{n \rightarrow \infty}{\sim} \frac{n^{r-1}}{(r-1)!}$.\\
			Ainsi, $ \alpha \binom{n+r-1}{n} \underset{n \rightarrow \infty}{\sim} \alpha \frac{n^{r-1}}{(r-1)!}$\\
			Et $ \forall i \in [\![1,p]\!], \forall j \in [\![1;k-1]\!], c_{i,j} \binom{n+j-1}{n} \frac{1}{\omega^{n+j}} = o\left(n^{k-1}\right)$, car les pôles de $\mathcal{P}$ sont des racines de l'unité, donc de module $1$.\\
			Par conséquent, \[u_n \underset{n \rightarrow \infty}{\sim} \alpha \frac{n^{k-1}}{(k-1)!}\]
			Reste à calculer $\alpha$.\\
			Pour cela, on multiplie $f(X)$ par $(1-X)^k$ et on substitue $1$ à $X$ :
			\begin{align*}
			(1-X)^k f(X) &= \prod_{i=1}^k{\frac{1-X}{1-X^{a_i}}} = \prod_{i=1}^k{\frac{1}{1+X+\ldots+X^{a_i-1}}} \\
			\alpha + 0 &= \prod_{i=1}^k{\frac{1}{a_i}}
			\end{align*}
			D'où : \[u_n \underset{n \rightarrow \infty}{\sim} \frac{1}{a_1 \ldots a_k} \frac{n^{k-1}}{(k-1)!}\]
\end{description}
\end{proof}


\hrulefill \\
~\\
\underline{Notes:}\\
~\\
\checkmark ~\textbf{A l'oral}, 13'04 en speedant\\
\checkmark ~Calculer le nombre de manières pour obtenir 100\euro ~en billets de 5, pièces de 1 et 2.\\



\end{document}