\documentclass[12pt] {article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{amsmath,amssymb,graphicx,multicol,mathrsfs, fancyhdr,enumerate,fourier,eurosym,enumerate,tabularx,variations,numprint} \usepackage[dvips]{color} \usepackage[tikz]{bclogo} \usepackage{pst-plot,pst-tree,pstricks,pst-node,pstricks-add,pst-math,pst-xkey,pst-eucl,colortbl,diagbox}\usepackage[francais]{babel} \everymath{\displaystyle} \usepackage[colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref} \textwidth 19cm \textheight 24cm \hoffset -1,4cm \voffset -3.7cm \oddsidemargin 0pt \renewcommand{\thesubsection}{\textcolor{red}{\Roman{subsection}}} \renewcommand{\thesubsubsection}{\textcolor{blue}{\Roman{subsection}}.\textcolor{blue}{\arabic{subsubsection}}} \pagestyle{fancy} % pour le pied de page central \cfoot{Page \thepage/\pageref{fin}} \begin{document} \begin{center}\section*{\textcolor{red}{Combinatoire et dénombrement}}\end{center} \tableofcontents \subsection*{\textcolor{blue}{Activité préparatoire A page 34}} \subsection{\textcolor{red}{Cardinaux des ensembles finis}} \subsubsection{\textcolor{blue}{Réunion et intersection}} \begin{bclogo}[couleur = cyan!20, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définitions}} Soit E un ensemble non vide.\\ $\text{Card }(\textbf{E})$ est le nombre d'éléments de E.\\ L' ensemble vide $\emptyset$ n'a pas d'élément.\\ $\text{Card }(\emptyset) = 0$. \end{bclogo}. \bigskip Exemple : si $E\{1~;~2~;~5\}$, $\text{Card (E)}=3$. \bigskip \begin{bclogo}[couleur = cyan!20, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définition}} Soient deux événements A et B. \begin{enumerate}[$\bullet$] \item On note $\text{A}\cap\text{B}$ l'intersection de A et de B, constituée des éventualités appartenant à A et à B. \item On note $\text{A}\cup\text{B}$ la réunion de A et de B, constituée des éventualités appartenant à A ou à B. \end{enumerate} \end{bclogo} \bigskip \begin{bclogo}[couleur = cyan!20, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définition}} Deux ensembles $A$ et $B$ sont disjoints si leur intersection est vide (aucun élément en commun).\\ On écrit $A \cap B=\emptyset$. \end{bclogo} \begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Propriété}} $\text{Card }(A \cup B)=\text{Card }(A)+\text{Card }(B)-\text{Card }\left(A \cap B\right)$ \end{bclogo} La justification vient du fait que quand on calcule $\text{Card }(A)+\text{Card }(B)$, on compte deux fois les éléments communs, donc les éléments de l'intersection. \begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Propriété}} Si $A$ et $B$ sont disjoints, $\text{Card }(A \cup B)=\text{Card }(A)+\text{Card }(B)$. \end{bclogo} \subsubsection{\textcolor{blue}{Produit cartésien d'ensembles}} \begin{bclogo}[couleur = cyan!20, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définitions}} Soient $A$ et $B$ deux ensembles non vides.\\ Le produit cartésien de $A$ et $B$; noté $A\times B$ (qui se lit A croix B) est l'ensemble des couples $(x~;~y)$ où $x$ appartient à $A$ et $y$ à $B$.\\ $A\times B=\left\{(x~;~y),~x\in A,~y\in B\right\}$ \end{bclogo} \bigskip \noindent \textbf{\textcolor{blue}{Exemple}} : \\ $A=\{1~;~2\}$ et $B=\{a~;~b~;~c\}$.\\ $A\times B=\{(1~;~a)~;~(1~;~b)~;~(1~;~c)~;~(2~;~a)(2~;~b)~;~(2~;~c)\}$ \bigskip \noindent \textbf{\textcolor{red}{Remarque}} : Les coordonnées cartésiennes d'un point s'écrivent sous la forme $(x~;~y)$, où $x\in\mathbb{R}$ et $y\in\mathbb{R}$.\\ On dit que $(x~;~y)$ appartient au produit cartésien $\mathbb{R}\times \mathbb{R}$, qu'on écrit $\mathbb{R}^2$ par analogie avec la notation puissance. \bigskip \noindent \textbf{\textcolor{red}{Remarque}} : si $A$ et $B$ sont deux ensembles distincts, $A\times B\neq B\times A$. \begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Théorème}} Soient $A$ et $B$ deux ensembles finis.\\ $\text{Card }(A\times B)=\text{Card }(A)\times \text{Card }B$. \end{bclogo} \noindent \textbf{\textcolor{red}{Démonstration}} :\\ il suffit de faire un arbre pour compter le nombre de couples possibles.\\ Si $n=\text{Card }(A)$, nous avons $n$ branches pour le choix du premier élément du couple.\\ Si $p=\text{Card }(B)$, de chaque branche tracée précédemment, il part $p$ branches correspondant au choix du deuxième élément. Nous avons donc $np$ branches au total. \bigskip \begin{bclogo}[couleur = cyan!20, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définition}} Soient $E_1$, $E_2$, $E_n$ n ensembles.\\ Le produit cartésien $E_1\times E_2\times \cdots\times E_n$ est l'ensemble des $n$- uplets de la forme $\left(a_1~;~a_2~;~\cdots a_n\right)$ où $a_i\in E_i$ pour $1\leqslant i\leqslant n$. \end{bclogo} \bigskip \begin{bclogo}[couleur = cyan!20, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définition}} Si $A$ est un ensemble non vide, on appelle $n$-uplet de $A$ un élément de $A^n$, donc de la forme \\ $\left(a_1~;~a_2~;~\cdots~;~a_n\right)$ où $a_i\in A$ pour tout $i$ avec $1\leqslant i\leqslant n$. \end{bclogo} \bigskip \noindent \textbf{\textcolor{red}{Vocabulaire}} : pour $n=2$, on parle de couple ; Pour $n>2$, on parle de triplet, quadruplet, quintuplet, sextuplet, ou plus généralement $n$-uplet. \bigskip \begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Propriété}} $\text{Card }\left(A^n\right)=\left[\text{Card }(A)\right]^n$. \end{bclogo} \textbf{\textcolor{blue}{Démonstration}} : se fait par récurrence. \bigskip \begin{enumerate}[$\bullet$] \item Le code PIN d'un téléphone portable est composé de quatre chiffres ; le nombre de codes possibles est $10^4=\numprint{10000}$. \item Un livre de recettes de cuisine propose 100 entrées, 100 plats et 100 desserts.\\ Le livre annonce un million de menus possibles. A-t-il raison ? Oui : le nombre de menus possibles est $\left(10^2\right)^3=10^6=\numprint{1000000}$. \end{enumerate} \subsection*{\textcolor{blue}{Activité B page 34}} \subsection{\textcolor{red}{\textcolor{red}{Arrangements et permutations}}} \subsubsection{\textcolor{blue}{Arrangements d'éléments d'un ensemble}} \begin{bclogo}[couleur = cyan!20, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définition}} Soit $n$ un entier naturel non nul.\\ On appelle factorielle $n$, notée $n!$ le nombre défini par $n!=1\times 2\times \cdots\times n$.\\ Par convention, on. pose $0!=1$ \end{bclogo} \bigskip On a donc : \\ $0!=1$ ; $1!=1$ ; $2!=1\times 2=2$ ; $3!=1\times 2\times 3=2!\times 3=6$\\ $4!=1\times 2\times 3\times 4=3!\times 4=24$ ; $5!=4!\times 5=120$ ; $6!=5!\times 6=720$ \bigskip \textbf{\textcolor{blue}{Remarque}} : il semble que les résultats successifs deviennent \og{}vite\fg{} grands.\\ Donner une valeur approchée de $68!$.\\ Même question avec $69!$ ; que se passe-t-il ? \bigskip \textbf{\textcolor{blue}{Remarque}} (hors programme) : la formule de Stirling donne une idée de la croissance de $n!$. \[\boxed{\textcolor{red}{\lim_{n\rightarrow +\infty}\dfrac{n!}{\sqrt{2\pi n}\left(\dfrac{n}{\mathrm{e}}\right)^n}=1}}\textbf{}\] Donc $n!$ a le même ordre de grandeur que $\sqrt{2\pi n}\left(\dfrac{n}{\mathrm{e}}\right)^n$ \begin{bclogo}[couleur = cyan!20, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définition}} Un arrangement de $p$ éléments d'un ensemble $E$ de $n$ éléments ($p\leqslant n$) est un $p$-uplet d'éléments \textbf{distincts} de $E$ (liste \textbf{\textcolor{red}{ordonnée}}). \end{bclogo} \bigskip Exemple : $E=\left\{a~;~b~;~c~;~d~;~e\right\}$.\\ Des arrangements de 3 éléments de $E$ sont par exemple :\\ $\left(a~;~b~;~c\right)$, $\left(b~;~a~;~c\right)$, $\left(c~;~a~;~b\right)$, $\left(a~;~c~;~e\right)$ \bigskip Ce qui seraint bien est de savoir cmbien il y a de tels arrangements. \bigskip \begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Propriété}} Le nombre d'arrangements de $p$ éléments d'un ensemble de $n$ éléments est :\\ $A_n^p=n(n-1)(n-2)\times \cdots\times (n-p+1)$.\\ \textbf{\textcolor{red}{Remarque}} : $A_n^p=\dfrac{n!}{(n-p)!}$ \end{bclogo} \bigskip \textbf{\textcolor{red}{Démonstration} :} On imagine un arbre donnant la liste de tous les arrangements possibles ; il faut alors compter le nombre de branches finales.\\ On peut imaginer un meuble avec $p$ tiroirs dans lesquels on veut ranger $p$ objets parmi $n$ (qu'on peut voir comme $(n-0)$).\\ On a $n$ choix possibles pour le premier objet ; ce premier objet étant choisi, il y a $(n-1)$ possibilités pour ce deuxième objet. Le nombre de choix possibles pour le troisième objet est $(n-2)$.\\ Le nombre de choix pour le $p$-ième emplacement est $n-(p-1)=n+p+1$ (puisque l'on a déjà choisi $p-1$ objets).\\ Par principe multiplicatif, on a bien : \[A_n^p=n(n-1)\times \cdots\times (n-p+1).\] \begin{enumerate}[$\bullet$] \item $n!=n(n+1)(n-2)(n-p+1)(n-p)(n-p-1)\times \cdots\times 2\times 1$ \item $(n-p)!=(n-p)(n-p-1)times \cdots\times 2\times 1$. \item On en déduit que $\dfrac{n!}{(n-p)!}=n(n-1)\times \cdots\times (n-p+1)=A_n^p$ \end{enumerate} \bigskip L'écriture avec les factorielles sert plutot pour des calculs théoriques et celle avec les produits dans des calculs \og{}à la main\fg{}. \bigskip \textbf{\textcolor{blue}{Exemples}} : \begin{enumerate} \item On considère une course de 17 chevaux ; on s'intéresse au tiercé, c'est-à-dire à l'ordre des trois premiers chevaux à l'arrivée.\\ Quelqu'un qui ne connaît rien aux chevaux et qui veut être sûr de toucher le tiercé dans l'ordre souhaite parier sur toutes les arrivées possibles.\\ Le nombre de \og{}tiercés\fg{} possibles est $A_{17}^3=17\times 16\times 15=\numprint{4080}$. \item Les affiliés d'un club doivent élire un président, un vice-président et un trésorier, parmi $n$ candidats.\\Sachant que tous les candidats se présentent à tous les postes, et que les fonctions sont non-cumulables, combien y a-t-il de possibilités : \begin{enumerate}[a)] \item Pour n = 3 ? \item Pour n = 6 ? \item Pour n = 10 ? \item Pour n = 101 ? \end{enumerate} \textbf{\textcolor{blue}{Solutions}} : on calcule $A_n^3=n(n-1)(n-2)$ pour les différentes valeurs de $n$ \end{enumerate} \subsection{\textcolor{red}{Combinaisons, coefficients binomiaux}} \subsubsection{\textcolor{blue}{Parties d'un ensemble fini}} \begin{bclogo}[couleur = cyan!20, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définition}} une partie d'un ensemble fini $E$ est un sous-ensemble de $E$. \end{bclogo} \bigskip \textbf{\textcolor{red}{Exemple}} : soit $E=\{1~;~2~;~3\}$.\\ \begin{enumerate}[$\bullet$] \item $\{1~;~3\}$, $\emptyset$ et $E$ sont des parties de $E$. \item L'ensemble des parties de $E$, qu'on note $\mathscr{P}(E)$ est : $P(E)=\{\emptyset~;~\{1\}~;~\{2\}~;~\{3\}~;~\{1~;~2\}~;~\{1~;~3\}~;~\{2~;~3\}~;~\{1~;~2~;~3\}\}$ \end{enumerate} \bigskip \begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Propriété}} Soit $E$ un ensemble de $n$ éléments.\\ Alors $\text{Card}(\mathscr{P}(E))=2^n$ \end{bclogo} \bigskip \textbf{\textcolor{red}{Démonstration}} : On veut déterminer une partie $A$ de $E$ ; à chaque élément de $E$, on associe le nombre 0 si cet élément n'appartient pas à $A$ et 1 s'il appartient à $A$.\\ Le nombre de parties de $\mathscr{P}(E)$ est donc le nombre de $n$-uplets de $E$, soit $2^n$. \bigskip Exemple : (cf. activité A page 34). Les vacanciers pouvaient choisir de 0 à 3 activités. L'ensemble des activités prises par un vacancier est donc un élément de $\mathscr{P}(E)$ où $E$ est l'ensemble des trois activités.\\ $\text{Card}(E)=3$, donc $\text{Card}\left(\mathscr{P}(E)\right)=2^3=8$. Il y a huit choix possibles pour chaque vacancier. \subsubsection{\textcolor{blue}{Combinaisons}} \begin{bclogo}[couleur = cyan!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définition}} Soit $E$ un ensemble de $n$ éléments ; oon appelle combinaison de $p$ éléments de $E$ tout sous-ensemble de $p$ éléments. On ne tient donc pas compte de l'ordre. \end{bclogo} \bigskip \textbf{\textcolor{blue}{Exemple : }} Soit $E=\left\{a~;~b~;~c~;~d\right\}$.\\ Une combinaison de 3 éléments est par exemple $\{a~;~b~;~d\}$. Le sous-ensemble \{b~;~a~;~d\} est le même puisque l'ordre ne compte pas. \newpage \subsubsection{\textcolor{blue}{Coefficient binomial}} \begin{bclogo}[couleur = cyan!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définition}} Soit $E$ un ensemble de $n$ éléments. On appelle coefficient binomial $\binom{n}{p}$ le nombre de combinaisons de $p$ éléments parmi les $n$ éléments de $E$. \end{bclogo} \bigskip \begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Propriété}} Pour $0\leqslant p\leqslant n$, $\binom{n}{p}=\dfrac{A_n^p}{p!}=\dfrac{n!}{p!(n-p)!}$ \end{bclogo} \bigskip \textbf{\textcolor{red}{Démonstration}} :\\ Chaque combinaison de $p$ éléments correspond à $p!$ arrangements de ces $p$ éléments.\\ On a donc $\binom{n}{p}\times p!=A_n^p$ donc $\binom{n}{p}=\dfrac{A_n^p}{p!}$.\\ On en déduit $\binom{n}{p}=\dfrac{n(n-1)\times \cdots (n-p+1)}{p(p-1)(p-2)\times \cdots \times 2\times 1}$. (avec $p$ facteurs au numérateur et $p$ facteurs au dénominateur). \bigskip Ainsi : $\binom{10}{3}=\dfrac{10\times 9\times 8}{3\times 2\times 1}=120$. \bigskip \textbf{\textcolor{blue}{Remarques}} : \begin{enumerate}[$\bullet$] \item $\binom{n}{p}$ est toujours un entier naturel. \item Par définition, si $p>n$, $\binom{n}{p}=0$ (on ne peut pasa voir de sous-esnemble plus grands que l'ensemble lui-même). \item $\binom{n}{0}=1$ (il n'y a qu'un ensemble vide). \item $\binom{n}{n}=1$(il n'y a qu'un sous-ensemble de $n$ éléments, $E$ lui-même.) \item $\binom{n}{1}=n$ (car il y a $n$ sous-ensembles possibles de 1 élément) \item De même: $\binom{n}{n-1}=1$ \item Les coefficients binomiaux et le nombre d'arrangements peut se calculer à la calculatrice. \end{enumerate} \newpage \noindent \textbf{\textcolor{red}{Exemples}} : \begin{enumerate} \item Dans un jeu de 52 cartes, le nombre de \og{}mains\fg{} de 5 cartes est $\binom{52}{5}$=\numprint{2598960}. \item Une grille contient les dix nombres entiers de 0 à 9 et et les six lettres de A à F.\\ On demande de choisir trois nombres et deux lettres.\\ Le nombre de combinaisons possibles de trois nombres est $\binom{10}{3}$ et celui de deux lettres est $\binom{6}{2}$.\\ Le nombre de choix possiobles est donc $\binom{10}{3}\times \binom{6}{2}=120\times 15=\numprint{1800}$.\\ Il y a donc \numprint{1800} grilles possibles. \end{enumerate} \bigskip \begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Propriétés}} \begin{enumerate}[$\bullet$] \item Soit $k\leqslant n$ ; alors $\binom{n}{k}=\binom{n}{n-k}$ \item Relation de Pascal : si $1\leqslant k\leqslant n-1$, $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$. \end{enumerate} \end{bclogo} \bigskip \textbf{\textcolor{blue}{Démonstration} }: \begin{enumerate}[$\bullet$] \item Par définition, $\binom{n}{k}$ est le nombre de sous-ensembles de $k$ éléments choisis parmi $n$.\\ Mais choisir $k$ éléments revient à choisir les $n-k$ éléments restants ; il y a donc autant de sous-ensembles à $n-k$ d'où $\binom{n}{k}=\binom{n}{n-k}$. \item On considère un ensemble de $n$ éléments dans lequel on privilégie un élement appelé $\alpha$.\\ $\binom{n}{k}$ est le nombre de sous-ensembles contenant $k$ éléments.\\ On les sépare en deux catégories : \begin{enumerate}[$\bullet$] \item ceux qui contiennent $\alpha$ : cela revient à choisir $k-1$ éléments parmi $n-1$ puisque $\alpha$ fait partie des $k$ éléments. Il y en a donc $\binom{n-1}{k-1}$. \item ceux qui ne contiennent pas $\alpha$ : cela revient à choisir $k$ éléments parmi $n-1$ puisque $\alpha$ ne fait pas partie des $k$ éléments à choisir. Il y en a donc $\binom{n-1}{k}$.\\ On a donc bien $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$. \end{enumerate} \end{enumerate} \newpage \subsubsection{\textcolor{blue}{Triangle de Pascal}} Nous avons déjà vu deux façons de calculer les coefficients binomiaux.\\ Le triangle de Pascal (basé sur la relation de Pascal) donne un moyen simple et rapide de calculer les coefficients binomiaux de proche en proche. \bigskip \begin{center} \begin{tabularx}{\linewidth}{|*{10}{>{\centering \arraybackslash}X|}} \hline \rowcolor{blue!20}\backslashbox{n}{p}&0&1&2&3&4&5&6&7&8\\ \hline \cellcolor{blue!20}0&\cellcolor{red!40}1&0&0&0&0&0&0&0&0\\ \hline \cellcolor{blue!20}1&1&\cellcolor{red!40}1&0&0&0&0&0&0&0\\ \hline \cellcolor{blue!20}2&1&2&\cellcolor{red!40}1&0&0&0&0&0&0\\ \hline \cellcolor{blue!20}3&1&3&3&\cellcolor{red!40}1&0&0&0&0&0\\ \hline \cellcolor{blue!20}4&1&\cellcolor{yellow!60}4&\cellcolor{yellow!60}6&4&\cellcolor{red!40}1&0&0&0&0\\ \hline \cellcolor{blue!20}5&1&5&\cellcolor{yellow!60}10&10&5&\cellcolor{red!40}1&0&0&0\\ \hline \cellcolor{blue!20}6&1&6&15&20&15&6&\cellcolor{red!40}1&0&0\\ \hline \cellcolor{blue!20}7&1&7&21&35&35&21&7&\cellcolor{red!40}1&0\\ \hline \cellcolor{blue!20}8&1&8&28&56&70&56&28&8&\cellcolor{red!40}1\\ \hline \end{tabularx} \end{center} Exemple : $\binom{5}{2}=\binom{4}{1}+\binom{4}{2}=4+6=10$ donc $\boxed{\textcolor{red}{\binom{5}{2}=10}}$. \bigskip \textbf{\textcolor{red}{Remarque}} : dans le triangle de Pascal, on remarque que la somme des coefficients binomiaux d'une même ligne est une puissance de 2 et vaut $2^n$. \begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Propriété}} Soit $n$ un entier naturel. $\sum_{k=0}^{k=n}\binom{n}{k}=2^n$. \end{bclogo} \bigskip \textbf{\textcolor{red}{Démonstration}} : Soit $E$ un ensemble à $n$ éléments..\\ Notons $a_k=\binom{n}{k}$ ; c'est le cardinal de l'ensemble $A_k$ des parties de $E$ constituées de $k$ éléments de $E$.\\ $\mathscr{P}(E)=A_0 \cup A_1 \cup \cdots \cup A_n$.\\ Alors $2^n=\text{Card}\left(\mathscr{P}(E)\right)=\text{Card}\left(A_0\right)+\text{Card}\left(A_1\right)+\cdots \text{Card}\left(A_n\right)=\sum_{k=0}^{k=n}\text{Card}\left(A_k\right)=\sum_{k=0}^{k=n}\binom{n}{k}$. \noindent \textbf{\textcolor{red}{Remarque}} : \\ Les \textbf{\textcolor{blue}{coefficients binomiaux}} apparaissent dans le développement du \textbf{\textcolor{blue}{binôme}} de Newton $(a+b)^n$.\\ $(a+b)^n=\binom{n}{0}a^nb^0+\binom{n}{1}a^{n-1}b^1+\cdots+\binom{n}{k}a^{n-k}b^k+\cdots+\binom{n}{n}a^0b^n$.\\ Par exemple : $\boxed{\textcolor{red}{(a+b)^3=a^3+3a^2b+3ab^2+b^3}}$. \bigskip De même : $\boxed{\textcolor{red}{(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4}}$. \bigskip Avec $a=b=1$, on retrouve le résultat précédent. \label{fin} \end{document}