Chapitres Maths en MPSI, PCSI, MP2I, PTSI
Chapitres Maths en MPSI, PCSI, MP2I, PTSI
Cours : Dénombrements en Maths Sup
Résumé de cours Exercices et corrigés
Cours en ligne de Maths en Maths Sup
Résumé de cours et méthodes – Dénombrements en Maths Sup
Plan :
1. Démontrer qu’un ensemble est fini
2. Utiliser des ensembles finis dans des raisonnements
3. Récapitulatif des résultats
4. Quelle méthode utiliser ?
Retrouvez nos cours particuliers de maths à Paris en cas de lacune ou de perfectionnement de votre niveau en maths sup.
1. Pour démontrer qu’un ensemble est fini
Si est non vide, démontrer qu’il existe un entier et une bijection de sur .
Alors est unique et appelé cardinal de et noté .
.
Démontrer qu’il existe une bijection d’un ensemble fini sur .
Alors est fini et .
Démontrer que est une partie d’un ensemble fini .
Alors .
Démontrer que est la réunion de deux ensembles finis et
Si .
Si ,
.
Démontrer que avec et finis :
.
Plus généralement si et si où est fini, est fini et .
Exercice
Si sont trois parties de l’ensemble fini , calculer .
Démo : On utilise le cardinal d’une réunion de deux ensembles avec et et
.
On réutilise la formule donnant le cardinal de la réunion de deux ensembles et la relation :
.
et en réordonnant :
.
COURS DE MATHS A DOMICILE
Les meilleurs profs de maths pour
réussir sa scolarité
En ligne ou à domicile
Avis Google France ★★★★★ 4,9 sur 5
2. Utiliser des ensembles finis dans des raisonnements
Si et sont deux ensembles finis de même cardinal et est une application de dans ,
est bijective ssi est injective ssi est surjective.
Si et sont deux ensembles finis, pour démontrer que = , il suffit de prouver une inclusion et que et ont même cardinal.
Si est une partie de l’ensemble fini , son complémentaire est fini et .
3. Récapitulatif des résultats
Dans la suite, et sont des entiers non nuls et est un ensemble de cardinal .
est le nombre
de choix successifs avec remise de éléments de
de listes avec répétition de éléments de
d’applications de dans .
⚠️ l’ordre des éléments a de l’importance !
Si , est le nombre
de choix successifs sans remise de éléments de
de listes de éléments distincts de
d’applications injectives de dans .
⚠️ les éléments sont choisis les uns après les autres et les éléments choisis sont distincts.
Si , est le nombre
de choix simultanés sans remise de éléments de
de listes strictement croissantes de éléments de (h.p. voir dem plus bas )
de parties à éléments de (ou combinaisons).
⚠️ Les éléments sont choisis en même temps. Les éléments choisis n’ont pas d’ordre.
Exercice Nombre de listes strictement croissantes de éléments de .
Correction : On suppose et on note l’ensemble et l’ensemble des parties de à éléments.
L’application
est une bijection (toute partie finie peut être rangée d’une unique façon sous forme strictement croissante), donc .
Résultats à savoir démontrer :
si et ,
.
.
Correction :
Soit l’ensemble des parties de à éléments.
.
L’application
est une bijection (toute partie finie peut être rangée d’une unique façon sous forme strictement croissante), donc .
On écrit avec
Si est un ensemble fini de cardinal , est fini de cardinal .
En connaître 2 démonstrations :
Première démonstration.
Soit un ensemble fini à éléments.
On écrit
en notant l’ensemble des parties de à éléments.
On introduit ainsi une partition de
donc
par le binôme de Newton.
Deuxième démonstration.
Si , on note .
car .
Relation entre et .
Soit et .
On note
en notant
et
et sont disjoints.
donc .
est une bijection, donc
alors
donne
est une suite géométrique de raison 2 et de premier terme
alors .
Et une troisième démonstration.
On rappelle que l’on note la fonction indicatrice de l’ensemble .
L’application , est une bijection, donc
.
UN PROF DE MATHS POUR EXCELLER
La pratique et la compréhension
clés de la réussite
Cours de maths en ligne ou à domicile
Avis Google France ★★★★★ 4,9 sur 5
4. Quelle méthode utiliser ?
4.1. Règle du produit
Si l’on doit choisir un premier élément de façons, un deuxième élément de façons , … , et le – ième élément de façons,
le nombre de choix possibles est égal à .
c’est en effet le nombre d’éléments de où est l’ensemble dans lequel on choisit le -ème élément.
4.2. Utilisation d’une réunion
Si l’on doit choisir un élément vérifiant une propriété ou un élément vérifiant une propriété :
On note (resp ) l’ensemble des éléments vérifiant (resp ).
Dans le cas où il n’y a aucun élément vérifiant les propriétés et en même temps :
car .
Dans le cas où il y a des éléments vérifiant les propriétés et en même temps :
.
4.3. Utilisation d’une partition
Pour justifier , commencer par prouver que la famille est une partition de (parties non vides, deux à deux disjointes, de réunion égale à ).
Puis .
4.4. « avoir au moins un élément vérifiant une propriété «
Pour dénombrer un problème contenant un « au moins », en général il est plus simple de dénombrer le complémentaire (c’est le cas lorsque le complémentaire se traduit par « sans »).
Lorsque le nombre maximum d’éléments vérifiant la propriété est faible, on peut envisager de noter « avoir éléments vérifiant » et écrire , les ensembles étant deux à deux disjoints,
4.5. Calculer où et sont deux parties de et définie par « avoir au moins un élément vérifiant »
Utiliser
.
Les deux ensembles étant disjoints :
et utiliser
pour répondre à la question.
Les cours en ligne de Maths Sup sont parfaits pour prendre de l’avance en mathématiques en MPSI, PCSI et PTSI. Ainsi, vous pouvez accéder dès maintenant aux chapitres suivants :