Mathématiques pour l'informatique - CHAPITRE 5. Combinatoire

La combinatoire occupe une place centrale en informatique car elle traite directement des objets discrets qui constituent le cœur de cette discipline : ensembles finis, structures de données, graphes, configurations possibles d’un système. À la différence des mathématiques continues, où l’on s’intéresse à des variations progressives, l’informatique est confrontée à des espaces finis mais souvent extrêmement vastes, dont il faut comprendre la structure et la taille.

Dans ce contexte, une question fondamentale est celle du dénombrement : combien existe-t-il de configurations possibles d’un problème donné ? Cette question intervient de manière cruciale dans l’analyse des algorithmes. Elle permet d’évaluer la complexité d’une recherche exhaustive, d’anticiper les limites pratiques d’un calcul, ou encore de comparer différentes stratégies de résolution. Une croissance combinatoire rapide du nombre de cas rend souvent impossible toute exploration naïve.

La combinatoire joue également un rôle clé dans des domaines variés de l’informatique, tels que la cryptographie (où l’on évalue la difficulté d’une attaque en fonction du nombre de possibilités à explorer), la théorie des graphes, l’optimisation ou encore les probabilités discrètes. Elle fournit les outils nécessaires pour structurer, compter et analyser ces ensembles de possibilités.

Ainsi, au-delà de ses aspects techniques, la combinatoire permet de développer une intuition essentielle : celle de l’ordre de grandeur des phénomènes discrets. Elle met en évidence que, même dans des situations simples en apparence, le nombre de configurations peut croître très rapidement, ce qui impose de concevoir des méthodes de calcul adaptées.

Le paradoxe des anniversaires

Dans ce chapitre, nous allons étudier le paradoxe des anniversaires. Il s'agit d'un paradoxe au sens où la réponse au problème posé n'est pas celle à laquelle on pourrait s'attendre. Il ne s'agit pas d'un paradoxe logique, la réponse ne recèle aucune contradiction.

Pour préciser la question, on ne tient compte que du jour et du mois de naissance, pas de l'année ni des années bissextiles, on ne considère donc que les 365 jours. D'autre part, pour éviter toute ambiguïté, on ne cherche pas à trouver exactement deux étudiant(e)s né(e)s le même jour, mais s'il existe au moins deux étudiants nés le même jour dans cet amphithéâtre.

Les sondages réalisés auprès des étudiants pour estimer le nombre en question, aboutissent immanquablement à une majoration très nette de la valeur réelle. En effet, il y a $365$ jours dans l'année et il est tentant de penser qu'il faut beaucoup d'étudiant(e)s pour espérer en trouver deux né(e)s le même jour. Le nombre proposé le plus fréquemment est $182$. L'origine de cette réponse est sans doute liée au seuil de probabilité recherché $1/2$ et le nombre de jours dans une année, mais aucune justification sensée de cette estimation n'a jamais été proposée.

Nous ne ferons pas durer le suspens, le seuil est de $23$ étudiant(e)s et ce résultat peut paraître déconcertant, d'où le qualificatif de paradoxe au sens informel. Par conséquent, l'expérience est systématiquement menée grandeur nature avec les étudiant(e)s qui suivent ce cours. La réalité est bien sûr conforme au résultat.

L'objectif de ce chapitre est d'introduire les concepts mathématiques, pour beaucoup élémentaires, qui vont permettre de le prouver. Nous verrons également, afin de ne pas limiter la portée de cet exercice à un simple jeu récréatif, que ce (faux) paradoxe constitue un avertissement très sérieux lors de la conception de certains protocoles en cryptographie.

Ensembles finis et infinis

L'ensemble des entiers naturels

Comme son nom l'indique, l'ensemble des entiers naturels collecte les nombres qui nous semblent naturels, tout au moins depuis que les hommes se sont interrogés sur le dénombrement, l'ordre et l'infini. Dès que l'on sait compter, il n'est pas difficile d'extrapoler et de prendre conscience que l'énumération des nombres entiers pourrait durer éternellement, malgré la finitude de nos existences et du monde qui nous entoure.

Il a fallu patienter jusqu'au début du XX-ème siècle pour que l'ensemble des entiers naturels soit parfaitement caractérisé dans le cadre d'une théorie mathématique (la théorie ZF). C'est-à-dire, défini grâce à des propriétés intrinsèques qu'il est le seul à posséder une fois dépouillé de tout autre attribut que de sa relation d'ordre :

En mathématiques, l'existence d'un ensemble naturel est acquise grâce à un axiome de la théorie des ensembles, l'axiome de l'infini. C'est indubitablement l'ensemble séminal de cette théorie.

On démontre (en exercice), que si l'on se donne deux ensembles naturels, il existe toujours entre eux une unique bijection croissante telle que sa bijection réciproque est elle aussi croissante (on parle d'isomorphisme d'ensembles ordonnés, comme nous le verrons au chapitre VII). Ceci signifie que même si ces deux ensembles naturels ne sont pas à strictement parler égaux, ils sont jumeaux, rien ne les distingue du point de vue de leurs relations d'ordres respectives. Autrement dit, nous pouvons toujours identifier un ensemble naturel quelconque à l'un d'entre eux.

Soit $n\in\N$, la demi-droite $\rrbracket n,\,\rightarrow\llbracket$ n'est pas vide, sans quoi $n$ serait le plus grand élément de $\N$, ce qui est absurde d'après la propriété 3 d'un ensemble naturel. Donc $\rrbracket n,\rightarrow\llbracket$ admet un plus petit élément d'après la propriété 1 et on l'appelle le successeur^* Il s'agit bien sûr de l'entier naturel $n+1,$ mais nous n'avons pas encore défini l'addition à ce stade. de $n$ que l'on note $n^{+}.$ D'après la première propriété d'un ensemble naturel, $\N$ contient un plus petit élément, on le note $0$, son successeur $1$, etc. et c'est une façon d'achever l'identification de cet ensemble à l'ensemble des entiers naturels bien connu du lecteur. Dans la suite du cours, on notera $\N^*:=\N\setminus\{0\}$.

Il faut retenir que l'existence d'un successeur (resp. prédecesseur) n'est possible que grâce à la première (resp. deuxième) propriété d'un ensemble naturel.

Récurrences

Le principe de récurrence (ou induction) est intimement lié à la structure d'ordre sur l'ensemble des entiers naturels. Il est parfaitement illustré par les vidéos spectaculaires de circuits de dominos qui tombent en cascade.

Si l'on place correctement les dominos — i.e. si l'on s'assure qu'à toute position dans le circuit, la chute du domino qui s'y trouve fera tomber le suivant (hérédité) — et que l'on peut faire tomber le premier du circuit (l'initialisation), alors tous les dominos vont tomber à partir du premier.

Dans les différents théorèmes de récurrence qui vont suivre, $n^{+}$ sera bien sûr remplacé par $n+1$ une fois définie l'addition dans $\N$.

Pour démontrer que $P(n^{+})$ est vrai, nous aurons parfois besoin de supposer que $P(k)$ est vrai pour tous les entiers $k$ compris entre $a$ et $n$.

Dans ce cas, il suffit de faire tomber les trois premiers (les $k$ premiers) pour tous les faire tomber.

On peut également avoir besoin de démontrer une propriété pour un nombre fini de valeurs.

En guise d'exercice, le lecteur pourra énoncer et prouver le théorème de théorème de récurrence fini descendante où l'on fait tomber un nombre fini de dominos mais en partant du dernier.

Soit $n$ un entier naturel. Démontrez par récurrence que \begin{equation} \label{eq:sumcub} \sum_{k=1}^nk^3 = \left(\sum_{k=1}^n k\right)^2. \end{equation}

Démontrez par récurrence que pout tout entier naturel $n$, le nombre $3^{2n}-1$ est divisible par $8.$

On considère le prédicat $P(n)$ suivant : $3^{2n}-1$ est divisible par $8$. On a $P(0)$ puisque $0$ est divisible par tout entier naturel. D'autre part, \begin{align*} 3^{2(n+1)}-1&=9.3^{2n}-1\\ &=9({\color{#FF8}3^{2n}-1})+8 \end{align*} Mais d'après l'hypothèse de récurrence il existe un entier naturel $k$ tel que ${\color{#FF8}3^{2n}-1}={\color{#FF8}8k}$, donc \begin{align*} 3^{2(n+1)}-1&=9({\color{#FF8}8k})+8\\ &=8(9k+1) \end{align*} donc $3^{2(n+1)}-1$ est divisible par $8$ et $P(n+1)$ est vrai.

Démontrez par récurrence que pour tout entier naturel $n\geqslant 2$, $3^n+4^n\leqslant 5^n$.

On considère le prédicat $P(n)$ suivant : $3^n+4^n\leqslant 5^n$. On a l'identité bien connue des maçons $3^2+4^2=5^2$ donc $P(2)$ est vrai. D'autre part, \begin{align*} 3^{\color{#FF8}n+1}+4^{\color{#FF8}n+1}&=3.3^n+4.4^n\\ &\leqslant 5.3^n+5.4^n\\ &\leqslant 5(3^n+4^n)\\ &\leqslant 5.5^n\quad\text{d'après l'hypothèse de récurrence}\\ &\leqslant 5^{\color{#FF8}n+1} \end{align*} donc $P(n+1)$ est vrai.

Démontrez que le quotient d'un entier naturel impair et d'un entier naturel pair n'est jamais entier.

Soit $p$ un entier et $q=2k$ un entier pair. Considérons le quotient \[\frac{p}{2k}.\] Ce quotient est entier si et seulement si $2k\mid p$, ce qui équivaut à l'existence d'un entier naturel $l$ tel que $2kl=p$, et prouve que $p$ est pair. Par contraposition si $p$ est impair et $q$ pair alors le quotient $\frac{p}{q}$ n'est pas entier.

Soit $n\in\N\setminus\{0\}$. On définit la suite réelle $(H_n)_{n\in\N\setminus\{0\}}$ par \[H_n:=\sum_{k=1}^n\frac{1}{k}.\]

Démontrez par récurrence que pour $n\geqslant 2$, $H_n\not\in\N$ en montrant que $H_n$ est le quotient d'en entier naturel impair et d'un entier naturel pair (distinguez le cas où $n$ est pair et impair).

Considérons le prédicat le nombre $H_n$ est un quotient dont le numérateur est un entier naturel impair et le dénominateur est un entier naturel pair. On a $H_2=1+\frac{1}{2}=\frac{3}{2}$ donc $P(2)$ est vrai. Supposons tout d'abord que $n$ soit pair, soit $n=2m$. Alors \begin{equation*} H_{n+1} = H_n + \frac{1}{2m+1} \end{equation*} mais l'hypothèse de récurrence $P(n)$ nous permet d'écrire que ${\color{#88F}H_n}={\color{#88F}\frac{2u+1}{2v}}$, autrement dit \begin{align*} H_{n+1} &= {\color{#88F}\frac{2u+1}{2v}}+ \frac{1}{2m+1}\\ &= \frac{(2m+1)(2u+1)+2v}{2v.(2m+1)}\\ &= \frac{4mu+2m+2u+1+2v}{2v.(2m+1)}\\ &= \frac{2(2mu+m+u+v)+1}{2v.(2m+1)}\\ \end{align*} Donc $H_{n+1}$ est le quotient $\frac{2x+1}{2y}$ d'un nombre impair et d'un nombre pair qui n'est jamais entier.

Supposons à présent que $n$ soit impair, soit $n=2m-1$. Dans ce cas on regroupe les fractions dont les dénominateurs ont la même parité : \begin{align*} H_{n+1} &= H_n + \frac{1}{2m}\\ &= 1+\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} +\cdots +\frac{1}{2m-1} + \frac{1}{2m}\\ &=(1+\frac{1}{3}+\frac{1}{5}+\cdots+\frac{1}{2m-1}) + (\frac{1}{2}+ \frac{1}{4}+\cdots+ \frac{1}{2m} )\\ &=(1+\frac{1}{3}+\frac{1}{5}+\cdots+\frac{1}{2m-1}) + \frac{1}{2} (1+ \frac{1}{2}+\frac{1}{3}\cdots+ \frac{1}{m})\\ &=({\color{#FF8}1+\frac{1}{3}+\frac{1}{5}+\cdots+\frac{1}{2m-1}}) + \frac{1}{2} {\color{#88F}H_m} \end{align*} En réduisant au même dénominateur, la somme à gauche dans la dernière expression et en la notant $\color{#FF8}\frac{a}{2w+1}$ car le dénominateur est un produit de nombres impairs donc impair. Si on fait l'hypothèse de récurrence forte, on sait que ${\color{#88F}H_m}={\color{#88F}\frac{2u+1}{2v}}$ et donc \begin{align*} H_{n+1} &= {\color{#FF8}\frac{a}{2w+1}} + {\color{#88F} \frac{2u+1}{4v}}\\ H_{n+1} &= \frac{2av+(2u+1)(2w+1)}{4bv}\\ H_{n+1} &= \frac{2(av+2uw+u+w)+1}{2(2bv)}\\ \end{align*} Le numérateur est impair et le dénominateur est donc pair.

Démontrez par récurrence qu'une relation d'ordre total définie sur un ensemble fini est nécessairement un bon ordre.

Le prédicat $P(n)$ considéré est Une relation d'ordre total définie sur un ensemble fini de cardinal $n$ est un bon ordre. Pour un ensemble réduit à un élément, cet élément est le minimum et $P(1)$ est vrai. Considérons un ensemble totalement ordonné $(X,\preceq)$ de cardinal $n+1$ et notons $y$ l'un quelconque de ses éléments. L'ensemble $(X\setminus\{y\},\preceq)$ muni de l'ordre induit est totalement ordonné et de cardinal $n,$ l'hypothèse de récurrence nous permet d'affirmer qu'il admet un plus petit élément $m$ : \[\forall x\in X\setminus\{y\}\ \ m\preceq x.\] Mais comme $(X,\preceq)$ est totalement ordonné, on peut comparer $m$ à $y$, c'est-à-dire que l'on a \[(m\preceq y)\vee(y\preceq m).\] Par transitivité de $\preceq$, soit $m$ est le plus petit élément de $X$ soit c'est $y$, mais dans les deux cas $X$ admet un plus petit élément, il est donc bien ordonné.

Cardinaux

Dans toutes les activités scientifiques, compter, dénombrer, estimer des quantités sont des pratiques essentielles et en apparence anodines. Malheureusement dès que l'on manipule des ensembles infinis, la notion de quantité s'avère délicate à généraliser et notre intuition est passablement mise en défaut. Il est par exemple logique de penser qu'il y a deux fois plus d'entiers naturels que d'entiers naturels pairs, or ce n'est pas le cas en un certain sens qu'il faudra préciser.

Plutôt que de dire que deux ensembles ont la même taille parce qu'ils ont le même nombre d'éléments, ce qui n'a de sens que si ces ensembles sont finis, on considère que deux ensembles sont de même taille si l'on est capable d'apparier chaque élément du premier avec un unique élément du second et réciproquement, à la manière des couples durant le slow du bal de promo où chaque étudiant a sa cavalière et qu'aucun ne se morfond sur le banc de touche. Les deux approches sont bien sûr équivalentes quand les ensembles sont finis, mais l'appariement a l'avantage de prolonger le concept si les ensembles sont infinis.

Deux ensembles $X$ et $Y$ sont dits équipotents s'il existe une bijection de $X$ sur $Y.$ Dans ce cas, on note $X\approx Y$.

Le mot équipotent, contraction des mots latins equi (égal) et potent (puissant), signifie littéralement même puissance, au sens militaire du terme. L'équipotence est la bonne manière d'aborder la notion de cardinalité, elle permet de comparer la taille d'ensembles quand bien même on ne peut pas les dénombrer. L'équipotence définit une relation d'équivalence sur une famille d'ensembles.

Soit $n\in\N$, on note $[n]$ l'intervalle $\llbracket 1,\,n\rrbracket $ pour l'ordre naturel avec pour convention $[0]=\varnothing.$

Il suffit d'observer le diagramme sagittal d'une injection, d'une surjection et d'une bijection entre deux ensembles finis pour se convaincre de la justesse de la proposition suivante (cela ne constitue pas pour autant une preuve).

Soit $n$ et $m$ deux entiers naturels. Alors

Il existe une injection $f:[n]\inj [m]$ si et seulement si $n\leqslant m$,
Il existe une surjection $f:[n]\surj[m]$ si et seulement si $n\geqslant m$,
Il existe une bijection $f:{[n]}\bij{[m]}$ si et seulement si $n=m$.

1. La condition $n\leqslant m$ est suffisante pour avoir l'injectivité, en effet si $n\leqslant m$, l'injection canonique de $[n]$ dans $[m]$ fait l'affaire. Montrons qu'elle est nécessaire. Considérons le prédicat $P(n)$ pour tout $m\in\N$, s'il existe une injection de $[n]$ dans $[m]$ alors $n\leqslant m$. On a $P(0)$ car toute application dont l'ensemble de départ est vide est injective. Soit $m$ un entier quelconque et $f:[n+1]\inj [m]$ une injection. On vérifie aisément que l'application \begin{equation*} g:[n]\to[m]\setminus\{f(n+1)\} \end{equation*} définie par $g(x):=f(x)$ est une injection. D'autre part en renumérotant les éléments de l'ensemble $[m] \setminus\{f(n+1)\}$ à partir du trou laissé par $f(n+1)$ dans l'ensemble $[m]$ grâce à la bijection (à vérifier par le lecteur) $\sigma:[m] \setminus\{f(n+1)\}\to[m-1]$ définie par \begin{equation*} \sigma(i):=\begin{cases} f(i) & \text{si}\ f(i)\lt f(n+1),\\ f(i)-1 &\text{si}\ f(i) \geqslant f(n+1) \end{cases} \end{equation*} l'application $\sigma\circ g$ est une injection de $[n]$ dans $[m-1]$ et l'hypothèse de récurrence nous donne $n\leqslant m-1$ soit $n+1 \leqslant m$.

2. Supposons que $f:[n]\to[m] $ soit surjective. Par définition, pour tout entier $k\in\llbracket 1,\,m\rrbracket $ son image réciproque $f^{-1}(k)$ n'est pas vide, elle admet donc un plus petit élément $x_k$ d'après la première propriété d'un ensemble naturel. Ceci prouve que l'on définit bien une application $x:[m]\to[n]$ par \[ \forall k\in[m]\quad x_k:=\min f^{-1}(k). \] Elle est injective car si $x_k=x_l$ alors $f(x_k)=f(x_l)$ or $f(x_k)=k$ et $f(x_l)=l$. On applique alors le résultat précédent.

3. C'est la conséquence des deux premières propositions.

D'après la troisième assertion de la proposition ci-dessus, si un ensemble $X$ est en bijection avec deux ensembles ${[m]}$ et ${[n]},$ on a nécessairement $n=m$. En effet, en notant $f:X\bij{[n]}$ et $g:X\bij{[m]}$ ces deux bijections, la composée $g\circ f^{-1}$ définit une bijection de ${[n]}$ dans ${[m]}.$ Ceci légitime la définition suivante :

Soit $X$ un ensemble. S'il existe un entier $n$ tel que $\ab{1}{n}\approx X$, on dit que $X$ est fini de cardinal $n$, sinon il est dit infini.

Dans ce cours, le terme cardinal sera réservé aux ensembles finis. La définition des cardinaux infinis demande des développements que nous n'aborderons pas ici. Le cardinal d'un ensemble fini $X$ est noté indifféremment $\count{X}$, parfois $\#X$ chez les anglo-saxons, ou $\text{card}(X)$ en France.

Si la proposition précédente ne s'applique qu'aux ensembles finis, l'utilisation des injections/surjections/bijections permet de comparer les ensembles en toute généralité. Qu'ils soient finis ou non, on évite la comptabilité. On comprend intuitivement que si l'on dispose d'une injection $f:X\inj Y$ entre deux ensembles infinis $X$ et $Y$, alors $Y$ est au moins aussi gros que $X$, et inversement si $f:X\surj Y$ est une surjection..

Toute partie de $\N$ est finie si et seulement si elle est majorée.

Nous nous contenterons de donner ici les grandes lignes de la preuve, la rédaction est laissée en exercice. La condition est nécessaire : si $P$ est une partie finie de $\N$, par définition on peut numéroter ses éléments, i.e. $P=\{p_1,p_2,\ldots,p_n\}$. Nous allons trier $P$ dans l'ordre croissant. Pour cela, on définit inductivement les ensembles $P_j$ et les entiers $m_i$ par \begin{align*} P_{k}&:=\begin{cases} P_{k-1}\setminus\{m_{k-1}\}&\text{si}\ k \gt 1\\ P&\text{si}\ k=1 \end{cases}\\ m_k&:=\min P_k\quad\forall k\in{[n]} . \end{align*}

On cherche pour chaque $i$ le minimum de la partie $P_i$ (c'est l'algorithme du tri sélection). L'existence du minimum $m_k$ se prouve par récurrence finie sur le prédicat $P_k$ n'est pas vide pour pouvoir appliquer la première propriété des ensembles naturels. Pour chaque valeur de $i$ il existe un unique $j$ tel que $m_i=p_j$, on définit ainsi une bijection croissante $\sigma:{[n]} \rightarrow{[n]} $ (il s'agit d'une permutation) telle que $m_i=p_{\sigma(i)}$. Par conséquent $m_k$ est le plus grand élément de $P$ et donc un majorant de $P$.

La condition est suffisante. En effet, si $P$ est majorée on note $n$ le plus petit de ses majorants (il existe puisque l'ensemble des majorants de $P$ n'est pas vide). Si $P$ est vide, il n'y a rien à montrer, sinon d'après la deuxième propriété des ensembles naturels, ce plus petit majorant est le plus grand élément de $P$, on le note $p_1$. Cette fois on va chercher inductivement le plus grand élément $p_2$ de $P\setminus\{p_1\}$, etc. Ce procédé de construction doit s'arrêter avec une valeur $p_k$ sans quoi on prouverait que $P$ n'était pas une partie finie de $\N$. Nous aurons finalement exhibé une bijection entre un intervalle $\llbracket 1,\,k\rrbracket $ et $P$.

L'ensemble $\N$ est infini.

En effet si $\N$ était fini, il admettrait un majorant et la deuxième propriété d'un ensemble naturel impliquerait que $\N$ admettrait alors un plus grand élément, ce qui est en contradiction avec la troisième propriété d'un ensemble naturel.

Soit $X$ et $Y$ deux ensembles et $f:X\rightarrow Y$ une application. On démontre que :

Toute partie $A$ d'un ensemble fini $X$ est finie et $\count{A}\leqslant\count{X}$.
L'intersection d'une famille quelconque d'ensembles finis est fini,
Si $X$ est fini alors $\count{f(X)}\leqslant \count{X}$ avec égalité si et seulement si $f$ est injective.
Si $X$ est fini et $f$ surjective, alors $Y$ est fini et $\count{Y}\leqslant \count{X}$ avec égalité si et seulement si $f$ est bijective.
Si $f$ est injective et $f(X)$ est fini alors $X$ est fini et $\count{X}=\count{f(X)}$.

On déduit de ces résultats le théorème suivant, qui nous simplifie le travail quand on doit démontrer qu'une application est bijective :

Soit $X$ et $Y$ deux ensembles finis de même cardinal et $f:X\rightarrow Y$ une application. Alors les trois assertions suivantes sont équivalentes :

$f$ est injective,
$f$ est surjective,
$f$ est bijective.

L'addition est l'application $+:\N\times\N\rightarrow\N$ définie par \begin{equation} \label{def:loiadd} x+y:=\count{X\cup Y} \end{equation} où $X$ et $Y$ sont deux ensembles quelconques disjoints et de cardinaux respectifs $x$ et $y$.

On définit également le produit ou la multiplication comme l'application $\times:\N\times\N\rightarrow\N$ définie par \begin{equation} \label{def:loiprod} x\times y:=\count{X\times Y} \end{equation} mais cette fois les deux ensembles ne sont pas nécessairement disjoints.

Notons que nous avons écrit ces applications avec une notation infixe plutôt que préfixe, $x+y$ au lieu de $+(x,y)$. Nous verrons au chapitre VI consacré aux structures que ces applications constituent des lois de compositions internes sur l'ensemble $\N$ et nous étudierons leurs propriétés générales qui sont déjà bien connues du lecteur pour l'ensemble $\N$.

La relation binaire notée $\mid$ et définie sur $\N$ par \begin{equation} a\mid b\ \Leftrightarrow\ \exists c\in {\N}\ \ ac=b \end{equation} est une relation d'ordre appelée divisibilité.

Si $a\mid b$, on dit que $a$ divise $b$ ou que $a$ est un diviseur de $b$ ou encore que $b$ est un multiple de $a$. C'est une relation d'ordre partiel (cf. exercice).

Un nombre entier naturel est dit premier s'il admet exactement deux diviseurs.

D'après cette définition, le nombre entier $1$ n'est pas un nombre premier, il n'admet qu'un seul diviseur. Le plus petit nombre premier est donc l'entier naturel $2$ et c'est le seul qui soit pair. On définit le plus grand commun diviseur comme le plus grand entier qui divise à la fois $a$ et $b$, on le note à la manière d'un couple $(a,b)$ ou parfois $a\wedge b$, le contexte évitant toute confusion avec le connecteur logique de conjonction :

\[(a,b):=\text{max}\{k\in\N\such (k\mid a)\wedge(k\mid b)\}.\]

On définit le plus petit commun multiple de deux entiers $a$ et $b$, parfois noté $[a,b]$ ou encore $a\vee b$ :

\[ [a,b]:=\text{min}\left(\{ka\mid k\in\N\}\cap \{kb\mid k\in\N\}\right).\]

Si $(a,b)=1$, on dit que $a$ et $b$ sont premiers entre eux. Nous reviendrons en détail sur cette relation particulière et les interactions entre les deux lois additive et multiplicative dans le chapitre consacré à l'Arithmétique.

Un ensemble équipotent à $\N$ est dit dénombrable. Un ensemble fini ou dénombrable est dit au plus dénombrable.

Définissez l'ensemble des nombres premiers $\mathscr P$ en logique des prédicats.

Par exemple, \[{\mathscr P}:=\big\{n\in\N\such\#\{d\in[n]\such d\mid n\}=2\big\}\] ou plus proche de la définition du lycée \[{\mathscr P}:=\big\{n\in\N\such (n\geqslant 2)\wedge\big(\forall k\in\N\ \ (k\mid n)\then (k=1)\vee(k=n)\big)\big\}\]

Attention au vocabulaire ! En français dénombrable signifie que l'on est capable de compter les éléments, donc synonyme de fini, alors qu'en mathématiques un ensemble dénombrable est toujours infini. Le mot dénombrable signifie dans notre contexte que l'on peut énumérer. Ce qu'il faut absolument retenir c'est que l'on peut toujours numéroter les éléments d'un ensemble $X$ au plus dénombrable (fini ou dénombrable). S'il est fini, on peut le décrire avec $X=\{x_i\such i\in{[n]}\}$ et s'il est dénombrable avec $X=\{x_i\mid i\in\N\}$. Ce n'est que la stricte application des définitions. Dans les deux cas, $x$ est une application à valeur dans $X$ et on écrit $x_i$ au lieu de $x(i)$ pour décrire l'élément de $X$ dont le numéro est $i$.

Il existe des ensembles qui ne sont pas dénombrables. Un ensemble non dénombrable est tellement gros, que malgré l'infinité des nombres entiers, il n'y en a pas assez pour numéroter tous ses éléments. Un résultat très important dû à G. Cantor, est qu'aucun ensemble $X$ ne peut être équipotent à l'ensemble de ses parties ${\mathscr P}(X).$ Il n'existe donc aucune bijection entre $\N$ et l'ensemble de ses parties ${\mathscr P}(\N)$. Comme l'application $i:\N\to{\mathscr P}(\N)$ définie par $n\mapsto\{n\}$ est injective, il devient évident que ${\mathscr P}(\N)$ est plus gros que $\N$. Un autre ensemble bien connu et qui n'est pas dénombrable, est l'ensemble des nombres réels $\R$. Nous ne le démontrerons pas dans ce cours.

Un ensemble au plus dénombrable est dit discret, sinon il est dit continu.

Le terme discret qualifie plus généralement tout processus (au sens large) dans lequel le temps ou l'espace est indexé par un ensemble au plus dénombrable. Par exemple une horloge dont l'aiguille des secondes fait un bond à la position suivante à chaque seconde (processus discret) versus une horloge dont l'aiguille des secondes tourne continûment autour du cadran (processus continu).

Nous pouvons à présent illustrer ce que nous disions en introduction au sujet des ensembles infinis et de la nécessité de se méfier de nos intuitions. Prenons par exemple l'ensemble des entiers naturels pairs : \[P:=\{n\in\N \such \exists k\in\N\ \ n=2k\},\] (parfois noté $2\N$) et soit $f:\N\rightarrow P$ l'application définie par $f(n):=2n$. Elle est injective car \[ f(n)=f(m)\iff 2n=2m\iff n=m. \] Elle est surjective car tout élément $y\in P$ est pair ce qui signifie par définition qu'il existe un entier $k$ tel que $y=2k$, autrement dit $k$ est l'antécédent de $y$ que l'on cherchait. En conclusion, l'ensemble des entiers naturels pairs est équipotent à l'ensemble des entiers naturels, ce qui contredit l'idée informelle qu'il y a deux fois plus d'entiers que d'entiers pairs. C'est un résultat contre-intuitif puisque $P$ est strictement inclus dans $\N$ et leurs éléments sont pourtant en bijection.

Démontrez que les ensembles $\N$ et $\Z$ sont équipotents.

On considère par exemple l'application $f:\N\rightarrow\Z$ définie par \begin{equation*} f(n):=\begin{cases} k&\text{si}\ n=2k,\\ -(k+1)&\text{si}\ n=2k+1. \end{cases} \end{equation*} autrement dit les entiers pairs sont redéployés sur les entiers relatifs positifs et les entiers impairs sur les entiers relatifs négatifs.

L'application $f$ est injective : si $n$ et $m$ n'ont pas la même parité, alors leurs images n'ont pas le même signe; s'ils sont tous les deux pairs i.e. $n=2k$ et $m=2l$ alors $f(n)=k$ et $f(m)=l$, donc $f(n)=f(m)\Rightarrow n=m$ et s'ils sont tous les deux impairs, i.e. $n=2k+1$ et $m=2l+1$ alors $f(n)=f(m)\Rightarrow -(k+1)=-(l+1)$ donc $k=l$ et finalement $n=m$.

L'application est surjective : soit $k\in\Z$, si $k\geqslant 0$, alors l'entier $n:=2k$ est un antécédent de $k$ puisque $f(2k)=k$ et si $k\lt 0$ alors l'entier $-(2k+1)$ est un antécédent de $k$ puisque \begin{align*} f(-(2k+1))&=f(2{\color{#FF8}(-k-1)}+1)\\ &=-({\color{#FF8}(-k-1)}+1)\\ &=k. \end{align*}

L'ordre naturel et les preuves d'arrêt

Quand il s'agit de justifier formellement qu'une boucle se termine dans un programme informatique, par exemple une boucle while en Python :

n = int(input("n = "))
S = 0
while (n > 0) :
   S = S + n**2
   n = n - 1

c'est la première propriété de bon ordre de l'ensemble des entiers naturels que l'on invoque. En effet, on peut montrer en corollaire de cette propriété que

Il n'existe aucune suite strictement décroissante d'entiers naturels.

Par l'absurde, supposons que $(u_n)_{n\in\N}$ soit une suite d'entiers naturels strictement décroissante, autrement dit telle que \begin{equation} \label{eq:suiteU} \forall n\in n\quad u_{n+1} \lt u_n. \end{equation} Considérons l'ensemble $U:=\{u_n\such n\in\N\}$ des valeurs de cette suite. Cet ensemble est une partie non-vide de $\N$ qui admet par conséquent un plus petit élément $m$ d'après la première propriété des ensembles naturels. Il existe alors une valeur $k\in\N$ telle que $u_k=m$, mais on déduit de $(\ref{eq:suiteU})$ que $u_{k+1} \lt m,$ ce qui contredit le fait que $m$ est le plus petit élément de $U$.

On obtient symétriquement un résultat similaire pour les suites croissantes et qui s'appuie cette fois sur la deuxième propriété des ensembles naturels :

Il n'existe aucune suite d'entiers naturels strictement croissante et majorée.

Par l'absurde, supposons qu’il existe une suite strictement croissante d’entiers naturels $(u_n)_{n\in\N}$ qui soit majorée, c’est-à-dire telle que \begin{equation} \label{eq:suiteV} (\forall n\in\N\ \ u_{n+1} \gt u_n)\land (\exists m\in\N\ \ \forall n\in\N\ u_n \le m) \end{equation} Considérons l'ensemble $U := \{u_n \such n\in\N\}$ des valeurs de la suite. Cet ensemble est une partie non vide et majorée de $\N$ qui admet par conséquent un plus grand élément $m$ d’après la deuxième propriété des ensembles naturels. Il existe alors une valeur $k$ telle que $u_k = m$, mais on déduit de $(\ref{eq:suiteV})$ que $u_{k+1} > m$, ce qui contredit le fait que $m$ est le plus grand élément de $U$.

C'est ce corollaire qui permet, par exemple, de démontrer qu'on finira par sortir de la boucle while dans ce script Python :

n = 0
while (n < len(L)):
   print("n =", n)
   n = n + 1

On conclut cette section avec :

L'ensemble ordonné $(\N,\leqslant)$ est archimédien, c'est-à-dire satisfait la propriété suivante : \begin{equation} \forall (a,b)\in(\N^*\!\times\N)\ \ \exists n\in\N\quad na \gt b. \end{equation}

Si $a \gt b$ l'entier $n=1$ convient. Dans le cas contraire, on considère l'ensemble \[P:=\{ka\ \mid (k\in\N)\ \wedge\ (1\leqslant ka\leqslant b)\}.\] Cette partie de l'ensemble $\N$ n'est pas vide puisque $a\in P$ et elle est majorée par $b.$ D'après la deuxième propriété axiomatique de $\N$, la partie $P$ admet donc un plus grand élément $\kappa a$. Notons $n:=\text{succ}(\kappa)$, alors $\kappa a\lt na$ et par conséquent $na\not\in P$, soit $b\lt na.$

Cette propriété des entiers naturels est très utile, par exemple pour affirmer qu'on peut encadrer tout nombre réel $x$ entre deux valeurs entières consécutives : $n\leqslant x\lt n+1$, ou encore que pour tout réel $\varepsilon\gt 0$, il existe un entier naturel $n$ tel que $1/n\lt \varepsilon$, etc.

Analyse combinatoire

Produit cartésien

Il s'agit à présent d'étudier les cardinaux de certains ensembles finis. Cela va nous permettre (enfin) d'étudier le paradoxe des anniversaires. Plus généralement, calculer le cardinal d'ensembles est indispensable en probabilités discrètes. Nous admettrons les propositions les plus difficiles à démontrer.

La définition de la multiplication de deux entiers $n$ et $m$ justifie immédiatement la proposition suivante et fournit au passage l'explication de la notation du produit cartésien :

Soit $X$ et $Y$ deux ensembles finis. Alors \begin{equation} \label{eq:countXtimesY} \count{X\times Y}=\count{X}\times\count{Y}. \end{equation}

Un bar propose des boissons composées d'un liquide (eau, lait, thé) et d'un sirop (fraise, pêche, orange, citron, ananas, grenadine, cassis, pomme, poire).

Combien de boissons différentes le bar peut-il concevoir ?

On considère l'ensemble $L$ des liquides, de cardinal $3$ et l'ensemble $S$ des sirops de cardinal $9$. On modélise une boisson comme un couple du produit cartésien $L\times S$ dont le cardinal fournit le nombre de boissons différentes : $27=3\times 9$.

En itérant cette proposition $n-1$ fois, on obtient le corollaire

Soit $X$ le produit cartésien $X_1\times X_2\times\cdots\times X_n$ de $n$ ensembles finis. Alors \begin{equation} \label{eq:cardprodcart} \count{X}=\prod_{i=1}^n\count{X_i}. \end{equation}

On considère le prédicat $P(n)$ suivant : Le produit cartésien de $n$ ensembles finis $(X_i)_{i\in{[n]} }$ est un ensemble fini de cardinal $\prod_{i=1}^n\count{X_i}.$

Notons $\Pi_k:=\prod_{i=1}^kX_i$ le produit cartésien des ensembles $X_i$. D'après la proposition précédente, $\count{\Pi_2}=\count{X_1}.\count{X_2}$ donc $P(2)$ est vrai. Soit $k\in\llbracket 1,\,n\llbracket $. On a \begin{align*} \Pi_{k+1} &=\prod_{i=1}^{k+1}X_i\\ &=(\prod_{i=1}^{k}X_i)\times X_{k+1}\\ &=\Pi_k\times X_{k+1} \end{align*} D'après la proposition précédente, on en déduit que $\count{\Pi_{k+1}} = {\color{#FF8}\count{\Pi_k}}.\count{X_{k+1}}$ et l'hypothèse de récurrence ${\color{#FF8}\count{\Pi_{k}}} = {\color{#FF8}\prod_{i=1}^k\count{X_i}}$ nous permet de conclure que \begin{equation*} \count{\Pi_{k+1}}=\left({\color{#FF8}\prod_{i=1}^k\count{X_i}}\right).\count{X_{k+1}} = \prod_{i=1}^{k+1}\count{X_i}. \end{equation*} On a donc montré $P(k+1)$ et le théorème de récurrence finie achève la preuve.

La carte d'un restaurant propose $3$ entrées, $4$ plats et $4$ desserts.

Combien de menus différents constitués d'une entrée suivie d'un plat puis d'un dessert peut-il composer ?

Il faut tout d'abord modéliser le problème, c'est-à-dire trouver l'objet formel mathématique qui le représente le mieux possible. On note $E$, $P$ et $D$ les ensembles des entrées, plats et desserts de cardinaux $3$, $4$ et $4$ respectivement. Un menu peut-être représenté par un triplet $(e,p,d)\in E\times P\times D$, qui non seulement intègre les éléments constitutifs du menu mais également leur ordre d'apparition. Le nombre de menus différents est donc le cardinal de l'ensemble $E\times P\times D$ qui vaut $3\times4\times 4=48$ d'après le corollaire.

Autour des applications

Nous avons déjà rencontré la notation $Y^X$ pour désigner l'ensemble des applications d'un ensemble $X$ dans un ensemble $Y$, en voici la justification :

Soit $X$ et $Y$ deux ensembles finis. Alors \begin{equation} \label{eq:nbapplications} \count{Y^X}=\count{Y}^{|X|}. \end{equation}

Puisque $X$ est fini, notons $n$ son cardinal et posons $X=\{x_1,x_2,\ldots,x_n\}$ et $X_i:=\{x_i\}\times Y$. D'après $(\ref{eq:countXtimesY})$ on a \begin{align*} \forall i\in{[n]} \quad\count{X_i} &=\count{\{x_i\}\times Y}\\ &=\count{\{x_i\}}\times\count{Y}\\ &=\count{Y}. \end{align*} donc en appliquant l'identité $(\ref{eq:cardprodcart})$ du corollaire précédent, on en déduit que \[ \count{\prod_{i=1}^nX_i}=\count{Y}^n=\count{Y}^{\count{X}}. \]

Il ne reste plus qu'à montrer que $Y^X$ est équipotent à $\prod_{i=1}^nX_i$, il nous faut donc construire une bijection $\color{#FF8}s$ entre ces deux ensembles. Soit $f=(X,G,Y)$ une application de $X$ dans $Y$ de graphe $G$. Par définition d'une application, on a : \[ G=\left\{(x_i,f(x_i))\;\mid\; i\in{[n]}\right\}. \] On définit alors l'application ${\color{#FF8}s}:Y^X\rightarrow\prod_{i=1}^nX_i$ par \[ {\color{#FF8}s}(f)=(c_1,c_2,\ldots,c_n)\ \ \text{où}\ c_i:=(x_i,f(x_i)) \] L'application $s$ est évidemment injective, deux applications distinctes de $X$ dans $Y$ ont des graphes distincts, on associe donc bien deux $n$-uplets de couples distincts à des applications distinctes. Elle est également surjective car tout $n$-uplet $\big((x_1,y_1),\ldots,(x_n,y_n)\big)$ de $\prod_{i=1}^nX_i$ définit le graphe d'une application de $X$ dans $Y$.

Soit $X$ un ensemble fini, alors \begin{equation} \label{eq:cardparties} \count{{\mathscr P}(X)}=2^{\count{X}}. \end{equation}

Puisque $X$ est fini, notons $n$ son cardinal et posons $X=\{x_1,x_2,\ldots,x_n\}$. Montrons que l'ensemble ${\mathscr P}(X)$ est équipotent au produit cartésien $\{0,1\}^n$, il suffira alors d'appliquer $(\ref{eq:cardprodcart})$. On définit l'application $\chi:{\mathscr P}(X)\rightarrow \{0,1\}^n$ par \begin{equation} \label{eq:vecteurcaract} \chi(A):=({\mathbb 1}_A(x_1),{\mathbb 1}_A(x_2),\ldots,{\mathbb 1}_A(x_n)), \end{equation} où ${\mathbb 1}_A$ est la fonction indicatrice de la partie $A$. L'application $\chi$ est injective puisqu'à deux parties distinctes de $X$ elle associe deux $n$-uplets distincts. Elle est surjective puisqu'à un $n$-uplet $(b_1,b_2,\ldots,b_n)$ de $\{0,1\}^n$ on associe la partie $A:=\{x_i\mid b_i = 1\}$ de $X$.

Le $n$-uplet dans l'égalité $(\ref{eq:vecteurcaract})$ dans la démonstration de ce corollaire est appelé vecteur caractéristique de la partie $A$. C'est une représentation des parties d'un ensemble extrêmement utilisée en informatique, les vecteurs caractéristiques ne sont en effet ni plus ni moins que des séquences binaires que les processeurs des ordinateurs manipulent parfaitement. Ainsi les opérations ensemblistes sont particulèrement efficaces quand les ensembles sont codés sous cette forme.

Certains auteurs utilisent la notation $2^X$ pour désigner l'ensemble des parties d'un ensemble $X$, identifiant implicitement les parties de $X$ aux applications de $X$ dans l'ensemble $\{0,1\}$ (voir la construction des entiers naturels en théorie des ensembles par J. Von Neumann).

De combien de façons différentes peut-on colorier les $27$ pays de l'union européeenne sur une carte de géographie si l'on dispose de $5$ couleurs ?

En codant les pays à l'aide des entiers de l'intervalle ${[27]}$ et les couleurs par les entiers de l'intervalle ${[5]}$, choisir une couleur pour chacun des $27$ définit une application $c:{[27]}\rg{[5]}$, et il y en a $5^{27}$ différentes d'après (\ref{eq:nbapplications}).

Soit $(X_i)_{i\in I}$ une partition d'un ensemble fini $X.$ Alors les ensembles $I$ et $X_i$ sont finis et on a : \begin{equation} \label{eq:sommation} \count{X} = \sum_{i\in I}\count{X_i}. \end{equation}

Les $X_i$ sont finis car ce sont des parties d'un ensemble fini. L'application de $I$ dans ${\mathscr P}(X)$ définie par $i\mapsto X_i$ est injective car les ensembles $X_i$ sont deux-à-deux disjoints par définition d'une partition. D'autre part, ${\mathscr P}(X)$ est fini d'après $(\ref{eq:cardparties})$. On dispose donc d'une injection de $I$ dans un ensemble fini, donc $I$ est fini. La formule de sommation provient de la définition de l'addition dans $\N$ grâce à une récurrence finie (laissée au lecteur).

Soit $X$ et $Y$ deux ensembles finis distincts tels que $X\cap Y\neq\varnothing$.

Montrez que $|X\cup Y|=|X\setminus Y|+|Y\setminus X|+|X\cap Y|.$

Il suffit de montrer que les trois ensembles $X\setminus Y$, $Y\setminus X$ et $X\cap Y$ forment une partition de $X\cup Y$ et la formule de sommation permet de conclure. Les ensembles $X\setminus Y$, $Y\setminus X$ ne peuvent être vides puisque $X\neq Y$ et $X\cap Y\neq\varnothing$ par hypothèse. Montrons qu'ils sont deux-à-deux disjoints. Par l'absurde, supposons que $(X\setminus Y)\cap(Y\setminus X)\neq\varnothing$ et notons $x$ un élément de cette intersection. Comme $x\in X\setminus Y$ on a $(x\in X)\wedge(x\not\in Y)$ et ce qui est absurde puisque $x\in Y\setminus X$. D'autre part si $x\in X\cap Y$, il ne peut appartenir ni à $X\setminus Y$, ni à $Y\setminus X$ puisqu'il doit appartenir à $X$ et à $Y$. Reste à montrer que la réunion des trois ensembles est égale à $X\cup Y$. La preuve que leur réunion est incluse dans $X\cup Y$ est évidente, et si $x\in X\cup Y$ alors $(x\in X)\vee(x\in Y)$ ce qui est logiquement équivalent à \[\big((x\in X)\wedge(x\not\in Y)\big)\vee\big((x\in Y)\wedge(x\not\in X)\big)\vee\big((x\in X)\wedge(x\in Y)\big)\] qui exprime que $x$ appartient à l'un des trois ensembles.

La carte d'un restaurant propose $3$ entrées, $4$ plats et $4$ desserts (cf. cet exercice).

Combien de menus différents le client peut-il constituer si son menu ne contient pas nécessairement l'intégralité des trois éléments ?

On reprend le même modèle où $E$, $P$ et $D$ désignent les ensembles des entrées, plats et desserts de cardinaux respectifs $3$, $4$ et $4$. Si le client peut constituer son menu comme il l'entend, il contient un seul, [5~deux ou trois des éléments entrée, plat, dessert. Autrement dit, son menu est un élément de l'ensemble : \[({\color{#FF8}\underset{3}{E}\sqcup\underset{4}{P}\sqcup\underset{4}{D}})\sqcup{(\color{#88F}\underset{3\times4}{(E\times P)}\sqcup\underset{3\times4}{(E\times D)}\sqcup\underset{4\times4}{(P\times D)}})\sqcup({\color{darkgreen}\underset{3\times4\times 4}{E\times P\times D}}).\] et ces $7$ ensembles constituent une partition de l'ensemble des menus possibles, on peut donc en calculer le cardinal grâce à la formule de sommation : \[{\color{#FF8}3+4+4}+{\color{#88F}12+12+16}+{\color{darkgreen}48}=99.\]

Un moyen plus simple d'obtenir ce résultat consistait à rajouter l'entrée vide dans $E$, le plat vide dans $P$ et le dessert vide dans $D$, pour coder ces choix. Il y aurait ainsi $4\times 5\times 5=100$ menus possibles desquels il faut retirer le triplet constitué par les trois choix vides.

Soit $f$ une surjection entre deux ensembles finis $X$ et $Y$. S'il existe un entier $k$ tel que $\forall y\in Y\ \ \count{f^{-1}(\{y\})}=k$ alors \begin{equation} \count{X} = k\,\count{Y}. \end{equation}

On applique la formule de sommation à la partition associée à la relation d'équivalence définie sur $X$ par $f(x)=f(y)$.

Formalisez et démontrez le principe des tiroirs : si $n$ caleçons sont rangées dans $m$ tiroirs (peu importe dans quel ordre) avec $n \gt m$, un tiroir contient au moins $2$ caleçons.

On définit l'application factorielle de $\N$ dans $\N$ par

\begin{equation} n\mapsto\prod_{i=1}^ni = 1.2.3\ldots(n-1).n. \end{equation}

Cette application est notée de manière postfixe et sans parenthèses, $n!$ désigne l'image de l'entier $n$ pour cette application. Comme le produit d'une famille vide est égal à $1$, on a $0!=1$. La fonction exponentielle croît extrêmement rapidement, et même plus bien plus rapidement que la fonction exponentielle, i.e. $\displaystyle\lim_{n\rg +\infty}e^n/n\,!=0$. Par exemple $10!=3\,628\,800$ alors que $\text{exp}(10)\approx 22\,026$.

Soit $X$ et $Y$ deux ensembles finis de cardinaux $p:=\count{X}$ et $n:=\count{Y}$ tels que $0\leqslant p \leqslant n$. Le nombre d'injections de $X$ dans $Y$ est l'entier \begin{equation} \label{eq:nbinjections} \frac{n!}{(n-p)!} \end{equation}

Une injection de $X$ dans $Y$ est avant tout une application, et pour la construire, il est nécessaire d'associer une image $f(x)$ à chaque élément $x\in X$ en s'assurant que cette image n'est pas celle d'un autre élément de $X.$

Puisque $X$ est fini de cardinal $p$, par définition on peut numéroter ses éléments de $1$ à $p$, i.e. $X=\{x_1,x_2,\ldots,x_p\}$. Pour définir inductivement l'image de chacun des $x_i$ pour $i$ allant de $1$ à $p$ en assurant l'injectivité, il faut compter combien d'éléments dans $Y$ n'ont pas encore d'antécédents. Pour fixer une image à $x_1$, tous les éléments de $Y$ sont disponibles, il y a donc $n$ images possibles. À ce stade, il ne reste que $n-1$ images possibles pour $x_2$ et ceci pour chacun des $n$ choix de $x_1$ soit $n(n-1)$ images possibles pour $x_1$ et $x_2$.

On continue ce procédé constructif avec les $p-2$ éléments de $X$ restants pour obtenir \[n(n-1)(n-2)\cdots(n-(p-1))=\frac{n!}{(n-p)!}\]

Combien de codes secrets à quatre chiffres décimaux tous distincts peut-on créer ?

Il faut attribuer à chaque chiffre du code secret une valeur différente, ce qui revient à considérer une application injective $c:{[4]}\rg\ab{0}{9}$ (deux chiffres différents doivent avoir des valeurs différentes), soit $10!/6!=10\times 9\times 8\times 7=5040.$

Le nombre de bijections entre deux ensembles finis de même cardinal $n$ est égal à \begin{equation} n! \end{equation}

Une injection entre deux ensembles finis de même cardinal $n$ est une bijection d'après ce théorème. Il suffit donc de remplacer $p$ par $n$ dans $(\ref{eq:nbinjections})$ : \begin{equation*} \frac{n!}{(n-n)!}=n! \end{equation*}

Une bijection d'un ensemble fini sur lui-même s'appelle une permutation, une grande partie du prochain chapitre est consacrée à l'étude de ces bijections particulières.

De combien de façons différentes peut-on empiler 8 tee-shirts sur une étagère ?

On peut coder à la fois la position d'un tee-shirt sur la pile et un tee-shirt avec un entier de l'intervalle ${[8]}$, autrement dit les différentes façons d'empiler les tee-shirts est représenté par une bijection de l'ensemble ${[8]}$ sur lui-même et il est de cardinal $8!=40\,320.$

Autour du coefficient binomial

La suite logique du cours serait de calculer le nombre de surjections d'un ensemble fini $X$ dans un ensemble fini $Y$, mais c'est un résultat plus difficile à établir, il faut donc patienter un peu.

Soit $X$ un ensemble fini de cardinal $n$ et $p\in\llbracket 0,n \rrbracket$. On note ${\mathscr P}_p(X)$ l'ensemble des parties à $p$ éléments de $X$.

Soit $X$ un ensemble de cardinal $n$ et $p\in\N$ tel que $p\leqslant n.$ Alors \begin{equation} \label{coefbinomial} |{\mathscr P}_p(X)|=\frac{n!}{(n-p)!p!} \end{equation} Ce nombre est appelé coefficient binomial, on le note $\binom{n}{p}$.

La preuve qui va suivre n'est pas la plus directe ni la plus simple, mais elle met en œuvre les notions introduites dans les chapitres précédents et permet d'illustrer un mécanisme très général utilisé pour calculer le nombre d'éléments d'un ensemble : le mettre en bijection avec un autre ensemble dont le cardinal est connu ou plus facile à calculer.

Soit $f$ une injection de $[p] $ dans $X$, alors $P:=f([p] )$ est une partie finie de $X$ de cardinal $p$. Il suffit pour cela de vérifier que l'application $g:[p] \rightarrow P$ définie par $g(x):=f(x)$ qui coïncide avec $f$ sur $[p] $ est une bijection. Réciproquement, si $P$ est une partie de $X$ de cardinal $p$, alors par définition, il existe une bijection $\pi:[p] \rightarrow P$ et son prolongement sur $X$ est une injection de $[p] $ dans $X$. Notons ${\mathscr I}$ l'ensemble des injections de $[p] $ dans $X$ et $v:{\mathscr I}\rightarrow{\mathscr P}(X)$ l'application définie par $v(f)=f([p] )$. On vérifie que la relation binaire ${\mathscr R}$ définie sur l'ensemble ${\mathscr I}$ par $f\,{\mathscr R}\,g\Leftrightarrow f([p])=g([p] )$ est une relation d'équivalence. Autrement dit deux injections de la même classe d'équivalence fournissent la même partie à $p$ éléments de l'ensemble $X$. La décomposition canonique $\color{#FF8}\overline{v}$ de l'application $v$ est donc une bijection de l'ensemble quotient ${\mathscr I}/{\mathscr R}$ dans l'ensemble ${\mathscr P}_p(X)=v({\mathscr I})$ des parties à $p$ éléments de $X$ : \begin{equation} \begin{CD} {\mathscr I} @>{v}>> {\mathscr P}(X)\\ @V{\varphi}VV @AAjA \\ {{\mathscr I}/{\rel}} @>>{\color{#FF8}\overline{v}}> {\mathscr P}_p(X) \end{CD} \end{equation}

Il nous reste à dénombrer l'ensemble quotient ${\mathscr I}/{\mathscr R}$. On veut appliquer le principe des bergers à la surjection canonique $\varphi:{\mathscr I}\rightarrow{\mathscr I}/{\rel}$ pour montrer que \begin{align*} \count{{\mathscr I}}&=p!\count{{\mathscr I}/{\rel}}\\ &=p!\count{{\mathscr P}_p(X)} \end{align*} ce qui achèvera la preuve en appliquant $(\ref{eq:nbinjections})$. On vérifie que la surjection canonique $\varphi$ est compatible avec la relation ${\mathscr S}$ définie sur ${\mathscr I}$ par $f\,{\mathscr S}\,g$ si et seulement s'il existe une permutation $\sigma:[p]\to[p] $ telle que $g=f\circ\sigma$ et que toutes les classes d'équivalence ont le même cardinal $p!$ car l'application définie par $f\mapsto f\circ\sigma$ est injective puisque $\sigma$ est une bijection. L'image réciproque $\varphi^{-1}(\{\overline{f})\}$ d'un élément de ${{\mathscr I}/{\rel}}$ est la classe d'équivalence d'un de ses représentants pour la relation d'équivalence ${\mathscr S}$.

Une classe de $36$ étudiants veut élire un groupe de $4$ délégués.

Combien y-a-t-il de groupes de délégués possibles ?

Il faut choisir $4$ étudiants parmi $36$, il y a donc $\binom{36}{4}=58\,905$ groupes de représentants possibles. Attention ! on pourrait être tenté de calculer le nombre d'injections de ${[4]}$ dans ${[36]}$ puisqu'il faut choisir un étudiant différent pour chacun des $4$ postes de représentants possibles. En procédant ainsi, on tient compte de l'ordre dans lequel on les a choisis, en effet l'injection $(1,2,3,4)\mapsto(12,32,2,7)$ est différente de l'injection $(1,2,3,4)\mapsto(7,32,12,2)$ qui décrit pourtant le même groupe de représentants. Il faudrait donc diviser le résultat par le nombre de permutations possibles de ces $4$ valeurs, à savoir $4!$ et on retrouverait évidemment le coefficient binomial. Autrement dit une injection définit un quadruplet au lieu d'une partie à $4$ éléments et les $4!$ permutations des termes du quadruplet définissent la même partie.

Un mot de passe est une séquence de $8$ symboles choisis parmi les chiffres décimaux et les $26$ lettres de l'alphabet latin en majuscule ou en minuscule sachant qu'une majuscule est distinguée d'une minuscule.

Combien peut-on constituer de mots de passe différents qui respectent les quatre conditions suivantes ?

ses symboles sont tous différents.
il contient exactement deux chiffres.
il contient au moins deux majuscules.
il contient au moins une minuscule.

On commence par constituer tous les ensembles de $8$ symboles différents possibles. En effet par hypothèse, ils doivent tous être distincts. Chaque permutation des $8$ symboles de chaque ensemble définit un nouveau mot de passe, il y aura donc $8\,!$ mots de passes différents par ensemble. Pour constituer l'un de ces ensembles, il faut choisir :

deux chiffres, soit $\binom{10}{2}=45$ combinaisons.
deux majuscules soit $\binom{26}{2}=325$ combinaisons.
une minuscule, soit $\binom{26}{1}=26$ combinaisons.
trois symboles parmi les majuscules et les minuscules restantes uniquement puisque l'on ne peut plus rajouter de chiffres, soit $\binom{52-3}{3}=18\,424$ combinaisons.

Finalement on peut constituer \[8\,!\,(45\times 325\times 26\times 18\,424)=282\,470\,872\,320\,000\] mots de passe différents.

Les coefficients binomiaux sont très utilisés en combinatoire, à tel point qu'il existe des ouvrages spécifiquement consacrés à leur étude, il faut donc en connaître les propriétés élémentaires. Soit $p$ et $n$ deux entiers tels que $0\leqslant p\leqslant n$. On a

\begin{align} \label{id:comb1} \binom{n}{p}&=\binom{n}{n-p},\\ \label{id:comb2} \binom{n+1}{p+1}&=\binom{n}{p}+\binom{n}{p+1}. \end{align}

Démontrez les identités $(\ref{id:comb1})$ et $(\ref{id:comb2})$.

D'autre part,

\begin{equation} \label{eq:sommebinom} \sum_{p=0}^n\binom{n}{p}=2^n. \end{equation}

Ce dernier résultat s'obtient simplement. L'équipotence définit une relation d'équivalence sur l'ensemble ${\mathscr P}(X)$ et les $n+1$ classes d'équivalence sont constituées des parties ${\mathscr P}_p(X)$ de $X$ à $p$ éléments, $p\in\llbracket 0,\,n\rrbracket $ formant une partition de ${\mathscr P}(X)$. L'égalité $(\ref{eq:cardparties})$ et la formule de sommation permettent de conclure.

Soit $p$ et $n$ deux entiers naturel tels que $0\leqslant p\leqslant n$.

Démontrez que si $p\geqslant 1$ alors on a l'égalité suivante, appelée formule du pion \[p\binom{n}{p}=n\binom{n-1}{p-1}.\]

En déduire que \begin{equation*} \sum_{p=1}^np\binom{n}{p} = n2^{n-1}. \end{equation*}

On a \begin{align*} p\binom{n}{p} &=\frac{n!\;p}{(n-p)!\;p(p-1)!}\\ &=\frac{n(n-1)!}{(n-p)!\;(p-1)!}\\ &=n\frac{(n-1)!}{(n-1-(p-1))!\;(p-1)!}\\ &=n\binom{n-1}{p-1}. \end{align*}

Par conséquent \begin{align*} \sum_{p=1}^np\binom{n}{p} &=\sum_{p=1}^n n\binom{n-1}{p-1}\\ &=n\sum_{p=1}^n\binom{n-1}{p-1}\\ &=n2^{n-1}\quad\text{d'après (\ref{eq:sommebinom})} \end{align*}

Le Triangle de Pascal est une table à deux entrées qui contient à la ligne $n$ et à la colonne $p,$ le coefficient binomial $\binom{n}{p}$. La $n$-ème ligne contient donc les $n+1$ coefficients $\binom{n}{p}$ pour $p\in\llbracket 0,\,n\rrbracket $, ce qui explique la formation en triangle de ces nombres dans la table (il y a un coefficient de plus d'un eligne à la suivante). Il est construit ligne après ligne à l'aide d'un algorithme itératif qui s'appuie sur la formule $(\ref{id:comb2})$ : \begin{equation*} \begin{matrix} \ \ \ \text{ligne}~:\ \\ \text{colonne}~:\ \end{matrix} {\color{#FF8}\binom{n+1}{p+1}} ={\color{#88F}\binom{n}{p}}+{\color{#88F}\binom{n}{p+1}}. \end{equation*}

En effet, cette formule montre qu'en additionnant deux coefficients binomiaux côte à côte sur la ligne $n$, on obtient le coefficient binomial à la ligne suivante $n+1$ en-dessous du deuxième. Les valeurs $\binom{n}{0}=1$ et $\binom{n}{n}=1$ permettent d'initialiser les valeurs aux extrémités de chaque ligne. Vous pouvez observer la construction de ce triangle dans l'animation ci-dessous.

Quel est le plus grand entier $n$ pour lequel votre calculatrice est capable de calculer la factorielle de $n$ ? En quoi le triangle de Pascal permet-il de calculer plus efficacement des coefficients binomiaux que par la formule $(\ref{coefbinomial})$ ?

La formule ci-dessous fait apparaître les coefficients binomiaux dans le développement de $(x+y)^n$. Cette formule est valable dès que l'ensemble auquel appartiennent $x$ et $y$ est un anneau* Nous étudierons cette structure dans le chapitre consacré à l'arithmétique. et que ces deux éléments commutent.

Soit $n\in\N$ et soit $x$ et $y$ deux éléments d'un anneau qui commutent. Alors \begin{equation*} (x+y)^n = \sum_{p=0}^n\binom{n}{p}x^{n-p}y^{p}. \end{equation*}

Considérons le prédicat $P(n)$ définit par l'égalité ci-dessus. On a $P(0)$ puisque par convention $a^0=1$. Montrons que $\forall n\in\N$ , $P(n)=\Rightarrow P(n+1)$. On a \begin{align*} (x+y)^{n+1}&=(x+y)(x+y)^n\\ &=(x+y)\sum_{p=0}^n\binom{n}{p}x^{n-p}y^{p}\quad\text{hypothèse de récurrence}\\ &=\sum_{p=0}^n\binom{n}{p}x^{n-p+1}y^{p}+\sum_{p=0}^n\binom{n}{p}x^{n-p}y^{p+1}\\ &=x^{n+1}+\sum_{p=1}^n\binom{n}{p}x^{n-p+1}y^{p}+\sum_{p=0}^{n-1}\binom{n}{p}x^{n-p}y^{p+1}+y^{n+1}\\ &=x^{n+1}+\sum_{\color{#88F}p=0}^{\color{#88F}n-1}\binom{n}{\color{#88F}p+1}x^{\color{#88F}n-p}y^{\color{#88F}p+1}+\sum_{p=0}^{n-1}\binom{n}{p}x^{n-p}y^{p+1}+y^{n+1}\quad{\color{#88F}\text{réindexation}}\\ &=x^{n+1}+\sum_{p=0}^{n-1}\left(\binom{n}{p+1}+\binom{n}{p}\right)x^{n-p}y^{p+1}+y^{n+1}\\ &=x^{n+1}+\sum_{p=0}^{n-1}\binom{n+1}{p+1}x^{n-p}y^{p+1}+y^{n+1}\quad\text{d'après}\ (\ref{id:comb2})\\ &=x^{n+1}+\sum_{\color{#F84}p=1}^{\color{#F84}n}\binom{n+1}{\color{#F84}p}x^{\color{#F84}n+1-p}y^{\color{#F84}p}+y^{n+1}\quad{\color{#F84}\text{réindexation}}\\ \text{Finalement}\ \ (x+y)^{n+1}&=\sum_{p=0}^{n+1}\binom{n+1}{p}x^{n+1-p}y^{p}. \end{align*}

Savoir construire le triangle de Pascal permet de retrouver très rapidement les coefficients des différents termes de cette somme plutôt que d'apprendre par cœur les coefficients binomiaux.

Développez l'expression $(x-y)^6$. Soit $n$ un entier naturel, quels sont les coefficients du polynôme $P(X):=(1+X)^n$ une fois développé ?

On a \begin{align*} (x-y)^6 &=x^6+x^5(-y)^1+x^4(-y)^2+x^3(-y)^3+x^2(-y)^4+x(-y)^5+(-y)^6\\ &=x^6y+x^5y+x^4y^2-x^3y^3+x^2y^4+-xy^5+y^6. \end{align*} et \begin{align*} P(X)&=\sum_{p=0}^n\binom{n}{p}1^pX^{n-p}\\ &=\sum_{p=0}^n\binom{n}{p}X^{n-p}\\ &=\sum_{p=0}^n\binom{n}{p}X^{p}\quad\text{car}\ \binom{n}{p}=\binom{n}{n-p}.\\ \end{align*} Les coefficients du polynôme $P(X)$ sont donc les coefficients binomiaux.

Si l'on se donne deux ensembles $X$ et $Y$, le cardinal de leur réunion est égal à la somme de leurs cardinaux moins le nombre d'éléments qu'ils ont en commun, soit

\[\count{X\cup Y}=\count{X}+\count{Y}-\count{X\cap Y}.\]

Nous admettrons le théorème suivant qui généralise ce résultat.

Soit $(X_i)_{i\in{[n]}}$ une famille d'ensembles finis. Alors \begin{equation} \label{eq:somminout} \Big|\;\bigcup_{i=1}^{n}X_i\;\Big| = \sum_{k=1}^{n}(-1)^{k-1}{\color{#88F}\sum_{1\leqslant i_{1}\,<\,i_2\,<\,\cdots\,<\,i_{k}\leqslant n}}\left|X_{i_{1}}\cap X_{i_{2}}\cap \ldots \cap X_{i_{k}}\right| \end{equation}

La sommation de l'expression $(\ref{eq:somminout})$ se fait sur toute suite d'indices $(i_j)_{i\in\llbracket 1,\, k\rrbracket}$ strictement croissante et encadrée par les valeurs $1$ et $n$.

Paradoxe des anniversaires

Résolution

Nous avons à présent tous les outils pour analyser le paradoxe des anniversaires. La modélisation du problème passe par un encodage, c'est-à-dire une représentation des éléments concrets impliqués dans le problème à l'aide d'objets mathématiques abstraits. Il nous faut trouver un objet pour représenter les étudiants et un autre pour représenter les dates de naissance. Cette première phase est certainement aussi difficile à franchir que celle qui consiste à résoudre un problème mathématique déjà formulé de manière abstraite, tout au moins pour un débutant.

Comment coder un étudiant mathématiquement ? Quelle information le concernant doit-on garder dans notre modèle ? Comment va-t-on représenter une date d'anniversaire ? Si l'on calque directement l'expérience dans un amphithéâtre, on conserverait le nom, et éventuellement le prénom en cas d'homonymie* deux personnes distinctes doivent avoir des identifiants distincts, on veut donc une injection., des étudiants. Autrement dit, un étudiant serait naturellement codé par un couple $(p,n)$ constitué par son prénom et son nom, ces mots étant eux-mêmes codés par deux mots (des séquences) de lettres, i.e. d'éléments de l'alphabet (un ensemble fini) latin ${\mathscr A}=\{a,b,\ldots,z\}$. Une date de naissance serait représentée par le quantième du jour et le quantième du mois de naissance, autrement dit un couple $(j,m)\in[31]\times[12].$

C'est un modèle tout à fait convenable, mais il est inutilement détaillé pour aborder ce problème. En effet, le problème ne nécessite pas d'identifier les étudiants qui sont potentiellement nés le même jour, ni les autres d'ailleurs. D'autre part, les dates de naissance de ces éventuelles coïncidences ne sont pas exigées non plus. C'est le nombre d'étudiants dans l'amphithéâtre et le nombre de jours dans l'année qui sont déterminants. Il est donc plus pertinent de coder l'ensemble des étudiants par un ensemble fini à $n$ éléments, l'entier naturel $n$ désignant le nombre d'étudiants, et d'encoder la date de naissance par un entier naturel compris entre $1$ et $365$ en faisant abstraction des quantièmes.

On a donc, d'un côté l'ensemble des étudiants $X$ et de l'autre, l'ensemble des dates de naissance $Y\:={[365]}$. Si l'ensemble des étudiants est de cardinal $n$, par définition il est équipotent à l'ensemble $[n]$, autant supposer que $X=[n]$. Notons que si le problème demandait également d'identifier les étudiants, nous pourrions malgré tout coder $X:=[n]$, il suffirait de s'équiper d'une bijection entre $[n]$ et l'ensemble des couples $(p,n)$ des prénoms et des noms. C'est exactement ce que fait l'administration avec les numéros d'étudiants.

On a donc $X=[n]$ et $Y=[365]$. L'étudiant codé par un numéro $x$ est associé à sa date de naissance $y$ codée par le numéro $y\in Y$ du jour de l'année. Cette association constitue bien sûr une application $f:[n]\rightarrow {[365]}$. Avec ce modèle, dire qu'il n'existe pas d'étudiants nés le même jour se traduit par deux étudiants distincts ont des dates de naissances distinctes qui est la propriété caractéristique des applications injectives.

Il est impossible d'obtenir une injection $f:X\rightarrow Y$ entre deux ensembles finis $X$ et $Y$ si $\count{Y}\lt \count{X}$. Autrement dit, si l'amphithéâtre contient strictement plus de $365$ étudiants, il est inévitable que certains soient nés le même jour.

Résumons la situation. Un amphithéâtre particulier contenant $n$ étudiants définit une instance du problème, à savoir une application $f:[n]\rightarrow{[365]}$. Nous savons que si cette application est injective, tous les étudiants sont nés un jour différent. Sans même attendre l'étude des probabilités au prochain chapitre, si l'on se donne la taille $n$ d'un amphithéâtre et que l'on est capable de calculer le nombre d'applications injectives possibles — c'est-à-dire le nombre de façons d'attribuer $n$ dates de naissance de manière à ce que tous les étudiants soient nés un jour différent) — et le nombre total d'applications, le ratio $R_n$ de ces deux nombres fournit la probabilité qu'un amphithéâtre de $n$ étudiants ne contiennent jamais deux étudiants nés le même jour. Comme nous cherchons la probabilité de l'évènement complémentaire, à savoir la probabilité qu'il existe au moins deux étudiants nés le même jour, il ne reste alors qu'à trouver la plus petite valeur de $n$ telle que $1-R_n>\frac{1}{2},$ soit telle que $R_n<\frac{1}{2}$.

Le problème mathématique à résoudre est à présent cerné (nous reviendrons plus bas sur la pertinence de notre modélisation) :

Trouver le plus petit entier naturel $n$ tel que le rapport entre le nombre d'injections et le nombre d'applications d'un ensemble à $n$ éléments dans un ensemble à $365$ éléments est inférieur à $\frac{1}{2}.$

Si l'on note $X\hookrightarrow Y$ l'ensemble des injections d'un ensemble $X$ dans un ensemble $Y,$ l'entier en question est défini formellement de la manière suivante : \begin{equation} \min{\left\{{\color{white}n\in\N\mid \frac{{\color{#FF8}\#([n]\hookrightarrow{[365]})}}{{\color{#88F}\#{([365]}^{[n]})}}<\frac{1}{2}}\right\}}. \end{equation} Ce minimum existe puisque cet ensemble est une partie non-vide de $\N$, elle contient au moins les entiers strictement supérieurs à $365$, et admet donc un plus petit élément d'après la 1ère propriété caractéristique d'un ensemble naturel.

Revenons au calcul. La formule $(\ref{eq:nbapplications})$ nous fournit le nombre d'applications et la formule $(\ref{eq:nbinjections})$ le nombre d'injections entre deux ensembles finis. Il suffit de les appliquer pour obtenir le ratio attendu :

\begin{equation} \label{eq:RN} R_n:=\frac{\color{#FF8}\frac{365!}{(365-n)!}}{\color{#88F}365^n} =\frac{365\times364\times\cdots\times(365-(n-1))}{365^n}. \end{equation}

On cherche donc la plus petite valeur entière $n\leqslant 365$ telle que

\begin{equation} \label{ineq:anniv} \frac{365}{365}\times\frac{364}{365}\times\cdots\times\frac{(365-(n-1))}{365}\lt \frac{1}{2} \end{equation}

Il ne semble pas facile d'isoler la variable $n$ dans cette inégalité. On peut bien sûr éviter de se triturer les méninges en faisant travailler une machine qui calcule les différentes valeurs de $R_n$ jusqu'à ce que le seuil soit atteint. Par exemple avec ce petit script Python :

def R(n):
   P = 1
   for i in range(n):
      P = P * ((365 - i) / 365)
   return P

n = 2
while R(n) >= 0.5:
   n = n + 1
print("R(" + str(n) + ") = " + str(R(n)))

qui affiche

R(23) = 0.4927027656760144

L'algorithme proposé ci-dessus pour déterminer $n$ est très maladroit, on recalcule $R_n$ depuis le début à chaque fois, alors qu'on pourrait se contenter de ne faire qu'un produit supplémentaire à chaque étape. Modifiez le script en conséquence puis comparez le nombre de multiplications effectuées pour calculer $R_n$ en fonction de $n$ pour ces deux scripts.

C'est très simple, il suffit de mettre à jour R tant que l'objectif n'est pas atteint :

n = 1
R = 1
while R ≥ 0.5:
   R = R * ((365 - n) / 365)
   n = n + 1
print("R(" + str(n) + ") = " + str(R))

Avec l'algorithme initial, on réalise $n-1$ produits à chaque nouvelle valeur de $n$ pour calculer $R(n)$. Donc, en notant $\check{n}$ le minimum à atteindre, le nombre de produits effectués au total est \[\sum_{n=2}^{\check{n}}(n-1)=\frac{1}{2}\check{n}(\check{n}-1)\] Avec la version optimisée, on n'en calcule que $\check{n}-1$.

Comment évolue cette probabilité si le nombre $n$ d'étudiants augmente ? Comme on peut le vérifier à l'aide de l'application ci-dessous, à partir de $69$ étudiants, il n'y a plus qu'une chance sur $1\,000$ pour que tous soient nés un jour différent de l'année :

On pourrait se contenter de ce petit script pour répondre à la question, mais il faut réaliser dès à présent que nombre de problèmes ne peuvent être résolus à l'aide d'un programme informatique, parfois parce qu'un tel programme n'existe pas ou parce que le temps qu'il faudrait à ce programme pour nous fournir la réponse attendue est démesuré (Ces questions seront abordées en théorie de la calculabilité, en algorithmique et en théorie de la complexité). Il est donc important d'analyser un problème, soit pour y répondre directement, ou à défaut, pour être en mesure d'écrire des programmes plus efficaces.

On reprend l'expression de $R_n$ à gauche dans l'inégalité $(\ref{ineq:anniv})$ pour obtenir

\begin{equation} \label{eq:RNBIS} R_n=\big(1-\frac{0}{365}\big)\big(1-\frac{1}{365}\big)\big(1-\frac{2}{365}\big)\cdots\big(1-\frac{(n-1)}{365}\big). \end{equation}

Nous allons exploiter quelques résultats vus dans le cours d'analyse du premier semestre pour évaluer ce produit. On rappelle que l'exponentielle réelle $\text{exp}:\R\fromto\R$ est définie par la somme de la série convergente de terme général $\frac{x^n}{n!}$ :

\begin{align} \notag{\text{exp}\,}(x)&:= \lim_{n\rightarrow+\infty}\sum_{i=0}^{n}\frac{x^i}{i!}\\ &= \lim_{n\rightarrow+\infty}\left({\color{#88F}1+\frac{x}{1}}+\frac{x^2}{2}+\frac{x^3}{6}+\cdots+\frac{x^n}{n!}\right). \end{align}

On en déduit que ${\color{#88F}1+x} \approx \text{exp}\;(x)$ si $x$ est proche de $0$, puisque dans ce cas les termes de degré supérieur ou égal à 2 deviennent négligeables comparés à $1+x$. On peut alors réécrire $(\ref{eq:RNBIS})$ : \begin{align*} R_n&\approx \prod_{i=1}^{n-1}\text{exp}\,(-\frac{i}{365})\\ &\approx \text{exp}\,(-\frac{1}{365}{\sum_{i=1}^{n-1}i})\\ &\approx \text{exp}\,(-\frac{n(n-1)}{730})\\ \end{align*}

On doit finalement trouver la plus petite valeur de $n$ telle que

\begin{equation*} \text{exp}\,(-\frac{n(n-1)}{730})<\frac{1}{2}. \end{equation*}

Comme la fonction réciproque de la fonction exponentielle est la fonction logarithme et que cette dernière est croissante, on obtient

\begin{equation*} \frac{-n(n-1)}{730}\lt \text{ln}\,(\frac{1}{2})\ \iff\ n(n-1) \gt 730\;\text{ln}\,(2)\ \iff\ \underbrace{n^2-n-730\;\text{ln}\,(2)}_{P(n)}> 0. \end{equation*}

Ce qui nous amène à étudier le signe du polynôme $P(x)=x^2-x-730\,\ln(2)$. On calcule le discriminant $\Delta=1+2920\;\text{ln}\,(2)$ qui est strictement positif puisque $\text{ln}(2) \approx 0,\!69315$. Pour que $P(n)$ soit positif, donc du même signe que le coefficient de son monôme de degré 2, il faut que $x$ soit à l'extérieur de l'intervalle $[(1-{\color{orange}\sqrt{\Delta}})/2,(1+{\color{orange}\sqrt{\Delta}})/2]$ formé par les deux racines de $P(x)$. On peut passer au calcul effectif : \[ \Delta= 1+730\ln(2) \approx 2\,025 = ({\color{orange}9\times 5})^2. \] La seule racine positive est $x=\mathbf{23}$ et on retrouve le résultat numérique obtenu à l'aide du script Python.

Généralisation

Il ne faut pas limiter la portée de cette étude à la résolution d'un problème ludique. Nous allons voir que le paradoxe des anniversaires intervient en cryptographie. De la même manière qu'une signature manuelle ou une empreinte digitale est une très petite quantité qui résume et caractérise un individu, on peut construire l'empreinte numérique d'un document. Le calcul de cette empreinte est généralement réalisé par une fonction de hachage.

Il n'est pas question d'étudier ici les fonctions de hachage, nous n'en donnerons qu'une vision informelle et intuitive. Une fonction de hachage $h:X\rightarrow Y$ relie deux ensembles de tailles très différentes, l'ensemble de départ $X$ est très grand et contient tous les documents possibles (n'importe quel texte, lettre, mode d'emploi, journal, encyclopédies, ce cours, etc.). L'ensemble d'arrivée est quant à lui très petit comparativement à l'ensemble $X$, et contient donc les empreintes de ces documents.

Pour donner un ordre d'idée des cardinaux mis en jeu dans cette problématique, imaginons que les documents ne soient constitués qu'avec des symboles d'un alphabet minimaliste $\mathscr A$ constitué des 26 lettres de l'alphabet latin et de l'espace. C'est nettement insuffisant pour représenter les documents qui nous entourent, puisque ni les majuscules, ni les chiffres, ni les symboles diacritiques (accents, cédille, etc.), ni une multitude de signes très communs ne sont disponibles, néanmoins contentons nous de cet alphabet. Un simple courrier manuscrit d'une page comporte environ $1000$ symboles, le contenu d'un tel courrier peut donc être codé par un $1000$-uplet de ${\mathscr A}^{1000}$ et la formule $(\ref{eq:cardprodcart})$ sur le cardinal d'un produit cartésien nous donne immédiatement le nombre possible de courriers* Courriers abstraits sans se préoccuper de la signification du texte, sinon l'estimation serait plus proche de $10^{900}$, ce qui reste malgré tout gigantesque. différents, il y en a

\[27^{1000}=10^{1000\,\text{log}_{10}(27)}\approx 2.31\times 10^{1431},\]

ce qui dépasse de très loin tout nombre représentant une quantité réelle, puisque les physiciens estiment que le nombre de particules de la taille d'un proton^# Rayon $\approx8,\!8\times10^{-16}$m. qui pourraient être contenues (sans espace vide !) dans l'univers observable^$ Diamètre environ 93 milliards d'années lumière. est de l'ordre de $10^{124}$…

Nous savons d'après cet exercice que si l'ensemble des empreintes $Y$ est petit par rapport à l'ensemble des documents, la fonction $h$ ne peut certainement pas être injective. On souhaite cependant que la fonction $h$ satisfasse des conditions extrêmement contraignantes :

Calculer l'empreinte $h(x)$ d'un document $x$ donné est rapide,
Calculer l'image réciproque $h^{-1}(y)$ d'une empreinte $y$ donnée est infaisable,
Calculer deux documents $x_1$ et $x_2$ de même empreinte est infaisable,
Calculer un document $x_2$ de même empreinte qu'un document $x_1$ donné est infaisable.

Le terme infaisable signifie ici que le temps et/ou l'espace nécessaires pour obtenir le résultat dépassent de très loin les capacités des machines. Ces conditions permettent de vérifier l'intégrité d'un document ou d'assurer qu'un document est bien celui qu'on croit. En effet, toute modification d'un document se décèle facilement en calculant son empreinte et en la comparant à l'empreinte originale, les deux seront nécessairement différentes. D'autre part, si l'on connaît l'empreinte d'un document $x_1$, et que quelqu'un présente un document $x_2$ et prétend qu'il s'agit du document $x_1$, il suffit de comparer leurs deux empreintes, si elles sont égales, c'est qu'il s'agissait bien du même document $x_2=x_1$.

Les conditions 3 et 4 demandées aux fonctions de hachage nécessitent de s'intéresser au paradoxe des anniversaires. Si l'ensemble $X$ des documents jouent le rôle de l'ensemble des étudiants et l'ensemble des empreintes $Y$ le rôle de l'ensemble des dates d'anniversaire, nous savons déjà qu'il est certain qu'il existe deux documents qui ont la même empreinte puisqu'ici $\count{X} \gt \count{Y}$, mais cette fois il s'agit de les trouver. Combien de documents doit-on tirer au hasard dans $X$ pour que la probabilité d'en trouver qui ont la même empreinte soit supérieure à $\frac{1}{2}$ ? Il nous faut donc déterminer le cardinal $n\leqslant\count{Y}$ d'un sous-ensemble $E\subset X$ d'échantillons qui assure que la probabilité que la restriction $h|_E$ de la fonction de hachage à la partie $E$ soit injective est inférieure à $\frac{1}{2}$.

Comme ce sont des ordinateurs qui calculent des empreintes, elles sont vues comme des séquences binaires de longueur $b$, i.e. $Y:=\{0,1\}^b$, et on parle d'empreintes de $b$ bits.* binary digit.

On note $E\subset X$ l'espace des échantillons, $n:=\count{E}$ son cardinal, et $Y:=\{0,1\}^b$ l'espace des empreintes sur $b$ bits. Quel est le cardinal de l'espace $Y$ ? Vérifiez que la probabilité $R_n$ que tous les documents de $E$ aient des empreintes différentes est donnée par \[R_n=\prod_{i=1}^{n-1}\left(1-\frac{i}{2^b}\right).\] En approximant $1-x$ par $\text{exp}\;(-x)$, montrez que \[R_n\approx\text{exp}\;\left(-\frac{n(n-1)}{2^{b+1}}\right).\] Inspirez-vous des calculs effectués pour le paradoxe des anniversaires pour montrez que la plus petite valeur de $n$ telle que $R_n\lt \frac{1}{2}$ est égale à $2^{\frac{b}{2}}$.

En supposant que l'on dispose de machines capables de calculer $10^{12}$ empreintes par seconde, combien de temps faudrait-il pour traiter suffisamment d'échantillons pour atteindre la probabilité $\frac{1}{2}$ si les empreintes sont codées sur $96$ bits ?

À la lumière de cet exercice, il apparaît que la taille des échantillons à prélever est de l'ordre de la racine carrée de la taille de l'espace des empreintes, ce qui est considérablement plus faible et autorise une attaque si la taille des empreintes n'est pas assez grande.

Le modèle que nous avons établi pour le paradoxe des anniversaires est imparfait. En effet, il suppose implicitement que les dates de naissances des étudiants d'un amphithéâtre suivent une distribution uniforme sur l'intervalle ${[365]}$, autrement dit que la probabilité qu'un étudiant soit né un jour $j\in{[365]}$ est exactement $365^{-1}$. Les études démographiques montrent que la répartition des naissances n'est pas tout à fait uniforme, bien que la planification de la conception des enfants ait tendance à disparaître. Les questions de cette nature seront étudiées dans le prochain chapitre sur les probabilités.

Soit $n$ un entier naturel. Démontrez que \begin{align*} \prod_{k=1}^n(2k) &=2^n n!\\ \prod_{k=1}^n(2k-1) &=\frac{(2n)!}{2^n n!} \end{align*} Indication : séparez les termes pairs et impairs dans le calcul de $(2m)!$.

Compléments d'analyse combinatoire

Les résultats des deux prochaines propositions apparaissent de manière récurrente dans les calculs de complexité moyenne des algorithmes :

Soit $n$ et $p$ deux entiers naturels tels que $0\leqslant p\leqslant n.$ Alors \begin{equation} \sum_{p=1}^np\binom{n}{p} = n2^{n-1}. \end{equation}

En exercice. Considérez le polynôme formel $P(X):=(X+1)^n$ et calculez son polynôme dérivé $P'(X).$ Appliquez la formule du binôme de Newton pour développer $P(X)$ et calculez la dérivée de ce polynôme. En déduire le résultat.

Soit $n\in\N$ et $z\in\C$ avec $z\neq 1.$ Alors \begin{equation} \label{eq:sommepqp} \sum_{p=1}^n p\,z^p = \frac{z\left(n z^{n+1}-(n+1)z^n + 1\right)}{(z-1)^2}. \end{equation}

En exercice. Considérez le polynôme $P(Z):=1+Z+Z^2+\cdots+Z^{n-1}+Z^n$ et vérifiez que si $Z\neq 1,$ alors \[P(Z):=(Z^{n+1}-1)/(Z-1).\] Calculez sa dérivée $P'(Z)$ pour chacune de ses deux expressions. Concluez en calculant l'expression du polynôme $Z\,P'(Z).$

Si $z=1,$ la somme $(\ref{eq:sommepqp})$ n'est rien d'autre que la somme $n$ premiers entiers, autrement dit $n(n+1)/2.$

Le nombre de partitions d'un ensemble fini de cardinal $n$ est appelé $n$-ème nombre de Bell^♯Éric Temple Bell est un mathématicien écossais du 20ème siècle spécialisé en théorie de nombres et écrivain de science-fiction. et on le note $B_n$. Il satisfait la récurrence suivante : \begin{equation} \forall n\in\N\ \ B_{n+1}=\sum_{p=0}^{n}\binom{n}{p}B_p. \end{equation} Avec pour condition initiale $B_0=1$.

On vérifie facilement qu'il n'existe qu'une seule partition de l'ensemble vide, c'est la partition vide donc $B_0=1.$ (Notons qu'il n'y a pas de contradiction avec la condition qui stipule que tout élément d'une partition est non-vide, la partition étant vide, aucune de ses classes n'est vide.) L'unique partition d'un singleton $X=\{x\}$ est constituée du seul ensemble $X$, donc $B_1=1$. Nous allons démontrer le résultat général grâce au théorème de récurrence forte sur le prédicat $P(n)$ : \[ B_{n}=\sum_{p=0}^{n-1}\binom{n-1}{p}B_p. \] Nous venons de voir que $P(0)$ et $P(1)$ sont vrais. Soit $X$ un ensemble de cardinal $n+1$, il contient au moins un élément $x$. Pour constituer une partition $P$ de $X$, commençons par ranger $x$. Il doit appartenir à exactement une classe $Y\subseteq X$ de la partition $P$. On peut compléter cette classe $Y$ avec $p\in\llbracket 0,\,n\rrbracket $ autres éléments de $X$ et il y a $\binom{n}{p}$ façons de le faire d'après la définition d'un coefficient binomial. Pour compléter la partition $P$ de $X$, il reste à répartir les $n-p$ éléments restants de $X\setminus Y$ dans d'autres classes, autrement dit il faut créer une partition des $n-p$ éléments restants et il y a $B_{n-p}$ manières de le faire d'après l'hypothèse de récurrence. Pour conclure, pour chaque valeur $p\in\llbracket 0,\,n\rrbracket $, on peut construire $\binom{n}{p}$ parties $Y$ différentes de cardinal $p+1$ contenant $x$ et pour chacune d'entre elles, on peut répartir les $n-p$ éléments restants de $B_{n-p}$ manières distinctes : \begin{align*} B_{n+1}&=\sum_{p=0}^{n}\binom{n}{p}B_{n-p},\\ &=\sum_{p=0}^{n}\binom{n}{n-p}B_{n-p},\quad\text{d'après}\ (\ref{id:comb1}) \end{align*}

Soit $p$ et $n$ deux entiers naturels. Le nombre de partitions d'un ensemble fini de cardinal $n$ en $p$ classes est appelé nombre de Stirling*James Stirling est un mathématicien écossais du 18ème siècle précurseur de l'analyse numérique. et on le note $S(n,p).$ Il satisfait la récurrence suivante : \begin{equation} \forall n\in\N\ \ \forall p\in\N^*\quad S(n,p)=S(n-1,p-1)+pS(n-1,p). \end{equation} avec pour conditions initiales $S(0,0)=1$ et $\forall n>0,\ S(n,0)=S(0,n)=0.$

La preuve se fait encore une fois par récurrence forte pour $p$ fixé sur le prédicat $P(n)$ : \[S(n,p)=S(n-1,p-1)+pS(n-1,p).\] Pour $n=p=0$, la partition vide constitue bien une partition de l'ensemble vide en $0$ classes, donc $S(0,0)=1.$ Pour tout $n>0$, la partition vide n'est jamais un partition d'un ensemble non-vide, donc $S(n,0)=0$. D'autre part il n'existe aucun partition en $n>0$ classes de l'ensemble vide, donc $S(0,n)=0$. On considère à présent un ensemble $X$ de cardinal $n+1$ qui contient donc au moins un élément $x.$

Pour constituer une partition $P$ à $p$ classes de $X$, commençons par ranger l'élément $x$. Si à lui seul $\{x\}$ constitue une classe de $P$, alors les $n$ éléments restants de $X\setminus\{x\}$ sont à répartir en $p-1$ classes ce que l'on peut faire de $S(n,p-1)$ façons d'après l'hypothèse de récurrence. Sinon on répartit les $n$ éléments de $X\setminus\{a\}$ dans $p$ boites et il y a $S(n,p)$ façons de le faire d'après l'hypothèse de récurrence, il reste à ranger $x$ dans l'une de ces $p$ boites et il y a $p$ choix possibles, soit

\[S(n+1,p)=S(n,p-1)+pS(n,p).\]

Le corollaire suivant est immédiat :

Soit $n$ en entier naturel. On a \begin{equation} B_n=\sum_{p=1}^nS(n,p). \end{equation}

Soit $X$ et $Y$ deux ensembles finis de cardinaux $n:=\count{X}$ et $p:=\count{Y}$ tels que $0\leqslant p \leqslant n$. Le nombre de surjections de $X$ dans $Y$ est égal à \begin{equation} \label{eq:nbsurjections} p!\,S(n,p). \end{equation}

Soit $f:X\rightarrow Y:=\{y_1,y_2,\ldots,y_p\}$ une surjection. Notons $X_i:=f^{-1}(y_i)$ l'image réciproque de $y_i$. Alors par construction, $P:=\{X_1,X_2,\ldots,X_p\}$ est une partition de $X$ en $p$ classes. Mais pour cette unique partition, on dispose de $p!$ nouvelles surjections en permutant les $p$ éléments de $Y$. D'après la définition des nombres de Stirling, il y a $S(n,p)$ façons de partitionner l'ensemble de départ $X$ en $p$ classes $P=\{X_1,X_2,\ldots,X_p\}$ ce qui achève la preuve.

À partir de cette proposition, on peut établir une formule explicite pour les nombres de Stirling à l'aide du principe d'inclusion/exclusion. Nous admettrons ce résultat.

Soit $p$ et $n$ deux entiers naturels. Alors \begin{equation} S(n,p)=\frac{1}{p!}\sum_{k=0}^{p}(-1)^{p-k}\binom{k}{p}k^{n}. \end{equation}

Pour conclure, nous admettrons également le théorème suivant qui permet de mesurer la croissance de la fonction factorielle.

Soit $n$ un entier naturel. On a \begin{equation} \lim_{n\to+\infty}\frac{n!}{\sqrt {2\pi n}\;\left(\frac{n}{e}\right)^n}=1. \end{equation}

Autrement dit, la fonction factorielle se comporte asymptotiquement comme la fonction \[n\mapsto\sqrt {2\pi n}\;\left(\frac{n}{e}\right)^n\] ce qui permet aisément de déduire que la fonction factorielle croît plus vite que la fonction exponentielle mais moins vite que la fonction $n\mapsto n^n$ : \begin{align*} \lim_{n\to+\infty}\frac{e^n}{n!}&=0\\ \lim_{n\to+\infty}\frac{n!}{n^n}&=0\\ \end{align*}

En reprenant les mêmes conditions initiales que dans la définition des nombres de Stirling, démontrez l'égalité \begin{equation} \label{eq:stirling} S(n+1,p)=\sum_{k=0}^{n}\binom{n}{k}S(k,p-1). \end{equation}

Démontrez que le nombre de façons de ranger $n$ chaussettes dans $p$ tiroirs numérotés (l'ordre dans lequel les caleçons sont rangés dans un tiroir n'a pas d'importance) est égal a \begin{equation} \frac{(n+p-1)!}{(p-1)!} \end{equation}

Démontrez que le nombre d'applications croissantes d'un ensemble fini $X$ de cardinal $n$ dans un ensemble fini $Y$ de cardinal $p$ est égal à \begin{equation} \binom{n+p-1}{n}. \end{equation} Quel est le résultat si les applications sont strictement croissantes ?

Travaux pratiques

Nano tutoriel Python-UNIX à imprimer/lire/conserver.

En séance

Écrivez une fonction Python factorielle(n) qui calcule la factorielle du nombre entier $n$ passé en paramètre.

Écrivez un script en Python TrianglePascal(n) qui renvoie la liste des $n+1$ coefficients $\binom{n}{p}$ pour $p\in\llbracket 0,\,n\rrbracket $ en utilisant le principe de construction du triangle de Pascal. Indication : initialisez une liste de $n+1$ valeurs nulles puis mettez à jour cette liste en cohérence avec la construction des $n+1$ lignes du triangle de Pascal. Relisez au préalable cet exercice. En déduire une fonction Python binomial(n,p) qui renvoie le coefficient binomial $\binom{n}{p}$.

Un code phoque est un mot constitué uniquement avec deux symboles : le point . et le tiret -. Ces deux symboles sont transmis à l'aide de deux signaux qui ne diffèrent que par leur durée, le signal tiret est deux fois*trois fois pour le code morse. plus long que le signal point. Par exemple le code ..-. dont la longueur est $3+2=5$. La durée du signal point est normalisée à 1. Soit $n$ un entier supérieur ou égal à

En remarquant qu'un signal de longueur $n$ est constitué soit d'un point suivi d'un signal de longueur $n-1$ soit d'un tiret suivi d'un signal de longueur $n-2$, écrivez une fonction récursive phoque(n) qui renvoie la liste de tous les signaux de longueur $n$. Par exemple l'appel phoque(4) renvoie la liste ['....', '..-', '.-.', '-..', '--']

Écrivez la fonction phoqueit(n), version itérative de la fonction phoque(n). Comparez la durée d'exécution des deux versions pour $n=30$ en utilisant la commande time d'unix. Par exemple time python3 algo.py renvoie la durée d'exécution du script python algo.py. Bien sûr, ceci suppose que ce script ne contient pas de saisies à l'aide de la fonction input() qui pourraient fausser le calcul. Que constatez-vous ?

Compléments hors séance

On peut créer un script Python qui soit directement exécutable comme une commande unix et également récupérer les arguments éventuels de la commande. Pour cela :

Écrivez #!/usr/bin/python3 sur la première ligne du script.
Importez le module système : import sys.
Les arguments de la ligne de commande sont rangés dans la liste prédéfinie sys.argv sous forme de chaînes de caractères (sys.argv[0] contient le nom de votre script).
Exécutez la commande unix chmod +x monscript si votre script s'appelle monscript (l'extension .py n'est plus nécessaire).
Pour exécuter le script, il suffit de lancer ./monscript suivi éventuellement de paramètres.

On considère le script suivant nommé increment :

#!/usr/bin/python3
import sys

def plusun(n):
   return n + 1
    
if len(sys.argv) > 0:
   n = int(sys.argv[1])
   print(plusun(n))
else:
   print("Syntaxe: ",sys.argv[0]," entier")

Une fois transformé en fichier exécutable avec la commande chmod +x increment, la commande

./increment 13

affichera

alors que la commande

./increment

affichera

Syntaxe: increment entier

Écrivez la fonction Fibonacci(n) qui renvoie le tuple $F_0,F_1,\ldots,F_n$ des $n+1$ premiers termes de la suite récurrente de Fibonacci $(F_n)_{n\in\N}$ définie par les premiers termes $F_0:=0$, $F_1:=1$ et la récurrence $\forall n\geqslant 2$, $F_{n+2}=F_{n+1}+F_n$. Comparez $F_n$ avec la longueur de la liste renvoyée par phoqueit(n-1). Que constatez-vous ? Expliquez.

Écrivez une procédure récursive genuplet(n,m,nuplet) en Python qui affiche tous les $n$-uplets de l'ensemble $\llbracket 1,\,m\rrbracket^n$. Le paramètre nuplet servira à la construction récursive du $n$-uplet à afficher et sera initialisé au tuple vide $(\;)$ à l'appel de la procédure. Par exemple, l'appel genuplet(2,3,()) affichera tous les éléments de l'ensemble $\{1,2,3\}^2$ :

genuplet(2,3,())
(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(2,3)
(3,1)
(3,2)
(3,3)

On utilisera le type tuple du Python pour coder un $n$-uplet. On rappelle qu'un tuple est immuable et que l'on peut concaténer des tuples à l'aide de l'opérateur $+$, ainsi $(1,2)+(3,)=(1,2,3)$.

Indications : La base récurrente est à la programmation ce que l'initialisation est à la récurrence. Il s'agit de la partie du code que l'on doit réaliser directement sans faire d'appels récursifs. Quant à l'autodéfinition, elle correspond à l'hérédité et constitue le code qui contient les appels récursifs. La base récurrente de la procédure genuplet(n,m,nuplet) consiste à afficher le tuple passé en paramètre quand le paramètre d'appel $n$ vaut $0$ et l'autodéfinition consiste à rappeller la procédure avec chacun des $m$ tuples obtenus en concaténant le tuple passé en paramètre avec les tuples $(1,),(2,),\ldots,(m,)$.

Combinatoire

Introduction

Le paradoxe des anniversaires

Ensembles finis et infinis

L'ensemble des entiers naturels

Récurrences

Cardinaux

L'ordre naturel et les preuves d'arrêt

Analyse combinatoire

Produit cartésien

Autour des applications

Autour du coefficient binomial

Paradoxe des anniversaires

Résolution

Généralisation

Compléments d'analyse combinatoire

Travaux pratiques

En séance

Compléments hors séance