\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{fourier}
\usepackage[scaled=0.875]{helvet}
\usepackage{amsmath,amssymb,makeidx}
\usepackage[mathscr]{eucal}
\usepackage{eufrak}
\usepackage{fancybox}
\usepackage{graphicx}
\usepackage{tabularx}
\usepackage[normalem]{ulem}
\usepackage{pifont}
\usepackage{textcomp}
\newcommand{\euro}{\eurologo{}}
%Tapuscrit : Denis Vergès
\usepackage{pst-plot,pst-text}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\usepackage[left=3.5cm, right=3.5cm, top=3cm, bottom=3cm]{geometry}
\addtolength{\topmargin}{-1.59999pt}
\newcommand{\vect}[1]{\overrightarrow{\,\mathstrut#1\,}}
\renewcommand{\theenumi}{\textbf{\arabic{enumi}}}
\renewcommand{\labelenumi}{\textbf{\theenumi.}}
\renewcommand{\theenumii}{\textbf{\alph{enumii}}}
\renewcommand{\labelenumii}{\textbf{\theenumii.}}
\def\Oij{$\left(\text{O},~\vect{\imath},~\vect{\jmath}\right)$}
\def\Oijk{$\left(\text{O},~\vect{\imath},~ \vect{\jmath},~ \vect{k}\right)$}
\def\Ouv{$\left(\text{O},~\vect{u},~\vect{v}\right)$}
\usepackage{fancyhdr}
\usepackage[np]{numprint}
\setlength\parindent{0mm}
\usepackage[french]{babel}
\begin{document}
\lhead{\small CAPES externe}%
\lfoot{\small{}}
\rfoot{\small{mars 2010}}
\lfoot{\small{}}
%\renewcommand \footrulewidth{.2pt}%
\pagestyle{fancy}
\thispagestyle{empty}
\marginpar{\rotatebox{90}{\textbf{A. P. M. E. P.}}}

\begin{center}
{\Large \textbf{CAPES épreuve 2 session 2010}}

\bigskip
\textbf{Notations} \end{center}

\medskip

\begin{itemize}
\item[$\diamond$]  Dans tout le problème, $\mathbb{K}$ désigne $\R$ ou $\C$.  L'ensemble des suites d'éléments de $\mathbb{K}$ est
noté $\mathbb{K}^{\N}$. Une suite $\left(a_{n}\right)_{n\in \N}$ d'éléments de $\mathbb{K}$ sera noté plus simplement $\left(a_{n}\right)$. On note
$(0)$ la suite constante dont tous les termes sont nuls et on rappelle que deux suites $\left(a_{n}\right)$
et $\left(b_{n}\right)$ sont égales si et seulement si, pour tout entier $k \in \N$ on a $a_{k} = b_{k}$.

\item[$\diamond$]  Soient $\left(a_{n}\right)$ et $\left(b_{n}\right)$ deux éléments de $\mathbb{K}^{\N}$, on définit leur somme $\left(a_{n}\right) +\left(b_{n}\right)$, leur produit
$\left(a_{n}\right) \times  \left(b_{n}\right)$ et le produit d'une suite par un élément $\lambda \in \mathbb{K}$ respectivement par :

\setlength\parindent{5mm}
\begin{itemize}
\item[] $\left(a_{n}\right) +\left(b_{n}\right) = \left(a_{n} + b_{n}\right)$
\item[] $\left(a_{n}\right)  \times \left(b_{n}\right) =   \left(c_{n}\right)$ où, pour tout entier $n \in  \N : c_{n} = \sum_{k=0}^{n}
a_{k}b_{n-k}$

\item[] $\lambda \cdot \left(a_{n}\right) = \left(\lambda a_{n}\right)$
\end{itemize}
\setlength\parindent{0mm}

\item[$\diamond$]  On admet que $\left(\mathbb{K}^{\N}, +\right)$ est un groupe commutatif d'élément nul $(0)$.
\item[$\diamond$]  Pour tout $p \in \N$, on notera $X^p$ la suite $\left(x_{n}\right)  \in  \mathbb{K}^{\N}$ définie par :
\[\left\{\begin {array}{ l c l}
x_{p}& =& 1\\
x_{n} &=& 0~ \text{si}~ n \neq p
\end{array}\right.\]
On écrira aussi $X^0$ et $X^1$ respectivement $1$ et $X$.
\item[$\diamond$]  Pour tout $(k,~ n) \in \N^2$ tel que $0 \leqslant k \leqslant n$, le coefficient binomial $\binom{n}{k}$ est égal à $\dfrac{n!}
{k!(n - k)!}$.
\end{itemize}

\vspace{0,5cm}

\begin{center}
\textbf{Partie I  : série génératrice d'une suite} \boldmath $\left(a_{n}\right)$ \unboldmath
\end{center}

\medskip

\begin{enumerate}
\item  Propriétés algébriques
	\begin{enumerate}
		\item  Montrer que $\left(\mathbb{K}^{\N}, +, \times\right)$ est un anneau commutatif dont on précisera l'élément neutre.
		\item  Montrer que $\left(\mathbb{K}^{\N}, +, \times\right)$ est intègre. (Indication : \emph{si $\left(a_{n}\right)$ est un élément non nul de $\mathbb{K}^{\N}$, on pourra considérer le plus petit entier $k$ tel que $a_{k} \neq 0$.})
		\item  Montrer qu'un élément $\left(a_{n}\right)$ de $\mathbb{K}^{\N}$ est inversible dans $\mathbb{K}^{\N}$ si et seulement si $a_{0} \neq 0$.
		\item  Montrer que $\left(\mathbb{K}^{\N}, +, \cdot\right)$ est un $\mathbb{K}$-espace vectoriel.
 	\end{enumerate}
	
\medskip
		
Les résultats précédents montrent que toute suite $\left(a_{n}\right) \in  \mathbb{K}^{\N}$ peut s'écrire formellement sous la forme
$\displaystyle\sum_{n\geqslant 0} a_{n}X^n$. Lorsqu'on note $A(X) = \displaystyle\sum_{n\geqslant 0} a_{n}X^n$ ou $A = \sum_{n\geqslant 0} a_{n}X^n$, alors $A(X)$ ou $A$ sera appelée série génératrice de la suite $\left(a_{n}\right)$. On remarque que par définition du produit des suites on a $X^p \times X^q = X^{p+q}$ pour tout $(p,~ q) \in \N^2$. 

D'autre part, si $A$ est une série génératrice, pour tout entier $k \geqslant 2,~A^k$ désigne le produit
 $\underbrace{A \times A \times ... \times A}_{k~\text{facteurs}}$.

\medskip

\emph{On remarquera aussi que s'il existe un entier $p$ tel que $a_{p} \neq 0$ et tel que pour tout entier $n > p$ on a $a_{n} = 0$ alors la série génératrice de la suite $\left(a_{n}\right)$ n'est autre qu'un polynôme
de degré $p$ qu'on notera $\displaystyle\sum_{n=0}^p a_{n}X^n$.\\
D'après la question 1. c. ci-dessus, la série génératrice $\displaystyle\sum_{n \geqslant 0} a_{n}X^n$ est inversible si et seulement
si $a_{0} \neq 0$. Dans toute la suite, si la série génératrice $A(X)$ est inversible, on écrira son inverse sous la forme $\dfrac{1}{A(X)}$. Plus généralement si la série génératrice $A(X)$ est
inversible et si $B(X)$ est une série génératrice quelconque, le produit $B(X) \times \dfrac{1}{A(X)}$ sera noté $\dfrac{B(X)}{A(X)}$. Si de plus $B(X)$ et $A(X)$ sont des séries génératrices sous la forme de polynômes
alors $\dfrac{B(X)}{A(X)}$ peut être assimilée à une fraction rationnelle sur $\mathbb{K}$ et on admet que les techniques de décomposition en éléments simples sur $\mathbb{K}$ restent valables pour $\dfrac{B(X)}{A(X)}$}

\item \textbf{Éléments inversibles}

\medskip

	\begin{enumerate}
		\item  Montrer que la série génératrice inversible $\displaystyle\sum_{n \geqslant 0} X^n$ a pour inverse $1 - X$, c'est-à-dire
que :

\[\dfrac{1}{1 - X} = \sum_{n \geqslant 0} X^n\]
		\item  Soit $a \in  \mathbb{K} - \{0\}$, montrer que :
\[\dfrac{1}{1 - aX} = \sum_{n\geqslant 0} a^n X^n\]
		\item  Soient $a \in \mathbb{K} - \{0\}, b \in \mathbb{K} - \{0\}$ avec $a \neq b$, montrer que :
\[\dfrac{1}{(1 - aX)(1 - bX)} = \left(\dfrac{a}{a-b} \right)\dfrac{1}{1 - aX} + \left(\dfrac{b}{b - a} \right)\dfrac{1}{1 - bX}\]
 	\end{enumerate}
	
\item \textbf{L'opérateur de dérivation}

\medskip

L'opérateur de dérivation, $D : \mathbb{K}^{\N}  \to  \mathbb{K}^{\N}$ est défini par :
\[D : A = \sum_{n\geqslant 0}a_{n}X^n \mapsto D(A) = \sum_{n\geqslant 1}^{+ \infty}n a_{n}X^{n-1} = \sum_{n \geqslant 0}(n + 1)a_{n+1}X^n\]
	\begin{enumerate}
		\item  Montrer que $D$ est un endomorphisme du $\mathbb{K}$-espace vectoriel $\mathbb{K}^{\N}$.
		
Soient A et B deux séries génératrices. Montrer que :

		\item $D(A \times B) = D(A) \times B + A \times D(B)$.
(on pourra commencer par traiter le cas où $A = X^p$ et $B = X^q$ où $(p,~ q) \in \N^2$).
		\item  Si $B$ est inversible
\[D\left(\dfrac{A}{B} \right) = \dfrac{D(A) \times B - A \times D(B)}{B^2}\]
	\end{enumerate}
	
\item \textbf{Quelques exemples}

	\begin{enumerate}
		\item  Montrer que la suite $\left(a_{n}\right)_{n \in \N}$ dont la série génératrice est :
\[A(X) = \dfrac{1}{(1 - X)^2}\]
est définie pour tout entier $n$ par $a_{n} = n + 1$.
		\item  Montrer que, pour tout $p \in  \N$, la suite $\left(a_{p,~n}\right)_{n \in \N}$ dont la série génératrice est
\[A_{p}(X) = \dfrac{1}{(1 - X)^p}\]
est définie pour tout entier $n$ par :
\[a_{p,~n} = \binom{n+p - 1}{n}\]
		\item  Soit $A(X)$ la série génératrice d'une suite $\left(a_{n}\right)_{n \in \N}$. Montrer que $\dfrac{A(X)}{1 - X}$
est la série génératrice de la suite $\left(b_{n}\right)_{n \in \N}$ définie par :
\[b_{n} = \sum_{k=0}^n a_{k}\]
		\item  En déduire que, pour tout entier $p \in \N$ on a :
\[\sum_{k=0}^n \binom{k + p - 1}{k} = \binom{n + p}{n}\]
 	\end{enumerate}
\end{enumerate}
 
\vspace{0,5cm}

\begin{center}
\textbf{Partie II : séries génératrices et suites récurrentes}
\end{center}

\medskip

\begin{enumerate}
\item  On considère la suite $\left(a_{n}\right)_{n \in \N}$ définie par :
\[\left\{\begin{array}{l c l}
a_{0}& = &0\\
\multicolumn{3}{l}{\forall n \in \N,~ a_{n+1} = 2a_{n} + n}
\end{array}\right.\]

On se propose de déterminer la formule explicite de $a_{n}$ en fonction de $n$. On note $A(X)$ la série génératrice de la suite $\left(a_{n}\right)_{n \in \N}$.
	\begin{enumerate}
		\item  Montrer que :
\[A(X) = 2X \times A(X) + X^2 \times \sum_{n\geqslant 0} (n + 1)X^n\]
		\item  Déterminer la décomposition en éléments simples sur $\mathbb{K}$ de la fraction rationnelle
\[\dfrac{X^2}{(1 - X)^2 (1 - 2X)}\]
		\item En déduire l'expression de $a_{n}$ en fonction de $n$.
	\end{enumerate}
\item On considère la suite de Fibonacci $\left(F_{n}\right)_{n\in \N}$ définie par :
\[\left\{\begin{array}{l c l}
F_{0}& =& 0\\
F_{1}& =& 1\\
\multicolumn{3}{l}{\forall n \in \N,~ F_{n+2} = F_{n+1} + F_{n}}
\end{array}\right.\]
et on note $F(X)$ la série génératrice de la suite $\left(F_{n}\right)_{n\in \N}$.
	\begin{enumerate}
		\item Montrer que :
		
\[F(X) = \dfrac{1}{\sqrt{5}}\left(\dfrac{1}{1 - \alpha_{1}X} - \dfrac{1}{1 - \alpha_{2}X} \right)\]

où
\[\alpha_{1} = \dfrac{1 + \sqrt{5}}{2} \quad \text{et}\quad \alpha_{2} = \dfrac{1 - \sqrt{5}}{2}\]

		\item En déduire l'expression de $F_{n}$ en fonction de $n$.
	\end{enumerate}
\item Suites récurrentes linéaires d'ordre $k \:(k \geqslant 1)$.
%\alpha_{1} = \dfrac{1 + \sqrt{5}}{2} \quad \text{et}\quad \alpha_{2} = \dfrac{1 - \sqrt{5}}{2}
\medskip

Soit $\left(a_{1},~ \ldots,~ a_{k}\right) \in \C^k$, avec $a_{k} \neq  0$. On considère l'ensemble $\mathcal{U}$ des suites complexes $\left(u_{n}\right)$
définies par la donnée de $\left(u_{0},~ \ldots,~ u_{k-1}\right) \in \C^k$ et par la relation de récurrence

\[\forall n \geqslant  k,~ u_{n} = a_{1}u_{n-1} + a_{2}u_{n-2} + \ldots + a_{k}u_{n-k}.\]
(\emph{On utilisera, sans le démontrer, le fait que $(\mathcal{U},~+,~\cdot)$ est un $\C$-espace vectoriel}).

Soit $\left(u_{n}\right) \in \mathcal{U}$. On note $S$ la série génératrice de $\left(u_{n}\right)$, et $(E)$ l'équation caractéristique
de $\left(u_{n}\right)$ :

\[z^k = a_{1}z^{k-1} + a_{2}z^{k-2} +\ldots + a_{k} \quad  (E)\]

	\begin{enumerate}
		\item Montrer que $\varphi : \left(u_{n}\right) \in \mathcal{U} \mapsto \left(u_{0},~ u_{1},~ \ldots,~ u_{k-1}\right)$ est un isomorphisme de $\mathcal{U}$ dans $\C^k$.
		\item  On pose $Q(X) = 1 - a_{1}X - \ldots - a_{k}X^k$ et $P(X) = Q(X) \times S(X)$. Montrer que $P(X)$ est un polynôme de degré au plus $k - 1$, à coefficients dans $\C$.
		\item On note $z_{1},~\ldots,~z_{p}$ les racines dans $\C$ de l'équation $(E)$ et $\alpha_{1},~\ldots,~\alpha_{p}$ les ordres de
multiplicité respectifs de $z_{1},~\ldots,~z_{p}$.

Montrer qu'il existe des nombres complexes 
$b_{i,~j},~1 \leqslant i \leqslant p,~1 \leqslant j \leqslant \alpha_{i}$ tels que :
\[\dfrac{P(X)}{Q(X)}= \sum_{i=1}^{p} \left(\sum_{j=1}^{\alpha_{i}}\dfrac{b_{i,~j}}{\left( X - 1/z_{i}\right)^j} \right)\]
		\item Montrer alors qu'il existe des polynômes $R_{1},~\ldots,~R_{p}$ tels que pour tout $n$
\[u_{n} = \sum_{i=1}^p R_{i}(n) z_{i}^n~ \text{o\`u}~\forall i,\: deg\left(R_{i} \right) < \alpha_{i}.\]

		\item On note $\mathcal{V}$ l'ensemble des suites $\left(v_{n}\right)$ dont le terme général s'écrit

$v_{n} = \displaystyle\sum_{i=1}^p P_{i}(n)z_{i}^n$ où pour tout $i \in \{1,~ 2,~\ldots,~p\},~ P_{i}$ est un polynôme tel que 

$deg \left(P_{i}\right) < \alpha_{i}$.

Démontrer que $(\mathcal{V},~+,~\cdot )$ est un $\C$-espace vectoriel dont la dimension vérifie l'inégalité
dim $\mathcal{V} \leqslant k$ et déduire que $\mathcal{V} = \mathcal{U}$.
	\end{enumerate}
\end{enumerate}

\vspace{0,5cm}

\begin{center}
\textbf{Partie III : Nombre de partitions d'un ensemble}
\end{center}

\medskip

Soient $k \geqslant 1$ un entier et $S$ un ensemble non vide, on dit que $\left\{S_{1},~ S_{2},~\ldots,~  S_{k}\right\}$ est une partition
de $S$ en $k$ classes si :


\[\left\{\begin{array}{l}
\forall i   \in \{1, \ldots, k\},~ S_{i} \neq \emptyset\\
\forall (i,~ j) \in  \{1, \ldots, k\}^2,~S_{i} \cap S_{j} = \emptyset~ \text{si}~ i \neq j\\
\displaystyle \bigcup_{i=1}^k S_{i} = S
\end{array}\right.\]

Pour tout entier $n \geqslant  1$ et tout entier $k \in \{1, \ldots, k\}$ on note $\left\{\genfrac{}{}{0pt}{}{n}{k} \right\}$ le nombre de partitions
d'un ensemble de cardinal $n$ en $k$ classes. On pose par convention :

\setlength\parindent{5mm}
\begin{itemize}
\item[$\diamond$]  pour tout entier $n \geqslant 1$ : $\left\{\genfrac{}{}{0pt}{}{n}{0} \right\} = 0$
\item[$\diamond$]  pour tout entier $k > n$ : $\left\{\genfrac{}{}{0pt}{}{n}{k}\right\} = 0$
\item[$\diamond$] $\left\{\genfrac{}{}{0pt}{}{0}{0}\right\} = 1$
\end{itemize}
\setlength\parindent{0mm}

\begin{enumerate}
\item  Donner toutes les partitions de l'ensemble $S = \{1,~ 2,~ 3,~ 4\}$ en 2 classes.

Cette question montre que $\left\{\genfrac{}{}{0pt}{}{4}{2}\right\} = 7$. On se propose dans ce qui suit de calculer $\left\{\genfrac{}{}{0pt}{}{n}{k}\right\}$
en fonction de $n$ et $k$.
\item  Montrer que, pour tout entier $n \geqslant 1$ on a :

\[\left\{\genfrac{}{}{0pt}{}{n}{k}\right\} = \left\{\genfrac{}{}{0pt}{}{n-1}{k-1}\right\}  + k\left\{\genfrac{}{}{0pt}{}{n - 1}{k}\right\}\]

(\emph{On fixera un élément $s \in S$ et on considèrera les partitions contenant le singleton $\{s\}$ et les partitions qui ne le contiennent pas}).

\item  On considère la série génératrice
\[A_{k}(X) = \sum_{n \geqslant 0} \left\{\genfrac{}{}{0pt}{}{n}{k}\right\}X^n\]
	\begin{enumerate}
		\item  Montrer que pour tout entier $k \geqslant 1$, on a :
\[A_{k}(X) = X \times A_{k-1}(X) + kX \times A_{k}(X)\]
		\item  En déduire que, pour tout entier $k \geqslant 1$, on a :
\[A_{k}(X) = \dfrac{X^k}{\Pi_{m=1}^{k}(1 - mX)}\]

		\item  Montrer que, pour tout entier $k \geqslant  1$, on a :
\[\dfrac{1}{\Pi_{m=1}^{k}(1 - mX)} = \sum_{r=1}^{k} \dfrac{\alpha_{r}}{1 - rX}\]

où, pour tout $r \in \{1,~\ldots,~k\},~\alpha_{r}  = (-1)^{k-r}\dfrac{r^{k-1}}{(r - 1)!(k - r)!}$.
		\item  En déduire que, pour tout entier $n \geqslant k$ :
		\[\left\{\genfrac{}{}{0pt}{}{n}{k}\right\} = \sum_{r=1}^k (-1)^{k - r}\dfrac{r^n}{r!(k - r)!}\]

	\end{enumerate}
\item Application : nombre de surjections

On considère un ensemble $E$ de cardinal $n$ et un ensemble $F$ de cardinal $p$ où $n$ et $p$ sont deux entiers strictement positifs. On se propose de calculer le nombre $S(n,~ p)$ de surjections de $E$ sur $F$.
	\begin{enumerate}
		\item  Que vaut $S(n,~ p)$ lorsque $p > n$ ?
		\item  Que vaut $S(n,~ n)$ ?
		\item  On suppose maintenant que $p \in \{1,~\ldots,~n\}$. Montrer que :
\[S(n,~ p) = p!\left\{\genfrac{}{}{0pt}{}{n}{p}\right\}\]
	\end{enumerate}
\end{enumerate}

\vspace{0,5cm}

\begin{center}
\textbf{Partie IV : Nombre de dérangements}
\end{center}

\medskip

Soit $n \in \N^{*}$. On note $\mathfrak{S}_{n}$ l'ensemble des permutations de $\{1,~ \ldots,~ n\}$.

Un dérangement de l'ensemble $\{1,~ \ldots,~ n\}$ est une permutation $\sigma \in \mathfrak S_n$ sans point fixe c'est-à-dire
telle que pour tout entier $i \in \{1,~ \ldots,~ n\},~ \sigma(i) \neq~i$. On note $d_{n}$ le nombre de dérangements
de l'ensemble $\{1,~ \ldots,~ n\}$.

On pose $d_{0} = 1$ et pour tout entier naturel $n,~ p_{n} = \dfrac{d_{n}}{n!}$.

\begin{enumerate}
\item  Calculer $d_{1},~ d_{2}$ et $d_{3}$.
\item  Pour $0 \leqslant  k \leqslant  n$, on note $B_{k}$ l'ensemble des permutations de $\mathfrak S_n$  ayant exactement $k$
points fixes.
	\begin{enumerate}
		\item  Montrer que le cardinal de $B_{k}$ vérifie l'égalité : Card $\left(B_{k}\right ) = \displaystyle\binom{n}{k}d_{n - k}$ et en déduire
que :
\[\sum_{k=0}^n \binom{n}{k}d_{n - k} = n!\]

		\item  Soit $P$ la série génératrice de la suite $\left(p_{n}\right)$. Montrer que
\[E(X) \times P(X) = \sum_{n \geqslant 0} X^n,~\text{o\`u}~ E(X) = \sum_{n \geqslant 0} \dfrac{1}{n!}X^n.\]
		\item  Déterminer la série génératrice inverse de $E(X)$.
		\item  En déduire que
\[d_{n} = n!\sum_{k=0}^n \dfrac{(-1)^k}{k!}\]
	\end{enumerate}
\end{enumerate}

\vspace{0,5cm}

\begin{center}
\textbf{Partie V : Nombres de Catalan}
\end{center}

\begin{enumerate}
\item  \textbf{Chemins de Dyck}

\medskip

Le plan est rapporté à un repère \Oij. Pour tout entier $n \geqslant 1$,  on appelle chemin de Dyck de longueur $2n$, toute suite $\left(s_{0},~ s_{1},~\ldots,~ s_{2n}\right)$ de points du plan dont les coordonnées sont des entiers positifs tels que $s_{0} = (0,~ 0),~ s_{2n} = (2n,~ 0)$ et, tels que, pour tout entier $k \in \{0,~ 1,~\ldots,~2n-1\},~ s_{k+1}$ est l'image de $s_{k}$ par la translation de vecteur $\vect{\imath} + \vect{\jmath}$ ou de vecteur $\vect{\imath} - \vect{\jmath}$.

Voici un chemin de Dyck de longueur 16.

\medskip

\psset{unit=0.7cm}
\begin{center}
\begin{pspicture}(0,-0.5)(16.5,5)
\psaxes[linewidth=1.5pt]{->}(0,0)(16.5,5)
\psgrid[gridlabels=0pt,subgriddiv=1,gridwidth=0.3pt](0,0)(16,5)
\psline[linewidth=1.25pt](0,0)(1,1)(2,2)(3,1)(4,2)(5,1)(6,0)(7,1)(8,2)(9,3)(10,2)(11,3)(12,2)(13,1)(14,0)(15,1)(16,0)
\psdots(0,0)(1,1)(2,2)(3,1)(4,2)(5,1)(6,0)(7,1)(8,2)(9,3)(10,2)(11,3)(12,2)(13,1)(14,0)(15,1)(16,0)
\end{pspicture}
\end{center}

On note $c_{n}$ le nombre de chemins de Dyck de longueur $2n$. Les nombres $c_{n}$ sont appelés \textbf{nombres de Catalan}. Pour tout chemin de Dyck $C = \left(s_{0},~ s_{1},~\ldots,~ s_{2n}\right)$ de
longueur $2n$ on note $k(C)$ le plus petit entier tel que $s_{k(C)}$ soit d'ordonnée nulle et d'abscisse non nulle.
	\begin{enumerate}
		\item  Justifier que $k(C)$ est un entier pair.
		\item  Montrer que le nombre de chemins de Dyck $C$ de longueur $2n$ tel que $k(C) = 2n$ est égal à $c_{n-1}$.
		\item  Montrer que le nombre de chemins de Dyck $C$ de longueur $2n$ tel que $k(C) = 2p$
avec $p \in  \{1,~\ldots,~n\}$  est égal à $c_{p-1}c_{n-p}$. (Par convention, on pose $c_{0} = 1$).
		\item  En déduire que la suite $\left(c_{n}\right)$ vérifie la relation de récurrence :
\[c_{n} = \sum_{j=1}^n c_{j-1}c_{n-j}.\]
 	\end{enumerate}
\item \textbf{Expression des nombres de Catalan}
	
\medskip

Soit $r$ un nombre rationnel positif. On définit les coefficients binomiaux généralisés par : 
\[\left\{\begin{array}{l c l}

\binom{r}{0}&=&1\\
\binom{r}{n}&=&\dfrac{\Pi_{k=0}^{n-1} (r - k)}{n!}~\text{pour tout entier}~ n \geqslant 1
\end{array} \right.\]

On admet qu'il existe une unique série génératrice $S(X) = \Sigma_{n \geqslant 0} s_{n}X^n$ telle que :

\[\left\{\begin{array}{l c l}
s_{0} &=&1\\
S(X)^2 &=& 1 - 4X
\end{array}\right.\]
et que cette série génératrice est donnée par :

\[S(X) = \sum_{n \geqslant 0} \binom{\frac{1}{2}}{n}(-4)^nX^n\]
	\begin{enumerate}
		\item  Montrer que :
\[S(X) = 1 - \sum_{n \geqslant 0} \dfrac{2}{n + 1}\binom{2n}{n}X^{n+1}\]

		\item  On pose
\[H(X) = \dfrac{1}{2}\left(1 -  S(X)\right)\]

Vérifier que $H(X) = X + (H(X))^2$.
	\end{enumerate}
\item Soit $C(X)$ la série génératrice de la suite $\left(c_{n}\right)$ des nombres de Catalan.
	\begin{enumerate}
		\item  Montrer que :
\[X \times C(X) = X + (X \times C(X))^2\]
		\item  En déduire que, pour tout entier $n$, on a :
\[c_{n} = \dfrac{1}{n + 1}\binom{2n}{n}\]

puis que, pour tout entier $n \geqslant 1$ on a :
\[c_{n} = \binom{2n}{n} - \binom{2n}{n - 1}.\]
 	\end{enumerate}
\end{enumerate}
\end{document}