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 5Une image pour chaque élément
Une application de dans associe à chaque élément de une image dans . Pour en fabriquer une, on choisit les images une à une. Par exemple, de dans : choix pour l'image de , puis pour celle de . Cela fait applications. Parmi ces applications, envoient et sur des éléments différents : on les appelle des injections. En notant , ce sont , , , , et .
Devine : Des applications

Combien y a-t-il d'applications de dans ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :
Faux.
ne correspond à aucune suite de choix : chaque élément de a images possibles.
Choix B :
Faux.
C'est : on a échangé les rôles de et de .
Choix C :
Faux.
Ce nombre ne compte que les applications injectives.
Choix D :
Juste.
Juste : choix pour chacun des éléments, soit .
Voir la correction complète
Une application est déterminée par les images de , de et de . Chacune se choisit parmi les éléments de , quels que soient les autres choix. D'après le principe multiplicatif, il y a applications.
Étape 2 sur 5Applications, 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 -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 et deux ensembles finis non vides, et . On note l'ensemble des applications de dans .
- .
- Si , le nombre d'applications injectives de dans est ; si , aucune application de dans n'est injective.
- Si , toute injection de dans est une bijection, et le nombre de bijections de sur est .
Démonstration
Étape 1. Écrivons , les étant deux à deux distincts. L'application est une bijection de sur : une application est déterminée par les images des , et toute -liste en définit une. Par cardinal et bijection et le nombre de -listes, .
Étape 2. Comme les sont distincts, est injective si et seulement si la -liste associée est un arrangement. Si , cette bijection envoie les injections sur les arrangements : il y a injections.
Étape 3. Si est injective, est une bijection de sur , donc (cardinal et bijection) ; comme , (cardinal du complémentaire) : si , aucune injection. Si , le cas d'égalité donne : est bijective. Réciproquement, toute bijection est injective : il y a donc 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 -listes, et compter des injections, des arrangements. Le dernier point, « injective donc bijective » quand , vient du cas d'égalité de la formule du complémentaire : si a autant d'éléments que , alors .

Vérifie : Aucune injection

Dans la preuve, pourquoi n'existe-t-il aucune injection de dans lorsque ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :Une injection donne , et impose .
Juste.
Juste : une partie de a au plus éléments.
Choix B :Parce que vaut quand .
Faux.
n'est pas défini pour : 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 , vue de dans , est injective sans être surjective.
Voir la correction complète
Si est injective, est une bijection de sur . D'après le résultat sur les bijections, . Or est une partie de : d'après la formule du complémentaire, . Si , aucune injection n'existe.
Étape 3 sur 5Exemples et piège
Exemplede petits ensembles
- De dans , il y a applications. Note chacune par la liste : , , , , , , , . Aucune n'est injective, car .
- De dans , il y a injections.
- Les bijections de sur lui-même sont au nombre de .

Attentionqui est en exposant ?
✗ « De dans , il y a applications. »
✓ On choisit une image dans l'ensemble d'arrivée pour chaque élément de départ. Ici, éléments de départ ont chacun images possibles : applications. L'exposant est le cardinal de l'ensemble de départ.

Étape 4 sur 5Nombre de parties
Pour former une partie de , on décide, élément par élément : dedans ou dehors ? Pourquoi est-ce vrai ? Ce « oui ou non » est une application de dans . 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 un ensemble fini de cardinal . Alors
Démonstration
Étape 1. Si , a élément, et . Supposons . À toute partie de , associons , qui vaut sur et sur (complémentaire dans ).
Étape 2. est une bijection de sur , de réciproque : en effet, et, comme ne prend que les valeurs et , . Par cardinal et bijection et le nombre d'applications, .
Étape 3. Toute partie de est finie, de cardinal unique (résultat admis), compris entre et (cardinal du complémentaire). Les ensembles de parties à éléments, , ont éléments, sont deux à deux disjoints, de réunion . Le principe additif donne .

À retenirCe qu'il faut retenir de la preuve
Une partie de est codée par : pour les éléments de , pour les autres. Ce codage est une bijection, donc a autant d'éléments que . Puis, en rangeant les parties selon leur cardinal, le principe additif donne la somme des .

Vérifie : Décoder une partie

Dans la preuve, quelle partie de la réciproque associe-t-elle à une application de dans ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :L'ensemble des éléments d'image .
Faux.
C'est le complémentaire de la bonne partie : vaut sur .
Choix B :L'image directe .
Faux.
est une partie de , pas de .
Choix C :L'ensemble des éléments d'image .
Juste.
Juste : si , alors .
Choix D :L'ensemble 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 à la partie , formée des éléments que envoie sur . Pour , on retrouve . C'est l'image réciproque du chapitre « Ensembles et applications ».
Étape 5 sur 5À toi
Exempleparties de petits ensembles
- contient , , , , , , et : parties. Rangées selon leur cardinal : .
- Pour : .

À toi : Des parties sous condition

Soit . (a) Combien de parties de contiennent ? (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 s'écrit , avec partie de .
Encore bloqué ? Indice 2
Pour (b), compte plutôt les parties à ou élément.
Encore bloqué ? Indice 3
Point délicat : pour (a), vérifie que est une bijection, de réciproque .
Voir la solution complète
(a) L'application va de dans l'ensemble des parties de qui contiennent . Elle est bijective, de réciproque . D'après le résultat sur les bijections, il y a telles parties.
(b) a parties. Celles qui ont moins de deux éléments sont et les singletons. Par le complémentaire, parties ont au moins deux éléments.
← Étape précédenteFin de la notion
S'entraîner sur cette notion
- Applications et parties de petits ensembles · niveau application
- Identités sur les coefficients binomiaux et parties de cardinal pair · niveau entraînement
- Applications sous contrainte, parties contenant deux éléments donnés · niveau entraînement
- Couples de parties emboîtées · niveau examen
- Points fixes et involutions · niveau examen
- Le principe des tiroirs · niveau perfectionnement
Sources du cours
- Référentiel BURHAN du chapitre « Dénombrement » (1bac · sciences-mathematiques · mathematiques)
