\documentclass[a4paper,11pt]{article}
\usepackage[francais]{babel}
\usepackage[dvips]{graphics}
\usepackage{graphicx}
\usepackage[latin1]{inputenc}
%\usepackage{isolatin1}
\usepackage{amsmath}
\usepackage{amscd}
\usepackage{amstext}
\usepackage{amsbsy}
\usepackage{amsopn}
\usepackage{amsthm}
\usepackage{amsxtra}
\usepackage{upref}
\usepackage{euscript}
\usepackage{amssymb}
\usepackage{amsfonts}
%\usepackage{ulsy}
\usepackage[all]{xy}
\usepackage{enumerate} % pour avoir des enumerations plus evoluees
\usepackage{vmargin}
\usepackage{txfonts}
\usepackage{textcomp}
\usepackage{fontenc}
%\usepackage{marvosym}
% Idem pour avoir un beau symbole du si et seulement si
\def\NN{\ensuremath{\mathbb{N}}}
\def\ZZ{\ensuremath{\mathbb{Z}}}
\def\QQ{\ensuremath{\mathbb{Q}}}
\def\RR{\ensuremath{\mathbb{R}}}
\def\CC{\ensuremath{\mathbb{C}}}
\def\KK{\ensuremath{\mathbb{K}}}
%
\parindent=0pt
\setmarginsrb{2,5cm}{0,5cm}{2,5cm}{1,5cm}{16pt}{30pt}{16pt}{45pt}
%\setmarginsrb{1}{2}{3}{4}{5}{6}{7}{8} 
% {1} marge gauche, {2} est la marge en haut,{3} est la marge droite,{4} est la marge en bas, {5} fixe la hauteur de l'entête, {6} fixe la distance entre l'entête et le texte, {7} fixe la hauteur du pied de page, {8} fixe la hauteur entre le texte et le pied de page.
%
\date{}
%
\title{Exposé 3 : Coefficients binômiaux, dénombrement des combinaisons, formule du binôme. Applications}
%\author{Gwendal}
%
\newenvironment{pluslong}[2][]%
{\begin{flushleft}\textbf{#1} \textsc{#2\\} \textup}%
{\end{flushleft} }
%
%
\newenvironment{pluslong2}[2][]%
{\begin{flushleft}\textbf{#1} \textsc{#2} \textup}%
{\end{flushleft} }
%
\newenvironment{moyen}[1][]%
{\begin{flushleft}\textbf{#1\\} \textup}%
{\end{flushleft} }
%
\newenvironment{moyen2}[1][]%
{\begin{flushleft}\textbf{#1} \textup}%
{\end{flushleft} }
%
\newenvironment{court}%
{\begin{flushleft} \textup}%
{\end{flushleft} }
%
%
\newenvironment{preuve}[1][]%
{\begin{flushleft}\underline{preuve}\textup}%
{\qed\end{flushleft}}
%
\begin{document}
\maketitle
%\tableofcontents
% (table des matières)
%\newpage

\textbf{Prérequis}\footnotemark[1] :\\
-Notions d'ensemble fini\\
-Cardinal\\
-Définitions des $p$-arrangements d'un ensemble $\mathcal{A}$ de cardinal $n$\\
-Raisonnement par récurrence
%
\footnotetext[1]{L'exposé a été présenté à Bordeaux(1) en octobre 2004 par Blandine, corrigée par M.A, et a été tapé par Gwendal Haudebourg. Mise à jour le 31/07/2007}
%
\section{Combinaisons}

\begin{moyen}[Définition 1]
Soit $\mathcal{A}$ un ensemble fini. On appelle combinaison de $p$-éléments de $\mathcal{A}$ (ou $p$-combinaison) toute partie de $\mathcal{A}$ à $p$ éléments.\\
\textit{rq : la partie $\left\lbrace a,b \right\rbrace=$la partie $\left\lbrace b,a \right\rbrace$} 
\end{moyen}

\begin{moyen}[Théorème 1]
Le nombre de $p$-combinaisons d'un ensemble à $n$-éléments se note $C_{n}^{p}$ (ou $(n,p)$) et se lit "nombre de combinaisons de $p$ parmi $n$".\\
$C_{n}^{p}=\dfrac{n!}{p!(n-p)!}$
\end{moyen}

\begin{moyen}[preuve]
Soit $\mathcal{C}_{n}^{p}$ l'ensemble des $p$-combinaisons de $\mathcal{A}$, avec $card(\mathcal{A})=n$\\
Soit \textit{d l'ensemble des $p$-arrangements de $\mathcal{A}$}\\
$\vert d \vert=\dfrac{n!}{(n-p)!}$ ($\vert d \vert$ est souvent noté ${A_{n}^{p}}$; dans $\mathcal{A}$ l'ordre des éléments est indifférents). Or il y a $p!$ permutations possible des éléments d'un $p$-arrangement, d'où $C_{n}^{p}=\dfrac{\mathcal{A}}{p!}=\dfrac{n!}{p!(n-p)!}$\\

Remarque : $C_{n}^{p}=0$, $\forall p >n$ (nombre de parties à $p$ éléments parmi $n$, $p>n$ ? Aucune...)
\end{moyen}

\section{Coefficients binômiaux}

\begin{moyen}[Propriétés]
1) $C_{n}^{n}=C_{n}^{0}=1$\\
2) $C_{n}^{p}=C_{n}^{n-p}$\\
3) $C_{n}^{p}+C_{n}^{p+1}=C_{n+1}^{p+1}$ ie $C_{n}^{p}+C_{n}^{p-1}=C_{n+1}^{p}$ \\
4) $C_{n}^{p}=\frac{n}{p}C_{n-1}^{p-1}$
\end{moyen}

\begin{moyen}[preuve]
Soit en utilisant $C_{n}^{p}=\dfrac{n!}{p!(n-p)!}$, soit de manière plus naturelle : \\
1) Combien y a t-il de parties à $0$ éléments dans $n$-éléments ? Il y en a une seule (celle qui ne contient aucun éléments) d'où le résultat\\
2) A chaque fois que je choisis une partie à $p$-éléments, il lui correspond une partie à $n-p$ éléments.\\
3) Soit $E$, $\vert E \vert=n+1$, $a\in E$ fixé. Alors toute partie de $E$ à $p$ éléments est soit une partie de $E-\left\lbrace a\right\rbrace $ à $p$ éléments, soit $\left\lbrace a \right\rbrace\cup P$ où $\vert P \vert=p-1$ et $a \notin P$ 
\end{moyen}

remarque : La relation 3) fournit un moyen de calculer "de proche en proche" les coefficients $C_{n}^{p}$ permettant de construire le triangle de Pascal.

\begin{moyen}[Le triangle de Pascal]
Les nombres réels $C_{n}^{p}$ sont généralement présentés dans un tableau triangulaire où $n$ est l'indice de ligne et $p$ l'indice de colonne. Il se contruit de proche en proche grâce aux valeurs $C_{n}^{0}=C_{n}^{n}=1$ et grâce à la relation $C_{n}^{p}+C_{n}^{p+1}=C_{n}^{p+1}$. Ce tableau est appelé triangle de Pascal.
\end{moyen}


\begin{pluslong}[Théorème 2]{(Formule du binôme de Newton)}
Si $a$ et $b$ sont deux éléments qui commutent entres eux, alors $\forall n \in \NN$, on a : $$(a+b)^{n}=\sum_{k=0}^{n} C_{n}^{k}a^{k}b^{n-k}$$
\end{pluslong}

\begin{moyen}[preuve]
Soit par récurrence (mais pour cette preuve, il faut connaître la formule avant de la démontrer) : $n=0$ évident, on suppose la relation ci-dessus. Puis :
$$(a+b)^{n+1}=(\sum_{k=0}^{n} C_{n}^{k}a^{k}b^{n-k})(a+b)=(\sum_{k=0}^{n} C_{n}^{k}a^{k+1}b^{n-k})+(\sum_{k=0}^{n} C_{n}^{k}a^{k}b^{n-k+1})$$ $$=(\sum_{k=0}^{n-1} C_{n}^{k}a^{k+1}b^{n-k})+(\sum_{k=1}^{n} C_{n}^{k}a^{k}b^{n-k+1})+a^{n+1}+b^{n+1}$$ $$=(\sum_{k=0}^{n-1}( C_{n}^{k}+C_{n}^{k+1})a^{k+1}b^{n-k}+a^{n+1}+b^{n+1}=\sum_{k=0}^{n-1} C_{n}^{k}a^{k+1}b^{n-k}$$\\
Soit plus naturellement, par le dénombrement : \\
$(a+b)^{n}=(a+b)...(a+b)$ les termes du second membres sont de la forme $a^{k}b^{n-k}$ (\textit{si on prend $a$ $k$-fois, on prend nécessairement $b$ $n-k$ fois})\\
Le terme $a^{k}$ est choisi dans $k$ facteur parmi $n$ éléments, il y a $C_{k}^{n}$ façon de placer ces éléments, donc le second membre est $\sum_{k=0}^{n} C_{n}^{k}a^{k}b^{n-k}$. 
\end{moyen}

\section{Applications}

\subsection{Jeu de cartes}

\begin{moyen}
Soit un jeu de $32$ cartes. On appelle main un ensemble de $5$ cartes.\\
(i) Combien y a t-il de mains différentes ?\\ 
(ii) Combien y a t-il de mains à 3 coeurs et 2 trèfes ?\\
(iii) Combien y a t-il de mains à au moins 2 carreaux ?\\
(iv) Combien peut-on déterminer de mains de $5$ cartes contenant exactement $1$ roi et $2$ dames ?\\
Solutions : (i) $C_{32}^{5} (ii) C_{8}^{3}.C_{8}^{2}$ (iii) on passe par le complémentaire (avoir exactement 0 carreau ou exactement 1 carreau) : $C_{32}^{5}-(C_{8}^{0}.C_{24}^{5}+C_{8}^{1}.C_{24}^{4})$ (iv) $C_{4}^{1}.C_{4}^{2}.C_{24}^{2}=6624$ (\textit{32-8=24 les autres cartes examinées ne sont ni des rois, ni des dames...}).\\
\end{moyen}

\subsection{Pile de boulets}

\begin{moyen}
Combien existe t-il de boulets sphériques dans une pile de forme pyramidale, dont la base est un triangle équilatéral de $n$ boulets de côtés ?\\
solution : la base contient $1+2+...+n=\dfrac{n(n+1)}{2}=C_{n+1}^{2}$ donc  $C_{n+1}^{2}+C_{n}^{2}+...+C_{2}^{2}=C_{n+1}^{2}+C_{n+1}^{3}=C_{n+2}^{3}$ boulets. On a quand même besoin de (i) :
$$\sum_{k=p}^{n} C_{k}^{p}=C_{n+1}^{p+1}$$  
\end{moyen}

\begin{moyen2}[preuve de (i)] : on a $C_{n+1}^{p+1}=C_{n}^{p+1}+C_{n}^{p}$ $=C_{n-1}^{p+1}+C_{n-1}^{p}+C_{n}^{p}$ $=C_{n-2}^{p+1}+C_{n-2}^{p}+C_{n-1}^{p}+C_{n}^{p}$ $=...=\sum_{k=p}^{n} C_{k}^{p}$ (le faire proprement par récurrence).\\
\textit{on peut aussi le démontrer par le dénombrement (plus intuitif, mais pas évident...)}
\end{moyen2}

\subsection{Trigonométrie}

\begin{moyen2} : $\forall \in \NN$, $\cos(nx)$ peut s'écrire sous la forme de degré $n$ en $\cos(x)$.\\
\end{moyen2}

\textbf{preuve} : $\forall x \in \RR, \cos(nx)+i\sin(nx)=(\cos(x)+\sin(x))^{n}$ (formule de Moivre) $=\displaystyle\Sigma_{k=0}^{n}C_{n}^{k}(\cos(x))^{n-k}(i\sin(x))^{k}$ (formule du binôme) $=\displaystyle\Sigma_{k=0}^{n}C_{n}^{k}(\cos(x))^{n-k}(i)^{k}(\sin(x))^{k}$\\
En identifiant les parties réelles et imaginaires, on obtient : $\cos(nx)=\Sigma_{k=0}^{\left[ \frac{n}{2}\right] }C_{n}^{2k}(-1)^{2k}(\sin(x))^{2k}(\cos(x))^{n-2k}$ $=\Sigma_{k=0}^{\left[ \frac{n}{2}\right] }C_{n}^{2k}(-1)^{2k}(1-\cos(x))^{2k}(\cos(x))^{n-2k}$\\
Remarque : on a un résultat analogue pour la fonction $\sin$ 

\subsection{Inégalité de Bernouilli}

\begin{moyen}
Pour tout $x \in \RR_{+}$, $\forall \in \NN$, $(1+x)^{n}\geq 1+nx$
\end{moyen}

\textbf{preuve} : $(1+x)^{n}=\displaystyle\Sigma_{k=0}^{n}x^{k}=1+nx+...\geq 1+nx$ car $x\geq 0$

\subsection{Formule de Leibniz}

\begin{moyen}
 cf. leçon 75 : $(fg)^{n}=\displaystyle\Sigma_{k=0}^{n} C_{n}^{k}f^{(k)}g^{(n-k)}$
\end{moyen}

\subsection{Le petit théorème de Fermat}

\begin{moyen2}[Théorème] : soit $p$ un nombre premier. Alors $\forall a \in \NN$, $a^{p}\equiv\left[ p \right]$
\end{moyen2}

\textbf{preuve} : $C_{p}^{k}=\dfrac{p!}{(p-k)!k!}$ pour tout $k \in {0,...,p}$ et $kC_{p}^{k}=pC_{p-1}^{k-1}$ par (4), donc $p \vert kC_{p}^{k}$. Or $pgcd(p,k)=1$ pour $k<p$ donc $p \vert C_{p}^{k}$ (lemme de Gauss).\\
Montrons maintenant par récurrence le théorème de Fermat : \\
-pour $a=0$ ok\\
-supposons la propriété vraie jusqu'au rang $p$ (récurrence forte). Alors $(a+1)^{p}=\Sigma_{k=0}^{p}C_{p}^{k}a^{k}=1+a^{p}+C_{p}^{1}a+...+C_{p}^{p-1}a^{p-1}=(1+a^{p})\left[ p \right]$ (par l'HR, et car $p \vert C_{p}^{k}$) $=(1+a)\left[ p \right]$ (par l'hypothèse au rang $p$).\\
Donc la propriété est vraie au rang $p+1$. Donc par le théorème de récurrence, la propriété est vraie pour tout $a \in \NN$\\
Remarque : marche aussi pour $A \in \ZZ$
\section{Questions-Compléments}

\end{document}
