BURHAN.

Nombre d'applications et de parties : Cours de Mathématiques 1BAC Sciences Mathématiques, chapitre Dénombrement

Nombre d'applications et de parties : notion du chapitre Dénombrement du programme de maths 1BAC SM, expliquée pas à pas, avec 2 exemples guidés. Pour les élèves de 1BAC Sciences Mathématiques, option française (BIOF).

Notions du cours (10)

Apprendre avec Burhan

Applications et parties d'un ensemble fini

Étape 1 sur 5

Une image pour chaque élément

Une application de EE dans FF associe à chaque élément de EE une image dans FF. Pour en fabriquer une, on choisit les images une à une. Par exemple, de {1,2}\{1, 2\} dans {a,b,c}\{a, b, c\} : 33 choix pour l'image de 11, puis 33 pour celle de 22. Cela fait 99 applications. Parmi ces 99 applications, 66 envoient 11 et 22 sur des éléments différents : on les appelle des injections. En notant (f(1),f(2))\big(f(1), f(2)\big), ce sont (a,b)(a, b), (a,c)(a, c), (b,a)(b, a), (b,c)(b, c), (c,a)(c, a) et (c,b)(c, b).

Devine : Des applications

Combien y a-t-il d'applications de E={1,2,3}E = \{1, 2, 3\} dans F={1,2,3,4}F = \{1, 2, 3, 4\} ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :1212

Faux.

3×43 \times 4 ne correspond à aucune suite de choix : chaque élément de EE a 44 images possibles.

Choix B :8181

Faux.

C'est 343^{4} : on a échangé les rôles de EE et de FF.

Choix C :2424

Faux.

Ce nombre ne compte que les applications injectives.

Choix D :6464

Juste.

Juste : 44 choix pour chacun des 33 éléments, soit 434^{3}.

Voir la correction complète

Une application est déterminée par les images de 11, de 22 et de 33. Chacune se choisit parmi les 44 éléments de FF, quels que soient les autres choix. D'après le principe multiplicatif, il y a 4×4×4=644 \times 4 \times 4 = 64 applications.

Continuer : Applications, injections, bijections →

Étape 2 sur 5

Applications, injections, bijections

Une application se résume à la liste de ses images. Pourquoi est-ce vrai ? La preuve met les applications en bijection avec les pp-listes d'images. Les injections correspondent alors aux listes sans répétition, c'est-à-dire aux arrangements.

PropriétéNombre d'applications, d'injections, de bijections

Soit EE et FF deux ensembles finis non vides, p=card(E)p = \mathrm{card}(E) et n=card(F)n = \mathrm{card}(F). On note F(E,F)\mathcal{F}(E, F) l'ensemble des applications de EE dans FF.

  • card(F(E,F))=np\mathrm{card}(\mathcal{F}(E, F)) = n^{p}.
  • Si p≤np \leq n, le nombre d'applications injectives de EE dans FF est AnpA_{n}^{p} ; si p>np > n, aucune application de EE dans FF n'est injective.
  • Si p=np = n, toute injection de EE dans FF est une bijection, et le nombre de bijections de EE sur FF est n!n!.

Démonstration

Étape 1. Écrivons E={x1,…,xp}E = \{x_1, \dots, x_p\}, les xix_i étant deux à deux distincts. L'application f↦(f(x1),…,f(xp))f \mapsto \big(f(x_1), \dots, f(x_p)\big) est une bijection de F(E,F)\mathcal{F}(E, F) sur FpF^{p} : une application est déterminée par les images des xix_i, et toute pp-liste en définit une. Par cardinal et bijection et le nombre de pp-listes, card(F(E,F))=np\mathrm{card}(\mathcal{F}(E, F)) = n^{p}.

Étape 2. Comme les xix_i sont distincts, ff est injective si et seulement si la pp-liste associée est un arrangement. Si p≤np \leq n, cette bijection envoie les injections sur les arrangements : il y a AnpA_{n}^{p} injections.

Étape 3. Si ff est injective, ff est une bijection de EE sur f(E)f(E), donc card(f(E))=p\mathrm{card}(f(E)) = p (cardinal et bijection) ; comme f(E)⊂Ff(E) \subset F, p≤np \leq n (cardinal du complémentaire) : si p>np > n, aucune injection. Si p=np = n, le cas d'égalité donne f(E)=Ff(E) = F : ff est bijective. Réciproquement, toute bijection est injective : il y a donc Ann=n!A_{n}^{n} = n! bijections (nombre d'arrangements).

À retenirCe qu'il faut retenir de la preuve

Le geste clé : une application, c'est la liste de ses images. Compter des applications revient à compter des pp-listes, et compter des injections, des arrangements. Le dernier point, « injective donc bijective » quand p=np = n, vient du cas d'égalité de la formule du complémentaire : si f(E)f(E) a autant d'éléments que FF, alors f(E)=Ff(E) = F.

Vérifie : Aucune injection

Dans la preuve, pourquoi n'existe-t-il aucune injection de EE dans FF lorsque p>np > n ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :Une injection ff donne card(f(E))=p\mathrm{card}(f(E)) = p, et f(E)⊂Ff(E) \subset F impose p≤np \leq n.

Juste.

Juste : une partie de FF a au plus nn éléments.

Choix B :Parce que AnpA_{n}^{p} vaut 00 quand p>np > n.

Faux.

AnpA_{n}^{p} n'est pas défini pour p>np > n : la preuve raisonne sur les cardinaux.

Choix C :Parce qu'on l'a vérifié sur un exemple.

Faux.

Un exemple ne prouve pas un énoncé général.

Choix D :Parce qu'une injection doit toujours être surjective.

Faux.

Une injection n'est pas forcément surjective : l'identité de {1,2}\{1, 2\}, vue de {1,2}\{1, 2\} dans {1,2,3}\{1, 2, 3\}, est injective sans être surjective.

Voir la correction complète

Si ff est injective, ff est une bijection de EE sur f(E)f(E). D'après le résultat sur les bijections, card(f(E))=p\mathrm{card}(f(E)) = p. Or f(E)f(E) est une partie de FF : d'après la formule du complémentaire, p≤np \leq n. Si p>np > n, aucune injection n'existe.

← Étape précédenteContinuer : Exemples et piège →

Étape 3 sur 5

Exemples et piège

Exemplede petits ensembles

  • De {1,2,3}\{1, 2, 3\} dans {a,b}\{a, b\}, il y a 23=82^{3} = 8 applications. Note chacune par la liste (f(1),f(2),f(3))\big(f(1), f(2), f(3)\big) : (a,a,a)(a, a, a), (a,a,b)(a, a, b), (a,b,a)(a, b, a), (a,b,b)(a, b, b), (b,a,a)(b, a, a), (b,a,b)(b, a, b), (b,b,a)(b, b, a), (b,b,b)(b, b, b). Aucune n'est injective, car 3>23 > 2.
  • De {1,2,3}\{1, 2, 3\} dans {1,2,3,4}\{1, 2, 3, 4\}, il y a A43=24A_{4}^{3} = 24 injections.
  • Les bijections de {1,2,3}\{1, 2, 3\} sur lui-même sont au nombre de 3!=63! = 6.

Attentionqui est en exposant ?

✗ « De {1,2,3,4}\{1, 2, 3, 4\} dans {1,2,3}\{1, 2, 3\}, il y a 43=644^{3} = 64 applications. »

✓ On choisit une image dans l'ensemble d'arrivée pour chaque élément de départ. Ici, 44 éléments de départ ont chacun 33 images possibles : 34=813^{4} = 81 applications. L'exposant est le cardinal de l'ensemble de départ.

← Étape précédenteContinuer : Nombre de parties →

Étape 4 sur 5

Nombre de parties

Pour former une partie de EE, on décide, élément par élément : dedans ou dehors ? Pourquoi est-ce vrai ? Ce « oui ou non » est une application de EE dans {0,1}\{0, 1\}. La preuve en fait une bijection, puis compte les parties selon leur nombre d'éléments.

PropriétéNombre de parties d'un ensemble fini

Soit EE un ensemble fini de cardinal nn. Alors card(P(E))=2netCn0+Cn1+⋯+Cnn=2n.\mathrm{card}(\mathcal{P}(E)) = 2^{n} \quad \text{et} \quad C_{n}^{0} + C_{n}^{1} + \dots + C_{n}^{n} = 2^{n}.

Démonstration

Étape 1. Si n=0n = 0, P(∅)={∅}\mathcal{P}(\varnothing) = \{\varnothing\} a 1=201 = 2^{0} élément, et C00=1C_{0}^{0} = 1. Supposons n≥1n \geq 1. À toute partie AA de EE, associons χA:E→{0,1}\chi_A : E \to \{0, 1\}, qui vaut 11 sur AA et 00 sur A‾\overline{A} (complémentaire dans EE).

Étape 2. A↦χAA \mapsto \chi_A est une bijection de P(E)\mathcal{P}(E) sur F(E,{0,1})\mathcal{F}(E, \{0, 1\}), de réciproque g↦g−1({1})g \mapsto g^{-1}(\{1\}) : en effet, χA−1({1})=A\chi_A^{-1}(\{1\}) = A et, comme gg ne prend que les valeurs 00 et 11, χg−1({1})=g\chi_{g^{-1}(\{1\})} = g. Par cardinal et bijection et le nombre d'applications, card(P(E))=2n\mathrm{card}(\mathcal{P}(E)) = 2^{n}.

Étape 3. Toute partie de EE est finie, de cardinal unique (résultat admis), compris entre 00 et nn (cardinal du complémentaire). Les ensembles de parties à pp éléments, 0≤p≤n0 \leq p \leq n, ont CnpC_{n}^{p} éléments, sont deux à deux disjoints, de réunion P(E)\mathcal{P}(E). Le principe additif donne Cn0+⋯+Cnn=2nC_{n}^{0} + \dots + C_{n}^{n} = 2^{n}.

À retenirCe qu'il faut retenir de la preuve

Une partie AA de EE est codée par χA\chi_A : 11 pour les éléments de AA, 00 pour les autres. Ce codage est une bijection, donc P(E)\mathcal{P}(E) a autant d'éléments que F(E,{0,1})\mathcal{F}(E, \{0, 1\}). Puis, en rangeant les parties selon leur cardinal, le principe additif donne la somme des CnpC_{n}^{p}.

Vérifie : Décoder une partie

Dans la preuve, quelle partie de EE la réciproque associe-t-elle à une application gg de EE dans {0,1}\{0, 1\} ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :L'ensemble g−1({0})g^{-1}(\{0\}) des éléments d'image 00.

Faux.

C'est le complémentaire de la bonne partie : χA\chi_A vaut 11 sur AA.

Choix B :L'image directe g(E)g(E).

Faux.

g(E)g(E) est une partie de {0,1}\{0, 1\}, pas de EE.

Choix C :L'ensemble g−1({1})g^{-1}(\{1\}) des éléments d'image 11.

Juste.

Juste : si g=χAg = \chi_A, alors g−1({1})=Ag^{-1}(\{1\}) = A.

Choix D :L'ensemble EE tout entier.

Faux.

Une seule partie pour toutes les applications : ce ne serait pas une bijection.

Voir la correction complète

La réciproque associe à gg la partie g−1({1})g^{-1}(\{1\}), formée des éléments que gg envoie sur 11. Pour g=χAg = \chi_A, on retrouve AA. C'est l'image réciproque du chapitre « Ensembles et applications ».

← Étape précédenteContinuer : À toi →

Étape 5 sur 5

À toi

Exempleparties de petits ensembles

  • P({1,2,3})\mathcal{P}(\{1, 2, 3\}) contient ∅\varnothing, {1}\{1\}, {2}\{2\}, {3}\{3\}, {1,2}\{1, 2\}, {1,3}\{1, 3\}, {2,3}\{2, 3\} et {1,2,3}\{1, 2, 3\} : 23=82^{3} = 8 parties. Rangées selon leur cardinal : 1+3+3+1=81 + 3 + 3 + 1 = 8.
  • Pour {1,2,3,4}\{1, 2, 3, 4\} : C40+C41+C42+C43+C44=1+4+6+4+1=16=24C_{4}^{0} + C_{4}^{1} + C_{4}^{2} + C_{4}^{3} + C_{4}^{4} = 1 + 4 + 6 + 4 + 1 = 16 = 2^{4}.

À toi : Des parties sous condition

Soit E={1,2,3,4}E = \{1, 2, 3, 4\}. (a) Combien de parties de EE contiennent 11 ? (b) Combien ont au moins deux éléments ? Écris ta réponse avant de dévoiler la correction.

Besoin d'aide ? Indice 1

Pour (a), une partie qui contient 11 s'écrit {1}∪B\{1\} \cup B, avec BB partie de {2,3,4}\{2, 3, 4\}.

Encore bloqué ? Indice 2

Pour (b), compte plutôt les parties à 00 ou 11 élément.

Encore bloqué ? Indice 3

Point délicat : pour (a), vérifie que B↦{1}∪BB \mapsto \{1\} \cup B est une bijection, de réciproque A↦A∖{1}A \mapsto A \setminus \{1\}.

Voir la solution complète

(a) L'application B↦{1}∪BB \mapsto \{1\} \cup B va de P({2,3,4})\mathcal{P}(\{2, 3, 4\}) dans l'ensemble des parties de EE qui contiennent 11. Elle est bijective, de réciproque A↦A∖{1}A \mapsto A \setminus \{1\}. D'après le résultat sur les bijections, il y a 23=82^{3} = 8 telles parties.

(b) EE a 24=162^{4} = 16 parties. Celles qui ont moins de deux éléments sont ∅\varnothing et les 44 singletons. Par le complémentaire, 16−1−4=1116 - 1 - 4 = 11 parties ont au moins deux éléments.

← Étape précédenteFin de la notion

S'entraîner sur cette notion

Sources du cours

  • Référentiel BURHAN du chapitre « Dénombrement » (1bac · sciences-mathematiques · mathematiques)