MPSI · Dénombrement

Dénombrement des applications

Palier 0Palier 1Palier 1+Palier 2

Cette partie offre une lecture unifiée des objets combinatoires étudiés précédemment (pp-uplets, arrangements, permutations, parties), en les interprétant comme des applications particulières entre ensembles finis.

Le principe de la réinterprétation. Un pp-uplet (x1,x2,…,xp)(x_1,x_2,\dots,x_p) d'éléments de EE peut être vu comme une application

φ:⟦1,p⟧⟶E,i⟼xi.\varphi:\llbracket 1,p\rrbracket\longrightarrow E,\qquad i\longmapsto x_i.

Chaque pp-uplet correspond exactement à une telle application, et réciproquement. La nature de l'objet combinatoire se reflète alors dans les propriétés de l'application associée, comme le résume le tableau suivant :

Objet combinatoireContrainteTraduction
pp-uplet de EEordre, répétition permiseapplication quelconque ⟦1,p⟧→E\llbracket 1,p\rrbracket\to E
pp-arrangement de EEordre, sans répétitionapplication injective ⟦1,p⟧→E\llbracket 1,p\rrbracket\to E
Permutation de EEordre, sans répétition, exhaustifbijection E→EE\to E
Partie A⊆EA\subseteq Epas d'ordreapplication E→{0,1}E\to\{0,1\} (fonction indicatrice 1A\mathbf{1}_A)

Question

Le tableau ci-dessus renverse la perspective : au lieu de compter des tirages, des mots ou des parties, il ne reste plus qu'à compter des applications, en faisant varier la contrainte imposée. Commençons par le cas sans contrainte du tout. Combien y a-t-il d'applications d'un ensemble fini dans un autre — et la réponse dépend-elle de la nature des éléments, ou seulement des deux cardinaux ?

Théorème 1 : Dénombrement des applications

Si EE et FF sont des ensembles finis non vides, alors l'ensemble FEF^E des applications de EE vers FF est fini et

Card⁡(FE)=(Card⁡F)Card⁡E.\operatorname{Card}\bigl(F^E\bigr)=(\operatorname{Card} F)^{\operatorname{Card} E}.

Remarque :

La notation FEF^E n'est pas arbitraire : elle encode le cardinal, puisque Card⁡(FE)=(Card⁡F)Card⁡E\operatorname{Card}(F^E)=(\operatorname{Card} F)^{\operatorname{Card} E}.

Démonstration :

Posons Card⁡E=n\operatorname{Card} E=n. Notons (x1,x2,…,xn)(x_1,x_2,\dots,x_n) les éléments de EE. On définit l'application

Φ:FE⟶Fn,φ⟼(φ(x1),φ(x2),…,φ(xn)).\Phi:F^E\longrightarrow F^n,\qquad \varphi\longmapsto\bigl(\varphi(x_1),\varphi(x_2),\dots,\varphi(x_n)\bigr).
  • Injectivité. Soient φ,ψ∈FE\varphi,\psi\in F^E telles que Φ(φ)=Φ(ψ)\Phi(\varphi)=\Phi(\psi), c'est-à-dire φ(xi)=ψ(xi)\varphi(x_i)=\psi(x_i) pour tout i∈⟦1,n⟧i\in\llbracket 1,n\rrbracket. Comme (x1,…,xn)(x_1,\dots,x_n) est une énumération de tous les éléments de EE, on a φ=ψ\varphi=\psi.
  • Surjectivité. Soit (y1,y2,…,yn)∈Fn(y_1,y_2,\dots,y_n)\in F^n. L'application φ:E→F\varphi:E\to F définie par φ(xi)=yi\varphi(x_i)=y_i pour tout i∈⟦1,n⟧i\in\llbracket 1,n\rrbracket vérifie Φ(φ)=(y1,…,yn)\Phi(\varphi)=(y_1,\dots,y_n).

Ainsi Φ\Phi est bijective, donc Card⁡(FE)=Card⁡(Fn)=(Card⁡F)Card⁡E\operatorname{Card}(F^E)=\operatorname{Card}(F^n)=(\operatorname{Card} F)^{\operatorname{Card} E}.

Exemple :

Une grille de loto sportif à 1313 matchs, chacun coché 11, NN ou 22, est exactement une application de l'ensemble des matchs vers {1,N,2}\{1,N,2\} : il y a donc 313=1 594 3233^{13}=1\,594\,323 grilles. On remarquera que c'est l'ensemble d'arrivée qui monte en puissance, et l'ensemble de départ qui fournit l'exposant. Pourquoi dans ce sens-là, et pas l'inverse ?

Test 1 : Qui monte en exposant ?

Si EE et FF sont finis non vides, alors Card⁡(FE)=(Card⁡E)Card⁡F\operatorname{Card}(F^E)=(\operatorname{Card} E)^{\operatorname{Card} F}.

Exercice 1

Redémontrer la formule Card⁡P(E)=2n\operatorname{Card}\mathcal{P}(E)=2^n en réalisant une bijection entre P(E)\mathcal{P}(E) et {0,1}E\{0,1\}^E.

Solution :(cliquer pour afficher)

Posons n=Card⁡En=\operatorname{Card} E et considérons

f:{P(E)⟶{0,1}EA⟼1Af:\left\{ \begin{aligned} &\mathcal{P}(E)\longrightarrow\{0,1\}^E\\ &A\longmapsto \mathbf{1}_A \end{aligned}\right.

où 1A\mathbf{1}_A désigne la fonction indicatrice de AA, définie par 1A(x)=1\mathbf{1}_A(x)=1 si x∈Ax\in A et 1A(x)=0\mathbf{1}_A(x)=0 sinon.

Injectivité. Soient A,B∈P(E)A,B\in\mathcal{P}(E) telles que 1A=1B\mathbf{1}_A=\mathbf{1}_B. Pour tout x∈Ex\in E on a alors

x∈A  ⟺  1A(x)=1  ⟺  1B(x)=1  ⟺  x∈B,x\in A\iff \mathbf{1}_A(x)=1\iff \mathbf{1}_B(x)=1\iff x\in B,

donc A=BA=B.

Surjectivité. Soit φ∈{0,1}E\varphi\in\{0,1\}^E et posons A=φ−1({1})={x∈E : φ(x)=1}A=\varphi^{-1}(\{1\})=\{x\in E \ :\ \varphi(x)=1\}, qui est une partie de EE. Pour tout x∈Ex\in E, on a 1A(x)=1\mathbf{1}_A(x)=1 si et seulement si x∈Ax\in A, c'est-à-dire si et seulement si φ(x)=1\varphi(x)=1 ; comme φ\varphi et 1A\mathbf{1}_A ne prennent que les valeurs 00 et 11, cela entraîne 1A=φ\mathbf{1}_A=\varphi. Donc φ=f(A)\varphi=f(A).

Ainsi ff est bijective et, d'après le théorème précédent,

Card⁡P(E)=Card⁡{0,1}E=2 n.\operatorname{Card}\mathcal{P}(E)=\operatorname{Card}\{0,1\}^E=2^{\,n}.

Question

On vient de compter les applications sans aucune contrainte. Le tableau de réinterprétation annonçait que les pp-arrangements sont les applications injectives, et les permutations les bijections. Ces deux comptages sont-ils déjà connus sous un autre nom — et si oui, quel travail reste-t-il à faire ?

Théorème 2 : Dénombrement des injections et des bijections

Soient EE et FF deux ensembles finis non vides, avec Card⁡E=p\operatorname{Card} E=p et Card⁡F=n\operatorname{Card} F=n.

  1. Si p⩽np\leqslant n, le nombre d'injections de EE dans FF est Anp=n!(n−p)!=n(n−1)⋯(n−p+1)A_n^p=\dfrac{n!}{(n-p)!}=n(n-1)\cdots(n-p+1).
  2. Si p=np=n, le nombre de bijections de EE sur FF est n!n!.

Démonstration :

Une injection φ:E→F\varphi:E\to F est entièrement déterminée par le pp-uplet (φ(x1),…,φ(xp))(\varphi(x_1),\dots,\varphi(x_p)), dont les termes sont des éléments distincts de FF (l'injectivité interdit les répétitions). Un tel pp-uplet est exactement un pp-arrangement de FF, et il y en a Anp=n!(n−p)!A_n^p=\dfrac{n!}{(n-p)!}.

Lorsque p=np=n, toute injection de EE dans FF est nécessairement surjective (deux ensembles de même cardinal fini), donc bijective. On retrouve Ann=n!A_n^n=n!.

Remarque :

Le nombre de surjections de EE sur FF (avec p⩾np\geqslant n) est nettement plus difficile à calculer et n'est pas au programme. À titre informatif, il est donné par la formule

S(p,n)=∑k=0n(−1)k(nk)(n−k)p.S_{(p,n)}=\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^p.

Test 2 : Injecter dans plus petit

Soient EE de cardinal 55 et FF de cardinal 33. Le nombre d'injections de EE dans FF est A35A_3^5.

Test 3 : Compter les bijections

Il existe exactement n!n! bijections entre deux ensembles finis de même cardinal n⩾1n\geqslant 1.

Exercice 2 : Applications, injections, surjections

On pose E=⟦1,4⟧E=\llbracket 1,4\rrbracket et F=⟦1,3⟧F=\llbracket 1,3\rrbracket.

  1. Combien y a-t-il d'applications de EE dans FF ?
  2. Combien y a-t-il d'injections de EE dans FF ?
  3. Combien y a-t-il d'injections de FF dans EE ?
Solution :(cliquer pour afficher)

1. D'après le théorème de dénombrement des applications,

Card⁡(FE)=(Card⁡F)Card⁡E=34=81.\operatorname{Card}\bigl(F^E\bigr)=(\operatorname{Card} F)^{\operatorname{Card} E}=3^4=81.

2. Aucune : une injection de EE dans FF imposerait Card⁡E⩽Card⁡F\operatorname{Card} E\leqslant\operatorname{Card} F, c'est-à-dire 4⩽34\leqslant 3, ce qui est faux. La réponse est 00.

3. Ici l'ensemble de départ est FF (de cardinal 33) et l'ensemble d'arrivée est EE (de cardinal 44) : la condition 3⩽43\leqslant 4 est remplie, et le nombre d'injections vaut

A43=4×3×2=24.A_4^3=4\times 3\times 2=24.

Les questions 2. et 3. montrent que le sens de l'application n'est pas indifférent : A43A_4^3 existe, A34A_3^4 n'existe pas.

Exercice 3

  1. Un groupe de 1212 élèves doit élire un président, un vice-président et un secrétaire (trois rôles distincts, un élève ne pouvant en occuper qu'un seul). Combien de bureaux différents peut-on former ?
  2. Dans un tournoi d'échecs à 88 participants, on souhaite attribuer les médailles d'or, d'argent et de bronze. De combien de façons peut-on le faire ?
Solution :(cliquer pour afficher)
  1. Il s'agit de compter les injections d'un ensemble à 33 éléments (les rôles) dans un ensemble à 1212 éléments (les élèves), soit
A123=12×11×10=1 320.A_{12}^{3}=12\times 11\times 10=1\,320.
  1. De même, on choisit un podium ordonné parmi 88 joueurs :
A83=8×7×6=336.A_8^3=8\times 7\times 6=336.