Combinatoire
\(\def\rg{\rightarrow}\def\succ{{\text{succ}\,}}\def\rel{{\,{\mathscr R}\,}}\def\N{{\mathbb N}}\def\Z{{\mathbb Z}}\def\Q{{\mathbb Q}}\def\R{{\mathbb R}}\)

Introduction

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

La question est la suivante :

Dans une classe, à partir de combien d'étudiants est-il plus probable d'en trou­ver deux qui soient nés le même jour plutôt que tous soient nés un jour différent ?

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, il ne s'agit pas de compliquer inu­ti­le­ment l'énoncé. D'autre part, pour éviter toute ambiguïté, on ne cherche pas à trouver exactement deux étudiants nés le même jour, mais qu'il existe dans cette classe au moins deux étudiants nés le même jour.

Les sondages réalisés auprès des étudiants pour estimer le nombre en question, aboutissent im­man­qua­blement à 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'étudiants pour espérer en trouver deux né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\) étudiants et ce résultat peut paraître déconcertant. Par conséquent l'expérience est systématiquement menée grandeur nature avec les étudiants 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 la plupart élémentaires) qui vont permettre de le prouver. Nous verrons également que ce 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 et l'ordre. Par extrapolation, on a conscience que compter pourrait durer éternellement malgré la finitude de nos existences et du monde qui nous entoure. Les questionnements philosophiques, religieux et scien­ti­fi­ques autour de l'existence et la nature de l'ensemble des entiers naturels ont tellement ob­sé­dés les hommes que le fruit de ces cogitations pourrait occuper un rayon complet de bi­blio­thè­que.

Il a fallu patienter jusqu'au début du siècle dernier pour que cet ensemble soit caractérisé, 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 :

On appelle ensemble naturel tout ensemble \(({\mathscr N},\preceq)\) ordonné qui satisfait les trois propriétés suivantes :
  1. Toute partie non-vide de \({\mathscr N}\) admet un plus petit élément,
  2. Toute partie non-vide de \({\mathscr N}\) non-vide et majorée admet un plus grand élément,
  3. L'ensemble \({\mathscr N}\) n'admet pas de plus grand élément.

En mathématiques, l'existence de l'ensemble des entiers naturels est acquise grâce à un axiome de la théorie des ensembles, l'axiome de l'infini.*(*) La construction ef­fec­ti­ve des entiers naturels est étudiée en lo­gi­que. C'est in­du­bi­ta­ble­ment l'ensemble séminal de cette théo­rie.

Il existe un ensemble naturel.
Démontrez à l'aide de la première propriété d'un ensemble naturel, qu'un tel ensemble est totalement ordonné.

On peut démontrer, mais ce n'est pas l'objet de ce cours, que si l'on se donne deux ensembles na­tu­rels, il existe toujours entre eux une unique bijection croissante telle que sa bijection réciproque est elle aussi croissante (il s'agit d'un isomorphisme d'ensembles ordonnés, comme nous le verrons au prochain chapitre). 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 res­pec­ti­ves. Autrement dit, nous pouvons toujours identifier un ensemble naturel quelconque à un seul d'entre eux. La construction de John Von Neuman montre comment retrouver l'ensemble \(\N\). La relation d'ordre sur \(\N\) est donc tout simplement issue de l'inclusion, on la note \(\leq\) ou \(\leqslant\) et on l'appelle l'ordre naturel.

Considérons \(X:=\{\upsilon,\zeta,\tau\}\) muni de l'ordre alphabétique grec et \(Y:=\{z,t,u\}\) muni de l'or­dre alphabétique latin. Démontrez qu'il existe une unique bijection croissante entre \(X\) et \(Y\) et que sa bi­jec­tion réciproque est croissante elle aussi.

Soit \(n\in\N\), la demi-droite \(]n,\rightarrow[\) n'est pas vide, sans quoi \(n\) serait le plus grand élément de l'en­sem­ble, ce qui est absurde d'après la propriété 3. Donc \(]n,\rightarrow[\) admet un plus petit élément d'après la pro­prié­té 1 et on l'appelle le successeur de \(n\) que l'on note \(\succ(n).\)*(*) Il s'agit bien sûr de l'entier \(n+1\) mais nous n'avons pas encore défini l'addition. 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\}\).

Inspirez vous de la construction d'un successeur pour définir le prédécesseur \(\text{prec}\,(n)\) d'un entier \(n\in{\N^*}\). Indication : construisez une demi-droite à laquelle vous appliquerez la propriété 2 d'un ensemble naturel.
Démontrez que l'ap­pli­ca­tion \(\succ\,:\N\rightarrow{\N^*}\) définie par \(n\mapsto\succ\,(n)\) est une bi­jec­tion crois­san­te. En déduire que l'ensemble \({\N^*}\) est un ensemble naturel.

Récurrence

Considérons une partie \(X\subseteq\N\) qui contient 0 et qui est stable pour l'application \(\succ\,:\N\rightarrow\N\), i.e. \(\succ(X)\subseteq X\). Nous allons démontrer que \(X=\N\) en faisant un rai­son­ne­ment par l'absurde en sup­po­sant que la partie \(Y:=\N\setminus X\) de \(\N\) n'est pas vide. Dans ce cas, d'après la propriété 1 d'un ensemble naturel, \(Y\) admet un plus petit élément \(y\) qui ne peut être nul puisque \(0\not\in Y\) car \(0\in X\). L'entier \(y\) admet donc un prédécesseur \(x\) qui ne peut ap­par­te­nir à \(Y\) sans quoi \(y\) ne serait plus le plus petit élément de \(Y\) puisque \(x < y\), donc \(x\in X\). Mais \(y=\succ(x)\) donc \(y\in\succ(X)\) or la partie \(X\) est stable pour l'application successeur donc \(y\in X\) ce qui contredit \(y\in Y\). Nous venons de prouver le principe de ré­cur­ren­ce :

Toute partie de l'ensemble \(\N\) qui contient \(0\) et sta­ble pour l'ap­pli­ca­tion successeur est l'ensemble \(\N\) tout entier.

Dans les deux théorèmes suivants nous avons anticipé l'étude de l'addition dans \(\N\) pour écrire \(n+1\) au lieu de \(\succ(n)\).

Soit \(P(n)\) un prédicat sur \(\N\) et \(a\in\N\). Si les deux assertions sui­van­tes sont satisfaites
  1. \(P(a)\) est vrai  (initialisation),
  2. \(\forall n\in\N\ \ P(n)\Rightarrow P(n+1)\) (hérédité).
alors \(\forall n\geq a\ \ P(n)\).
On définit le prédicat \(Q(n)\) par \(P(\succ^a(n))\) sur \(\N\) où \(\succ^a\) est le \(a\)-ème itéré de la fonc­tion successeur. La partie \(\{n\in\N\mid Q(n)\}\) contient 0 et est stable pour l'ap­pli­ca­tion suc­ces­seur. On applique le principe de récurrence et on déduit que \(\forall n\in\N,\ Q(n)\), autrement dit que \(\forall n\geq a,\ P(n)\).

Nous aurons parfois besoin pour démontrer que \(P(n+1)\) est vrai de supposer que \(P(k)\) est vrai pour tous les entiers \(a\leq k\leq n\).

Soit \(P(n)\) un prédicat sur \(\N\) et \(a\in\N\). Si les deux as­ser­tions sui­van­tes sont satisfaites
  1. \(P(a)\) est vrai  (initialisation),
  2. \((\forall k\in[a,n]\ \ P(k)) \Rightarrow P(n+1)\) (hérédité forte).
alors \(\forall n\geq a\ \ P(n)\).

Ensembles finis et infinis, cardinaux.

Dans toutes les activités scientifiques, compter, dénombrer, estimer des quantités sont des pratiques essentielles et en apparence inoffensives. Malheureusement dès que l'on manipule des ensembles in­fi­nis, la notion de quantité s'avère difficile à généraliser et notre intuition est passablement mise en défaut. Il est par exemple très logique de penser qu'il y a deux fois plus d'entiers naturels que d'entiers naturels pairs, nous ver­rons qu'il n'en est rien.

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 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'en­sem­bles quand bien même on ne peut pas nécessairement les dénombrer. L'équipotence définit une relation d'équivalence sur les éléments d'une famille d'ensembles. Soit \(n\in\N\). On dé­si­gne par \(\N_n\) l'intervalle \([1,n]\) pour l'ordre naturel avec pour convention \(\N_0=\varnothing\), et par \(\N^*\) l'en­semb­le \(\N\setminus\{0\}\).

Soient \(n\) et \(m\) deux entiers naturels et \(f\) une application de \(\N_m\rightarrow\N_n\). Alors
  1. Si \(f\) est une injection alors \(m\leq n\),
  2. Si \(f\) est une surjection alors \(n\leq m\),
  3. Si \(f\) est une bijection alors \(m=n\).
Démontrez la proposition précédente.

D'après les résultats de cet exercice, si un ensemble \(X\) est en bijection avec deux ensembles \(\N_m\) et \(\N_n,\) nécessairement \(n=m\). On peut alors donner la définition suivante :

Un ensemble \(X\def\count#1{\,|#1|\,}\) équipotent à un ensemble \(\N_n\) est appelé ensemble fini et l'entier \(n\) est appelé son cardinal. Dans le cas contraire, il est dit infini.

Il est important de se souvenir que l'on ne parle de cardinal d'un ensemble que si cet ensemble est fini, dans le cas contraire il faut parler d'ensemble infini et non pas d'ensemble de cardinal infini, même si cet abus de langage est souvent pratiqué. Le cardinal d'un ensemble fini \(X\) sera noté in­dif­fé­rem­ment \(\#X\) (usuelle chez les anglo-saxons), \(\count{X}\) ou \(\text{card}(X)\). On admettra le théorème suivant :

Toute partie de \(\N\) est finie si et seulement si elle est majorée.
L'ensemble \(\N\) est infini.

On démontre que :

  1. Toute partie \(A\) d'un ensemble fini \(X\) est finie et que \(\count{A}\leq\count{X}\),
  2. L'intersection d'une famille quelconque d'ensembles finis est fini,
  3. Soit \(f:X\rightarrow Y\) une application. Si \(X\) est fini alors \(\count{f(X)}\leq \count{X}\) avec égalité si et seulement si \(f\) est injective,
  4. Soit \(f:X\rightarrow Y\) une surjection. Si \(X\) est fini alors \(Y\) est fini et \(\count{Y}\leq \count{X}\) avec égalité si et seulement si \(f\) est bijective,
  5. Soit \(f:X\rightarrow Y\) une injection. Si \(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 :

Soient \(X\) et \(Y\) deux ensembles finis de même cardinal et \(f:X\rightarrow Y\) une ap­pli­ca­tion. Alors les trois assertions suivantes sont équivalentes :
  1. \(f\) est injective,
  2. \(f\) est surjective,
  3. \(f\) est bijective.
Autrement dit si \(f\) est injective ou surjective et que l'on note respectivement \(a\) (resp. \(b\)) les bijections entre \(X\) (resp. \(Y\)) et \(\N_n\) le diagramme suivant est commutatif : \begin{equation*} \require{AMScd} \begin{CD} X @>{f}>> Y\\ @VaVV\swarrow\!\!{}_b \\ \N_n \end{CD} \end{equation*}

On définit l'addition de deux entiers naturels comme l'application \(+:\N\times\N\rightarrow\N\) définie par \begin{equation} \label{def:loiadd} x+y:=\count{A\cup B} \end{equation} où \(A\) et \(B\) sont deux ensembles quelconques disjoints et de cardinaux respectifs \(x\) et \(y\). On définit également le produit ou la multiplication de deux entiers naturels comme l'application \(\times:\N\times\N\rightarrow\N\) définie par \begin{equation} \label{def:loiprod} x\times y:=\count{A\times B} \end{equation} mais cette fois les deux ensembles peuvent ne pas être disjoints. Nous verrons que ces applications constituent des lois de compositions internes et nous étudierons leurs propriétés générales qui sont déjà bien connues du lecteur pour l'ensemble \(\N\). Notons que ces applications sont notées de manière infixe.

On définit une relation binaire sur l'ensemble des entiers naturels \(\N\) appelée divisibilité :

\begin{equation} a\mid b\Leftrightarrow \exists c\in {\N},\ ac=b. \end{equation}

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 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. Le plus petit nombre premier est donc l'entier naturel \(2\) est 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)\), le contexte évitant toute confusion en général :

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

On définit le plus petit commun multiple de deux entiers \(a\) et \(b\) :

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

Si le plus grand commun diviseur \((a,b)=1\), on dit que \(a\) et \(b\) sont premiers entre eux. Nous re­vien­drons en détail sur cette relation particulière et les interactions entre les deux lois additive et mul­tip­li­ca­ti­ve dans le chapitre consacré à l'Arithmétique.

Un chef de chantier essaie d'organiser la construction d'une villa dans le Var. Il doit faire intervenir deux artisans le même jour. Le premier n'est disponible qu'un jour sur 6, l'autre une fois tous les 11 jours. Le chef de chantier a pu rencontrer le premier artisan le lundi 12 mars et le second le mercredi 14 mars. Quel jour doit-il leur donner rendez-vous pour leur faire effectuer les travaux le plus tôt possible ?
Un ensemble équipotent à \(\N\) est dit dénombrable. Un ensemble fini ou dé­nom­bra­ble est dit au plus dénombrable.
Attention au vocabulaire ! En français dénombrable signifie que l'on est ca­pa­ble de compter les éléments, il est plutôt synonyme de fini alors qu'en ma­thé­ma­ti­ques un ensemble dénombrable est 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 numéroter les éléments d'un ensemble \(X\) au plus dénombrable (fini ou dénombrable). S'il est fini on peut l'écrire \(X=\{x_1,x_2,\ldots,x_n\}\), s'il est dé­nom­bra­ble (donc infini) alors \(X=(x_i)_{i\in\N}\). Ce n'est que la stricte ap­pli­ca­tion des définitions.

Ces définitions n'ont d'intérêt que s'il existe des ensembles qui ne sont pas dénombrables et c'est le cas. Il existe des ensembles dont on ne peut pas numéroter tous les éléments. Par exemple l'ensemble \({\mathscr P}(\N)\) des parties de \(\N\) ou l'ensemble des nombres réels \(\R\) ne sont pas dénombrables. Nous ne le démontrerons pas dans ce cours. On dit parfois qu'un ensemble est discret s'il est au plus dénombrable, dans le cas contraire on dit qu'il est 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.

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 \mid \exists k\in\N\ \ n=2k\},\] et considérons l'application \(f:\N\rightarrow P\) définie par \(f(n):=2n\). Elle est évidemment injective car si \(f(n)=f(m)\), alors \(2n=2m\) et on en déduit que \(n=m\). Elle est également surjective car tout élément \(y\in P\) est pair et par définition il existe un entier \(k\) tel que \(y=2k\), autrement dit \(k\) est l'antécédent cherché. En conclusion, l'ensemble des entiers naturels pairs est équipotent à l'ensemble des entiers naturels tout entier, ce qui contredit l'idée informelle qu'il y a deux fois plus d'entiers que d'entiers pairs.

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

Analyse combinatoire

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 in­dis­pen­sa­ble en probabilités discrètes. Nous admettrons les propositions les plus difficiles à démontrer.

La multiplication de deux entiers \(n\) et \(m\) fournit la proposition suivante et l'explication de la notation du produit cartésien :

Soient \(X\) et \(Y\) deux ensembles finis. Alors \begin{equation} \count{X\times Y}=\count{X}\times\count{Y}. \end{equation}

En itérant cette proposition \(n\) 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}

Nous avons vu au chapitre précédent que l'on notait \(Y^X\) l'ensemble des applications d'un ensemble \(X\) dans un ensemble \(Y\), voici la justification de cette notation :

Soient \(X\) et \(Y\) deux ensembles finis. Alors \begin{equation} \label{eq:nbapplications} \count{Y^X}=\count{Y}^{|X|}. \end{equation}
Notons \(n:=\count{X}\) et posons \(X=\{x_1,x_2,\ldots,x_n\}\). Montrons que l'ensemble \(Y^X\) est équipotent au produit cartésien \(\mathscr X\) des \(n\) ensembles \(X_i:=\{x_i\}\times Y\). Il suffira alors d'une part d'appliquer la proposition précédente pour montrer que \(\forall i\in\N_n,\ \count{\{x_i\}\times Y}=\count{Y}\) puis de conclure avec le co­rol­lai­re appliqué au produit catésien \(\mathscr X.\)

Soit \(f:X\rightarrow Y\) une application. Par dé­fi­ni­tion, son graphe \(G=\{(x_i,f(x_i))\mid i\in\N_n\}\). On définit alors l'ap­pli­ca­tion \(s:Y^X\rightarrow\mathscr X\) par \[ s(G)=(c_1,c_2,\ldots,c_n)\ \ \text{où}\ c_i:=(x_i,f(x_i)) \] L'application \(s\) est évidemment injective, à deux graphes distincts on associe bien deux \(n\)-uplets de couples distincts. Elle est surjective, car tout \(n\)-uplet \(\big((x_1,y_1), (x_2,y_2),\ldots,(x_n,y_n)\big)\) du produit cartésien \(\mathscr X\) 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}
Notons \(n:=\count{X}\) 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 \(s:{\mathscr P}(X)\rightarrow \{0,1\}^n\) par \begin{equation} \label{eq:vecteurcaract} \chi(A):=(1_A(x_1),1_A(x_2),\ldots,1_A(x_n)), \end{equation} où \(1_A\) est l'indicatrice de la partie \(A\), i.e. \begin{equation*} 1_A(x):=\begin{cases}1&\text{si}\ x\in A,\\0&\text{sinon}.\end{cases} \end{equation*} L'application \(s\) est injective, à deux parties distinctes de \(X\) elle associe deux \(n\)-uplets distincts et à chaque \(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\).
L'écriture \((\ref{eq:vecteurcaract})\) dans cette preuve 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.
Soit \(X\) un ensemble fini, et \((X_i)_{i\in I}\) une partition de \(X.\) Alors l'ensemble d'indexation \(I\) et tous les ensembles \(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 \((\ref{eq:sommation})\) provient de la définition de l'addition dans \(\N\).
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} Cette identité est appelée principe des bergers.
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 > m\), un tiroir contient au moins \(2\) caleçons.

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

\begin{equation} n\mapsto\begin{cases} 1&\text{si}\ n=0,\\ n\times(n-1)\times(n-2)\times \cdots\times 3\times 2\times 1&\text{si}\ n>0. \end{cases} \end{equation}

Et on note \(n!\) l'image d'un entier \(n\) pour cette application. C'est une fonction qui croît très ra­pi­de­ment, bien plus rapidement que la fonction exponentielle, par exemple \(10!=3\,628\,800\) alors que \(\text{exp}(10)\approx 22\,026\).

Écrivez une fonction Python factorielle(n) qui calcule la factorielle du nombre entier \(n\) passé en paramètre.
Soient \(X\) et \(Y\) deux ensembles finis de cardinaux \(p:=\count{X}\) et \(n:=\count{Y}\) tels que \(0\leq p \leq n\). Le nom­bre d'injections de \(X\) dans \(Y\) est l'entier \begin{equation} \label{eq:nbinjections} \frac{n!}{(n-p)!} \end{equation}
Le nombre de bijections d'un ensemble fini de car­di­nal \(n\) sur lui-même est égal à \begin{equation} n! \end{equation}

Une bijection d'un ensemble fini sur lui-même s'appelle une permutation, le chapitre prochain est consacré à l'étude des permutations.

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

La logique voudrait que nous fournissions maintenant le nombre de surjections d'un ensemble fini dans un ensemble fini, mais c'est un résultat plus difficile à établir, il faut donc patienter.

Le nombre de parties à \(p\) éléments d'un ensemble fini \(X\) de car­di­nal \(n\) est égal à \begin{equation} \label{coefbinomial} \frac{n!}{(n-p)!p!} \end{equation} Ce nombre est appelé coefficient binomial, on le note \(\binom{n}{p}\).

Les coefficients binomiaux sont très utilisés en combinatoire, à tel point qu'il existe des ouvrages qui sont spécifiquement dédiés à leur étude, il faut donc en connaître les propriétés élémentaires. Soient \(p\) et \(n\) deux entiers tels que \(0\leq p\leq 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} \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'en­semb­le \({\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[0,n]\) formant une partition de \({\mathscr P}_p(X)\). L'égalité \((\ref{eq:cardparties})\) et la formule de sommation \((\ref{eq:sommation})\) permettent de conclure.

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[0,n]\), 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{#FF0}\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 ob­ser­ver la cons­truc­tion de ce triangle en saisissant une valeur maximale \(n=\) ou en cliquant sur le bouton ci-dessous.

Calcul des coefficients binomiaux du triangle de Pascal pour \(n\leq\ \).

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

La formule du binôme de Newton 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 cha­pi­tre consacré à l'ari­thmé­ti­que. et que ces deux éléments commutent.

Soit \(n\in\N\) et soient \(x\) et \(y\) deux éléments d'un anneau qui commutent. Alors \begin{equation} \label{eq:binomenewton} (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é \((\ref{eq:binomenewton})\). 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 dif­fé­rents termes de cette somme plutôt que d'apprendre par cœur les coefficients binomiaux.

Développer l'expression \((x-y)^6\). Soit \(n\) un entier naturel, quels sont les coefficient de \((1+x)^n\) une fois l'expression développée ?

Si l'on se donne deux ensembles \(X\) et \(Y\), le cardinal de leur réunion est égal à la somme de leurs car­di­naux 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 appelé principe d'inclusion/exclusion et qui gé­né­ra­li­se ce résultat.

Soient \((X_i)_{i\in[1,n]}\) une famille d'ensembles fi­nis. Alors \begin{equation} \label{eq:somminout} \Big|\;\bigcup_{i=1}^{n}X_i\;\Big| = \sum_{k=1}^{n}(-1)^{k-1}\sum_{\color{#88F}1\leq i_{1}\,<\,i_2\,<\,\cdots\,<\,i_{k}\leq 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[1,\,k]}\) strictement croissante et bornée par les valeurs \(1\) et \(n\).

Paradoxe des anniversaires

Nous avons à présent tous les outils pour étudier 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 support pour re­pré­sen­ter 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 di­rec­te­ment l'expérience dans une salle de classe, on conserverait le nom, et éventuellement le prénom en cas d'homonymie*(*) deux per­son­nes dis­tinc­tes doivent avoir des identifiants dis­tincts, 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, autrement dit un couple \((j,m)\in[1,31]\times[1,12]\).

C'est un modèle tout à fait convenable mais il est est bien trop riche pour nos besoins. En effet, le problème ne demande 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 la classe et le nombre de jours dans l'année qui sont déterminants. Il est donc plus pertinent de coder la classe 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 du jour et du mois.

On a donc, d'un côté l'ensemble des étudiants \(X\) et de l'autre l'ensemble des dates \(Y\:=[1,365]\). Si l'ensemble des étudiants est de cardinal \(n\), par définition il est équipotent à l'ensemble \(\N_n:=[1,n]\), autant supposer que \(X=[1,n]\). Notons que si le problème demandait également d'identifier les étu­diants, nous pourrions malgré tout continuer à utiliser l'intervalle \([1,n]\) pour les représenter. Il suffirait de conserver la bijection qui lie \([1,n]\) à \(X\) pour retrouver le couple \((p,n)\). C'est exactement ce que fait l'administration avec le numéro qui vous identifie sur votre carte d'étudiant.

Une relation lie les éléments de ces deux ensembles, chaque numéro \(x\) d'étudiant est associé à un quan­tième \(y\) de l'année codant la date de naissance de l'étudiant. Il s'agit bien sûr d'une application \(f:[1,n]\rightarrow [1,365]\). Avec ce modèle comment traduit-on qu'il n'existe pas d'étudiants nés le même jour ? Ceci signifie que deux étudiants distincts ont des dates de naissances distinctes et on reconnaît immédiatement là une injection.

Résumons la situation. Une classe d'étudiants définit une instance du problème, à savoir une ap­pli­ca­tion \(f:[1,n]\rightarrow[1,365]\). Nous savons que si cette application est injective, cela signifie qu'il n'existe pas d'étudiants nés le même jour. Sans même introduire le langage du calcul des pro­ba­bi­li­tés, qui sera étudié spécifiquement dans le cours de probabilités discrètes de la licence, si l'on se donne la taille \(n\) d'une classe et que l'on est capable de calculer le nombre d'ap­pli­ca­tions 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 nous fournira la probabilité qu'une classe de \(n\) élèves 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 restera qu'à trouver la plus petite valeur de \(n\) telle que \(1-R_n>1/2\), soit \(R_n<1/2\).

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

Trouver le plus petit entier naturel \(n\) tel que le ratio entre le nombre d'in­jec­tions et le nombre d'applications d'un ensemble à \(n\) éléments vers un ensemble à \(365\) éléments est supérieur à \(50\).

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{\frac{365!}{(365-n)!}}{365^n} =\frac{365\times364\times\cdots\times(365-(n-1))}{365^n}. \end{equation}

Nous savons déjà qu'il est impossible d'obtenir une injection \(f:X\rightarrow Y\) entre deux ensembles finis \(X\) et \(Y\) si \(\count{Y} < \count{X}\). Autrement dit, si la classe contient \(n>365\) étudiants, il est certain qu'il existe deux étudiants nés le même jour. On cherche donc la plus petite valeur entière \(n\leq 365\) telle que

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

Malheureusement, 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 en 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)))
La valeur renvoyée par ce programme est \(n=23\). Comment évolue cette probabilité si la taille de la classe augmente ? Pour une classe de \(n:=\,\) étudiants, la probabilité de trouver deux étudiants nés le même jour est égale à \(1-R_n\approx\;\) Comme on peut le constater, à partir d'un am­phi de \(69\) étudiants, il n'y a plus qu'une chance sur \(1000\) pour que tous les étudiants soient nés un jour différent !

On pourrait se contenter de ce programme 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'être en mesure d'analyser un problème, soit pour y répondre directement ou à défaut pour écrire des programmes plus efficaces.

On repart de l'expression de \(R_n\) à gauche dans \((\ref{ineq:anniv})\) pour obtenir

\begin{equation} \label{eq:RNBIS} R_n=\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 cette somme. On rappelle que l'exponentielle réelle est une application de \(\R\) dans \(\R\) définie par la somme de la série convergente de terme général \(\frac{x^n}{n!}\) :

\begin{align} \notag x\mapsto {\text{exp}\,}(x)&:= \lim_{n\rightarrow+\infty}\sum_{i=0}^{n}\frac{x^n}{n!}\\ &= \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} < \text{exp}\;(-x)\), et on sait de plus que si \(x\) est proche de 0, cette majoration est fine puisque les termes d'ordre supérieur à 2 sont négligeables. On réécrit \((\ref{eq:RNBIS})\) :

\begin{align*} R_n&< \prod_{i=1}^{n-1}\text{exp}\,(-\frac{i}{365})\\ &< \text{exp}\,(-\frac{1}{365}{\color{#FF0}\sum_{i=1}^{n-1}i})\\ \end{align*}

La somme des \(n-1\) premiers entiers naturels non-nuls se calcule aisément (c'est la somme d'une série arithmétique de raison 1 vue en classe de 1ère. Vous pouvez également chercher comment Gauss a répondu à cette question à l'âge de 10 ans) :

\begin{equation*} {\color{#FF0}\sum_{i=1}^{n-1}i}=\frac{n(n-1)}{2}. \end{equation*}

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{align*} \frac{-n(n-1)}{730} &< \text{ln}\,\frac{1}{2}\\ \frac{-n(n-1)}{730} &< -\text{ln}\,2\\ n(n-1) &> 730\;\text{ln}2\\ \underbrace{n^2-n-730\;\text{ln}2}_{P(n)}&> 0. \end{align*}

Il faut donc étudier le signe du polynôme \(P(n)\). Le discrimant \(\Delta=1+2920\;\text{ln}\,2\) est manifestement strictement positif puisque \(\text{ln}\,2\approx 0.3931 > 0\). 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 \([x_1,x_2]\) formé par les deux racines de \(P(n)\). On peut passer au calcul effectif. On a \[ \Delta\approx (9\times 5)^2 \] et on en tire les deux racines \(x_1\approx -22\) et \(x_2\approx \mathbf{23}\) ce qui permet de retrouver le résultat numérique obtenu à l'aide de notre script Python.

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 caractérise un individu, on peut construire l'empreinte numérique d'un document. Il s'agit d'une quantité de taille réduite qui est censé résumer et caractériser 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 in­for­mel­le et intuitive. Une fonction de hachage \(h:X\rightarrow Y\) relie deux ensembles de tailles très dif­fé­ren­tes, 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 l'alphabet minimaliste \(\mathscr A\) constitué des 26 lettres de l'alphabet 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 pas 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 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 d'atomes contenus dans notre univers observable est de l'ordre de \(10^{81}\)…

Nous savons d'après cet exercice que si l'ensemble des empreintes \(Y\) est petit par rapport à l'en­semb­le des documents, la fonction \(h\) ne peut certainement pas être injective. On souhaite ce­pen­dant que la fonction \(h\) satisfasse des conditions extrêmement contraignantes :

  1. Calculer l'empreinte \(h(x)\) d'un document \(x\) donné est rapide,
  2. Calculer l'image réciproque \(h^{-1}(y)\) d'une empreinte \(y\) donnée est infaisable,
  3. Calculer deux documents \(x_1\) et \(x_2\) de même empreinte est infaisable,
  4. 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é­pas­sent 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 comprarant à l'empreinte ori­gi­na­le, les deux seront nécessairement différentes. D'autre part, si l'on connaît l'empreinte d'un do­cu­ment \(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 com­pa­rer 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 \(Y\) des empreintes 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} > \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\leq\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 do­cu­ments 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 < \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 au­to­ri­se 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 im­par­fait. En effet, il suppose implicitement que les dates de naissances des élèves d'une classe suivent une distribution uniforme sur l'intervalle \([1,365]\), autrement dit que la pro­ba­bi­li­té qu'un étudiant soit né un jour \(j\in[1,365]\) est exactement \(365^{-1}\). Les études démographiques montrent que la répartition des naissances n'est pas tout à fait uni­for­me, bien que la pla­ni­fi­ca­tion de la conception des enfants ait tendance à dis­pa­raî­tre. Les questions de cette nature seront étudiées dans le cours de probabilités discrètes.
Soient \(p\) et \(n\) deux entiers tels que \(0\leq p\leq n\). Démontrez que \begin{equation*} \sum_{p=0}^np\binom{n}{p} = n2^{n-1}. \end{equation*} Indication : utilisez la formule du binôme pour développer le polynôme \(P(X):=(X+1)^n\). Calculez éga­le­ment son polynôme dérivé.
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)!\).
Soit \(q\) un entier naturel. Démontrez que \begin{equation*} \sum_{k=0}^nkq^k = \frac{q}{(q-1)^2}[q^{n}(n(q-1)+1)+1]. \end{equation*} Indication : Vérifiez que le polynôme \(P(X):=\frac{X^{n+1}-1}{X-1}=X^n+X^{n-1}+\cdots+X^2+X+1\). Calculez éga­le­ment son polynôme dérivé.
Soit \(n\) un entier naturel. Démontrez par récurrence que \begin{equation*} \sum_{k=0}^nk^2 = \frac{n(n+1)(2n+1)}{6} \end{equation*}

Compléments

Le nombre de partitions d'un ensemble fini de cardinal \(n\) est appelé \(n\)-ème nombre de Bell et on le note \(B_n\). Il satisfait la récurrence suivante : \begin{equation} \forall n\geq 2,\ \ B_{n}=\sum_{p=0}^{n-1}\binom{n-1}{p}B_p. \end{equation} Avec pour conditions initiales \(B_0=1,\ B_1=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[0,n]\) 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[0,n]\), 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*} Et on conclut en réindexant la somme.
Soient \(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 et on le note \(S(n,p).\) Il satisfait la récurrence suivante : \begin{equation} \forall n,\ \forall p>0\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}
Soient \(X\) et \(Y\) deux ensembles finis de cardinaux \(n:=\count{X}\) et \(p:=\count{Y}\) tels que \(0\leq p \leq n\). Le nom­bre de surjections de \(X\) dans \(Y\) est l'entier \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.

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

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

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 ex­po­nen­tiel­le 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}
Inspirez vous de la construction du triangle de Pascal pour écrire un script en Python qui cons­truit le triangle de Stirling d'après l'identité \((\ref{eq:stirling})\).
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 ?