MPSI · Dénombrement

Propriétés du cardinal

Palier 0Palier 1Palier 1+Palier 2

Union disjointe et parties

Question

Compter un ensemble, c'est le mettre en bijection avec un segment d'entiers — un travail à reprendre intégralement pour chaque nouvel ensemble. Peut-on en faire l'économie lorsque l'ensemble se décompose en morceaux déjà comptés ? Commençons par le cas le plus simple : deux paquets n'ayant aucun élément en commun.

Proposition 1

Si AA et BB sont des ensembles finis d'union disjointe, alors A⊔BA\sqcup B est fini et

Card⁡(A⊔B)=Card⁡A+Card⁡B.\operatorname{Card}(A\sqcup B)=\operatorname{Card} A+\operatorname{Card} B.

Remarque :

Preuve intuitive. Si AA possède pp éléments et BB en possède qq, on compte de 11 à pp les éléments de AA, puis de p+1p+1 à p+qp+q ceux de BB : au lieu de repartir de 11 pour compter les éléments de BB, on poursuit le comptage à la suite de ceux de AA.

Démonstration :

  • Premier cas. Si A=∅A=\varnothing ou B=∅B=\varnothing, le résultat est trivial.
  • Deuxième cas. Par définition du cardinal, il existe deux bijections φ1:A→⟦1,p⟧\varphi_1:A\to\llbracket 1,p\rrbracket et φ2:B→⟦1,q⟧\varphi_2:B\to\llbracket 1,q\rrbracket. On définit alors
ψ:{A⊔B→⟦1,p+q⟧x↦{φ1(x)si x∈A,φ2(x)+psi x∈B.\psi:\left\{ \begin{aligned} &A\sqcup B \to \llbracket 1,p+q\rrbracket\\ &x\mapsto \begin{cases} \varphi_1(x) & \text{si } x\in A,\\ \varphi_2(x)+p & \text{si } x\in B. \end{cases} \end{aligned}\right.

Cette application ψ\psi est injective. Soient x≠x′x\neq x' dans A⊔BA\sqcup B.

  • Si x,x′∈Ax,x'\in A, alors ψ(x)=φ1(x)≠φ1(x′)=ψ(x′)\psi(x)=\varphi_1(x)\neq\varphi_1(x')=\psi(x') par injectivité de φ1\varphi_1.
  • Si x,x′∈Bx,x'\in B, alors φ2(x)≠φ2(x′)\varphi_2(x)\neq\varphi_2(x') par injectivité de φ2\varphi_2, donc ψ(x)≠ψ(x′)\psi(x)\neq\psi(x').
  • Si x∈Ax\in A et x′∈Bx'\in B (ou l'inverse), alors ψ(x)∈⟦1,p⟧\psi(x)\in\llbracket 1,p\rrbracket tandis que ψ(x′)∈⟦p+1,p+q⟧\psi(x')\in\llbracket p+1,p+q\rrbracket : ces deux segments sont disjoints, donc ψ(x)≠ψ(x′)\psi(x)\neq\psi(x').

Elle est aussi surjective :

  • si y∈⟦1,p⟧y\in\llbracket 1,p\rrbracket, alors φ1−1(y)∈A⊂A⊔B\varphi_1^{-1}(y)\in A\subset A\sqcup B est un antécédent de yy par ψ\psi ;
  • si y∈⟦p+1,p+q⟧y\in\llbracket p+1,p+q\rrbracket, alors φ2−1(y−p)∈B⊂A⊔B\varphi_2^{-1}(y-p)\in B\subset A\sqcup B est un antécédent de yy par ψ\psi.

Donc ψ\psi est bijective, d'où Card⁡(A⊔B)=p+q=Card⁡A+Card⁡B\operatorname{Card}(A\sqcup B)=p+q=\operatorname{Card} A+\operatorname{Card} B.

Exemple :

Dans ⟦1,10⟧\llbracket 1,10\rrbracket, les entiers pairs et les entiers impairs forment deux paquets sans élément commun dont la réunion est ⟦1,10⟧\llbracket 1,10\rrbracket tout entier : il y en a 55 de chaque, et l'on retrouve bien 5+5=105+5=10. Sur ⟦1,2n⟧\llbracket 1,2n\rrbracket, le partage serait-il encore aussi équilibré ? Comment le démontrer ?

Test 1 : Sans hypothèse de disjonction

Si AA et BB sont deux ensembles finis, alors Card⁡(A∪B)=Card⁡A+Card⁡B\operatorname{Card}(A\cup B)=\operatorname{Card} A+\operatorname{Card} B.

Exercice 1 : Union disjointe d'une famille finie

Soient m∈N∗m\in\mathbb{N}^* et A1,A2,…,AmA_1,A_2,\dots,A_m des ensembles finis deux à deux disjoints. Montrer que leur réunion est finie et que

Card⁡(⨆i=1mAi)=∑i=1mCard⁡(Ai).\operatorname{Card}\left(\bigsqcup_{i=1}^{m}A_i\right)=\sum_{i=1}^{m}\operatorname{Card}(A_i).
Solution :(cliquer pour afficher)

Par récurrence sur m∈N∗m\in\mathbb{N}^*.

Initialisation. Pour m=1m=1, l'égalité s'écrit Card⁡(A1)=Card⁡(A1)\operatorname{Card}(A_1)=\operatorname{Card}(A_1).

Hérédité. Supposons le résultat acquis au rang mm et donnons-nous A1,…,Am+1A_1,\dots,A_{m+1} finis, deux à deux disjoints. Posons B=⨆i=1mAiB=\displaystyle\bigsqcup_{i=1}^{m}A_i : par hypothèse de récurrence, BB est fini et Card⁡(B)=∑i=1mCard⁡(Ai)\operatorname{Card}(B)=\sum_{i=1}^{m}\operatorname{Card}(A_i).

Vérifions que B∩Am+1=∅B\cap A_{m+1}=\varnothing. Si xx appartenait à cette intersection, il existerait i∈⟦1,m⟧i\in\llbracket 1,m\rrbracket tel que x∈Aix\in A_i, et l'on aurait x∈Ai∩Am+1x\in A_i\cap A_{m+1} avec i≠m+1i\neq m+1, ce qui contredit la disjonction deux à deux.

La proposition s'applique donc au couple (B,Am+1)(B,A_{m+1}) :

Card⁡(⨆i=1m+1Ai)=Card⁡(B)+Card⁡(Am+1)=∑i=1m+1Card⁡(Ai).\operatorname{Card}\left(\bigsqcup_{i=1}^{m+1}A_i\right)=\operatorname{Card}(B)+\operatorname{Card}(A_{m+1})=\sum_{i=1}^{m+1}\operatorname{Card}(A_i).

Conclusion. Le résultat est vrai pour tout m∈N∗m\in\mathbb{N}^*.

Question

Une partie d'un ensemble fini est-elle automatiquement finie ? L'intuition répond oui sans hésiter, mais la définition, elle, ne donne rien : elle fournit une bijection entre EE et un segment ⟦1,n⟧\llbracket 1,n\rrbracket, et rien ne dit qu'une partie AA de EE hérite d'une bijection avec un segment. Il faut donc le démontrer — et il suffira de le faire sur le cas modèle E=⟦1,n⟧E=\llbracket 1,n\rrbracket, auquel tout ensemble fini se ramène.

Lemme 1

Soit nn un entier naturel non nul. Toute partie de ⟦1,n⟧\llbracket 1,n\rrbracket est finie et de cardinal inférieur ou égal à nn.

Démonstration :

Par récurrence sur nn.

  • Pour n=1n=1, le sous-ensemble est soit vide, soit égal à ⟦1,n⟧\llbracket 1,n\rrbracket tout entier ; dans les deux cas, il est fini et de cardinal inférieur ou égal à nn.
  • Supposons le résultat vrai pour un n⩾1n\geqslant 1 fixé, et considérons E⊂⟦1,n+1⟧E\subset\llbracket 1,n+1\rrbracket.
    • Si n+1∉En+1\notin E, alors E⊂⟦1,n⟧E\subset\llbracket 1,n\rrbracket ; par hypothèse de récurrence, EE est finie et Card⁡(E)⩽n⩽n+1\operatorname{Card}(E)\leqslant n\leqslant n+1.
    • Si n+1∈En+1\in E, on pose E′=E∖{n+1}E'=E\setminus\{n+1\}, partie de ⟦1,n⟧\llbracket 1,n\rrbracket. Alors E′E' est finie et Card⁡(E′)=p⩽n\operatorname{Card}(E')=p\leqslant n. Comme E=E′⊔{n+1}E=E'\sqcup\{n+1\}, on obtient Card⁡(E)=Card⁡(E′)+1=p+1⩽n+1\operatorname{Card}(E)=\operatorname{Card}(E')+1=p+1\leqslant n+1.

Par principe de récurrence, le résultat est vrai pour tout n∈Nn\in\mathbb{N}.

Proposition 2 : Cardinal d'une partie

Soient EE un ensemble fini et A⊂EA\subset E. Alors AA est fini et Card⁡A⩽Card⁡E\operatorname{Card} A\leqslant\operatorname{Card} E, avec égalité si et seulement si A=EA=E.

Remarque :

Cette propriété est très utile pour remplacer un raisonnement par double inclusion : il suffit de montrer une seule inclusion et l'égalité des cardinaux (finis) pour conclure à l'égalité des ensembles.

Démonstration :

Si E=∅E=\varnothing, le résultat est clair. Sinon, Card⁡E=n⩾1\operatorname{Card} E=n\geqslant 1 et il existe une bijection φ:E→⟦1,n⟧\varphi:E\to\llbracket 1,n\rrbracket. Alors φ(A)\varphi(A) est un sous-ensemble de ⟦1,n⟧\llbracket 1,n\rrbracket (par croissance de l'image directe), donc fini avec Card⁡φ(A)⩽n\operatorname{Card}\varphi(A)\leqslant n (lemme précédent). Or Card⁡(A)=Card⁡(φ(A))\operatorname{Card}(A)=\operatorname{Card}(\varphi(A)) puisque φ\varphi est une bijection, d'où Card⁡(A)⩽n\operatorname{Card}(A)\leqslant n.

Cas d'égalité. Le sens réciproque est évident. Pour le sens direct, si Card⁡A=Card⁡E\operatorname{Card} A=\operatorname{Card} E, alors φ(A)=⟦1,n⟧=φ(E)\varphi(A)=\llbracket 1,n\rrbracket=\varphi(E) ; comme φ\varphi est bijective, A=EA=E.

Exercice 2 : Le cas d'égalité, autrement

Soient EE un ensemble fini et A⊂EA\subset E tels que Card⁡A=Card⁡E\operatorname{Card} A=\operatorname{Card} E. En écrivant E=A⊔(E∖A)E=A\sqcup(E\setminus A), redémontrer que A=EA=E.

Solution :(cliquer pour afficher)

Les deux parties AA et E∖AE\setminus A de EE sont finies d'après la proposition précédente, et elles sont disjointes de réunion EE. La proposition sur l'union disjointe donne donc

Card⁡E=Card⁡A+Card⁡(E∖A),\operatorname{Card} E=\operatorname{Card} A+\operatorname{Card}(E\setminus A),

d'où Card⁡(E∖A)=0\operatorname{Card}(E\setminus A)=0 puisque Card⁡A=Card⁡E\operatorname{Card} A=\operatorname{Card} E.

Or un ensemble de cardinal 00 est en bijection avec ⟦1,0⟧=∅\llbracket 1,0\rrbracket=\varnothing, donc il est vide. Ainsi E∖A=∅E\setminus A=\varnothing, c'est-à-dire E⊂AE\subset A. Avec l'inclusion A⊂EA\subset E de l'énoncé, on conclut A=EA=E.

Test 2 : Une inclusion et deux cardinaux

Soient EE un ensemble fini et AA une partie de EE telle que Card⁡A=Card⁡E\operatorname{Card} A=\operatorname{Card} E. Alors A=EA=E.

Complémentaire et crible

Question

Compter les éléments qui vérifient une propriété, ou compter ceux qui ne la vérifient pas : ce sont deux faces d'un même comptage. Souvent l'une des deux est nettement plus facile que l'autre — combien d'entiers de ⟦1,100⟧\llbracket 1,100\rrbracket ne sont pas divisibles par 77 ? Que coûte exactement le passage de l'un à l'autre ?

Proposition 3 : Cardinal du complémentaire

Si EE est un ensemble fini et A⊂EA\subset E, alors

Card⁡A‾=Card⁡E−Card⁡A,\operatorname{Card}\overline{A}=\operatorname{Card} E-\operatorname{Card} A,

où A‾\overline{A} désigne le complémentaire de AA dans EE, c'est-à-dire E∖AE\setminus A.

Remarque :

Les éléments de A‾\overline{A} sont tous les éléments de EE, sauf ceux de AA.

Démonstration :

On a E=A‾⊔AE=\overline{A}\sqcup A et cette union est disjointe, donc Card⁡E=Card⁡(A‾)+Card⁡A\operatorname{Card} E=\operatorname{Card}(\overline{A})+\operatorname{Card} A.

Question

La formule de l'union disjointe exige que AA et BB n'aient aucun élément commun. Que devient-elle si les deux ensembles se recouvrent ? Autrement dit : les seuls nombres Card⁡A\operatorname{Card} A et Card⁡B\operatorname{Card} B suffisent-ils encore à déterminer Card⁡(A∪B)\operatorname{Card}(A\cup B), et sinon, quelle information manque-t-il ?

Théorème 1 : Formule du crible

Si AA et BB sont des ensembles finis, alors A∪BA\cup B est fini et

Card⁡(A∪B)=Card⁡A+Card⁡B−Card⁡(A∩B).\operatorname{Card}(A\cup B)=\operatorname{Card} A+\operatorname{Card} B-\operatorname{Card}(A\cap B).

Remarque :

Contrairement à l'union disjointe, il y a ici des éléments communs aux deux ensembles réunis : il existe des doublons, qu'il ne faut compter qu'une seule fois dans l'union. Lorsqu'on calcule Card⁡A+Card⁡B\operatorname{Card} A+\operatorname{Card} B, on compte chacun de ces doublons deux fois ; il faut donc les retrancher une fois pour obtenir le bon dénombrement, où Card⁡(A∩B)\operatorname{Card}(A\cap B) désigne précisément le nombre de doublons.

Démonstration :

On écrit A∪B=A⊔(B∖(A∩B))A\cup B=A\sqcup\bigl(B\setminus(A\cap B)\bigr), union disjointe, d'où

Card⁡(A∪B)=Card⁡A+Card⁡(B∖(A∩B))=Card⁡A+Card⁡B−Card⁡(A∩B).\operatorname{Card}(A\cup B)=\operatorname{Card} A+\operatorname{Card}\bigl(B\setminus(A\cap B)\bigr)=\operatorname{Card} A+\operatorname{Card} B-\operatorname{Card}(A\cap B).

Test 3 : Crible à trois ensembles

Si AA, BB et CC sont trois ensembles finis, alors

Card⁡(A∪B∪C)=Card⁡A+Card⁡B+Card⁡C−Card⁡(A∩B∩C).\operatorname{Card}(A\cup B\cup C)=\operatorname{Card} A+\operatorname{Card} B+\operatorname{Card} C-\operatorname{Card}(A\cap B\cap C).

Exercice 3 : Divisibilité dans un segment

On note E=⟦1,100⟧E=\llbracket 1,100\rrbracket, puis AA l'ensemble des éléments de EE divisibles par 22 et BB celui des éléments de EE divisibles par 55.

  1. Déterminer Card⁡A\operatorname{Card} A, Card⁡B\operatorname{Card} B et Card⁡(A∩B)\operatorname{Card}(A\cap B).
  2. Combien d'entiers de EE sont divisibles par 22 ou par 55 ?
  3. Combien d'entiers de EE ne sont divisibles ni par 22, ni par 55 ?
Solution :(cliquer pour afficher)

1. Soit d∈{2,5,10}d\in\{2,5,10\}. Les multiples de dd contenus dans ⟦1,100⟧\llbracket 1,100\rrbracket sont exactement les entiers dkdk pour k∈⟦1,100/d⟧k\in\llbracket 1,100/d\rrbracket, et l'application k↦dkk\mapsto dk est une bijection de ⟦1,100/d⟧\llbracket 1,100/d\rrbracket sur cet ensemble (elle est injective car d≠0d\neq 0, et surjective par construction). Le cardinal cherché vaut donc 100/d100/d :

Card⁡A=50,Card⁡B=20.\operatorname{Card} A=50,\qquad \operatorname{Card} B=20.

Un entier est divisible par 22 et par 55 si et seulement s'il est divisible par 1010 (car 22 et 55 sont premiers entre eux), donc A∩BA\cap B est l'ensemble des multiples de 1010 de EE et Card⁡(A∩B)=10\operatorname{Card}(A\cap B)=10.

2. Les entiers divisibles par 22 ou par 55 forment A∪BA\cup B. La formule du crible donne

Card⁡(A∪B)=50+20−10=60.\operatorname{Card}(A\cup B)=50+20-10=60.

3. Les entiers cherchés forment le complémentaire de A∪BA\cup B dans EE, d'où

Card⁡A∪B‾=Card⁡E−Card⁡(A∪B)=100−60=40.\operatorname{Card}\overline{A\cup B}=\operatorname{Card} E-\operatorname{Card}(A\cup B)=100-60=40.

Produit cartésien

Question

Jusqu'ici, on a découpé un ensemble pour le compter : union disjointe, partie, complémentaire, crible. Mais un couple (x,y)(x,y) ne se découpe pas — il se fabrique, par deux choix successifs et indépendants. Combien de couples peut-on former de la sorte, et le comptage se ramène-t-il encore à une addition ?

Proposition 4 : Cardinal d'un produit cartésien

Si EE et FF sont des ensembles finis, alors E×FE\times F est fini et

Card⁡(E×F)=Card⁡E×Card⁡F.\operatorname{Card}(E\times F)=\operatorname{Card} E\times\operatorname{Card} F.

Remarque :

On peut interpréter le cardinal du produit cartésien comme une aire : si l'on place les éléments de EE sur un axe et ceux de FF sur un autre, le cardinal du produit cartésien correspond à la surface délimitée par EE et FF. La formule est « longueur ×\times largeur ». Cela se généralise à un plus grand nombre d'ensembles ; par exemple, le produit cartésien de trois ensembles correspond à un volume :

Card⁡(E×F×G)=Card⁡E×Card⁡F×Card⁡G.\operatorname{Card}(E\times F\times G)=\operatorname{Card} E\times\operatorname{Card} F\times\operatorname{Card} G.

Démonstration :

On note Card⁡E=n\operatorname{Card} E=n et on procède par récurrence sur le cardinal de FF.

  • Si Card⁡F=0\operatorname{Card} F=0, alors E×FE\times F est vide et son cardinal est nul : la propriété est bien initialisée.
  • On suppose le résultat vrai pour Card⁡F=p\operatorname{Card} F=p et on considère un ensemble F′F' de cardinal p+1p+1, que l'on écrit F′={x1,…,xp,xp+1}=F⊔{xp+1}F'=\{x_1,\dots,x_p,x_{p+1}\}=F\sqcup\{x_{p+1}\} avec F={x1,…,xp}F=\{x_1,\dots,x_p\} de cardinal pp. Les éléments de E×F′E\times F' sont les couples (ai,xj)(a_i,x_j) avec ai∈Ea_i\in E et j∈⟦1,p+1⟧j\in\llbracket 1,p+1\rrbracket, donc
E×F′=(E×F)⊔(E×{xp+1}),E\times F'=\bigl(E\times F\bigr)\sqcup\bigl(E\times\{x_{p+1}\}\bigr),

union disjointe. Ainsi

Card⁡(E×F′)=Card⁡(E×F)+Card⁡(E×{xp+1})=np+Card⁡(E×{xp+1})\operatorname{Card}(E\times F')=\operatorname{Card}(E\times F)+\operatorname{Card}(E\times\{x_{p+1}\})=np+\operatorname{Card}(E\times\{x_{p+1}\})

par hypothèse de récurrence. Or E×{xp+1}E\times\{x_{p+1}\} est de cardinal nn, car l'application φ:ai↦(ai,xp+1)\varphi:a_i\mapsto(a_i,x_{p+1}) est une bijection de EE sur E×{xp+1}E\times\{x_{p+1}\}. Donc Card⁡(E×F′)=np+n=n(p+1)=Card⁡E×Card⁡F′\operatorname{Card}(E\times F')=np+n=n(p+1)=\operatorname{Card} E\times\operatorname{Card} F', ce qui démontre l'hérédité.

  • Conclusion. Par principe de récurrence, pour tous ensembles finis EE et FF, Card⁡(E×F)=Card⁡E×Card⁡F\operatorname{Card}(E\times F)=\operatorname{Card} E\times\operatorname{Card} F.

Test 4 : Un facteur vide

La formule Card⁡(E×F)=Card⁡E×Card⁡F\operatorname{Card}(E\times F)=\operatorname{Card} E\times\operatorname{Card} F reste valable lorsque l'un des deux ensembles est vide.

Corollaire 1

Soient EE un ensemble fini et p∈N∗p\in\mathbb{N}^*. Alors Card⁡(Ep)=(Card⁡E)p\operatorname{Card}(E^p)=(\operatorname{Card} E)^p.

Démonstration :

Notons n=Card⁡En=\operatorname{Card} E et procédons par récurrence sur p∈N∗p\in\mathbb{N}^*.

Initialisation. Pour p=1p=1, on a E1=EE^1=E et Card⁡(E1)=n=n1\operatorname{Card}(E^1)=n=n^1.

Hérédité. Supposons Card⁡(Ep)=np\operatorname{Card}(E^p)=n^p pour un p∈N∗p\in\mathbb{N}^* fixé. L'application

Φ:{Ep×E→Ep+1((x1,…,xp), xp+1)↦(x1,…,xp,xp+1)\Phi:\left\{ \begin{aligned} &E^p\times E\to E^{p+1}\\ &\bigl((x_1,\dots,x_p),\,x_{p+1}\bigr)\mapsto (x_1,\dots,x_p,x_{p+1}) \end{aligned}\right.

est bijective : elle est injective car deux (p+1)(p+1)-uplets égaux ont les mêmes composantes, et surjective car tout (x1,…,xp+1)∈Ep+1(x_1,\dots,x_{p+1})\in E^{p+1} est l'image de ((x1,…,xp),xp+1)\bigl((x_1,\dots,x_p),x_{p+1}\bigr). La proposition précédente donne alors

Card⁡(Ep+1)=Card⁡(Ep×E)=Card⁡(Ep)×Card⁡(E)=np×n=np+1.\operatorname{Card}(E^{p+1})=\operatorname{Card}(E^p\times E)=\operatorname{Card}(E^p)\times\operatorname{Card}(E)=n^p\times n=n^{p+1}.

Conclusion. Le résultat est vrai pour tout p∈N∗p\in\mathbb{N}^*.

Remarque :

Un pp-uplet s'écrit (x1,x2,…,xp)∈Ep(x_1,x_2,\dots,x_p)\in E^p. Pour x1x_1, on dispose de nn possibilités (autant que d'éléments dans EE). Pour chaque choix de x1x_1, on a nn possibilités pour x2x_2, soit n×n=n2n\times n=n^2 possibilités pour (x1,x2)(x_1,x_2). Pour chaque choix de (x1,x2)(x_1,x_2), on a encore nn possibilités pour x3x_3, soit n3n^3 possibilités, et ainsi de suite. C'est le « volume » d'un hypercube de dimension pp et de côté n=Card⁡En=\operatorname{Card} E.

Test 5 : Puissance ou multiple ?

Si EE est un ensemble fini de cardinal nn, alors Card⁡(E3)=3n\operatorname{Card}(E^3)=3n.

Exercice 4

Un cadenas à code comporte 33 molettes, chacune offrant 1010 positions de 00 à 99. Combien y a-t-il de codes possibles ?

Solution :(cliquer pour afficher)

Notons E=⟦0,9⟧E=\llbracket 0,9\rrbracket l'ensemble des positions d'une molette : Card⁡E=10\operatorname{Card} E=10.

Un code est entièrement déterminé par la position de chacune des trois molettes, prises dans l'ordre : c'est donc un triplet (a1,a2,a3)(a_1,a_2,a_3) d'éléments de EE. L'application qui à un code associe ce triplet est une bijection de l'ensemble des codes sur E3E^3.

D'après le corollaire,

Card⁡(E3)=(Card⁡E)3=103=1 000.\operatorname{Card}(E^3)=(\operatorname{Card} E)^3=10^3=1\,000.

Il y a donc 1 0001\,000 codes possibles.