Logo Groupe Réussite
Groupe Réussite
  • Cours particuliers
    • Cours maths
    • Cours anglais
    • Cours physique chimie
    • Cours français
    • Cours informatique
  • Stages intensifs
  • Donner cours
  • 01 84 88 32 69

Cours en ligne Maths en Maths Spé

Chapitres Maths en MP, PSI, PC, TSI, PT

Équivalents
Algèbre linéaire et matrices
Séries numériques
Espaces vectoriels
Réduction endomorphismes
Matrices
Espaces vectoriels normés
Suites et séries de fonctions
Intégration intervalle quelconque
Séries entières
Dénombrement
Intégrales à paramètre
Variables aléatoires
Probabilités
Espaces préhilbertiens
Espaces euclidiens
Fonctions de variables
Courbes paramétrées
Équations différentielles linéaires
Familles sommables
À savoir démontrer
CONTACTEZ-NOUS

Cours en ligne Maths en Maths Spé

Chapitres Maths en MP, PSI, PC, TSI, PT

Équivalents
Algèbre linéaire et matrices
Séries numériques
Espaces vectoriels
Réduction endomorphismes
Matrices
Espaces vectoriels normés
Suites et séries de fonctions
Intégration intervalle quelconque
Séries entières
Dénombrement
Intégrales à paramètre
Variables aléatoires
Probabilités
Espaces préhilbertiens
Espaces euclidiens
Fonctions de variables
Courbes paramétrées
Équations différentielles linéaires
Familles sommables
À savoir démontrer
CONTACTEZ-NOUS

Dénombrements en MP, PC, PSI et PT

Résumé de cours Exercices et corriges

Exercices et corrigés – Dénombrements

1. Ensembles dénombrables

Exercice 1 :

Soit f une fonction croissante de \mathbb{R} dans \mathbb{R}. Montrer que l’ensemble des points de discontinuité de f est au plus dénombrable.

Corrigé de l’exercice 1 :

Soit A l’ensemble des points de discontinuité de f.
En tout point a \in A, f admet une limite à gauche f (a - 0) et une limite à droite f(a + 0) telles que f(a - 0) < f(a + 0).
\mathbb{Q} étant dense dans \mathbb{R}, il existe r \in \mathbb{Q} tel que f(a - 0) < r < f(a + 0).
On définit ainsi une application \varphi : A \to \mathbb{Q},\; a \mapsto r injective.
Comme \mathbb{Q} est dénombrable, il existe une bijection \psi de \mathbb{Q} sur \mathbb{N} donc une injection \psi \circ \varphi de A dans \mathbb{N}.
On en déduit que A est finie ou dénombrable.

Exercice 2 : 

Soit E = \{0 , 1\}^{\mathbb{N}} l’ensemble des suites d’éléments égaux à 0 ou 1.
Question 1 
E est dénombrable ?

Question 2
On note D l’ensemble des éléments de E qui sont des 0 à partir d’un certain rang.
D est dénombrable ?

Question 3
L’ensemble E' des suites périodiques de E est dénombrable ?

Corrigé de l’exercice 2 :

Question 1 :

Si E était dénombrable, il existerait une bijection \varphi de \mathbb{N} dans E.
On définit alors la suite u = (u_n)_n par u_n = 0 si \varphi(n)_n = 1 et u_n = 1 si \varphi(n)_n = 0.
On obtient un élément u de E et pour tout p \in \mathbb{N},\;  u_p \neq \varphi_p(p), donc la contradiction avec \varphi bijective.

Question 2
On note D'_0 = \{(0 ,\, \cdots \, 0 , \, \cdots )\}, D_0 = \{(\omega_0 , \, 1 ,\, \cdots \, 0 , \, \cdots )\, / \, \omega_0 = 0 \textrm { ou } 1\}
et si n \geq  1, \;D_n l’ensemble des éléments de E  dont le terme d’indice n est égal à 1, les termes d’indices supérieurs ou égaux à n + 1 sont des 0.
L’application \varphi_n : D_n \to \{0 , 1\}^{n }, (\omega_k)_{k \in \mathbb{N} } \mapsto (\omega_0 ,\, \cdots \, , \, \omega_{n - 1} ) est bijective.

Comme \{0 , 1\}^{n} est fini, D_n est fini.
D est la réunion dénombrable des ensembles finis D_n et de l’ensemble D'_0\,, donc D est fini ou dénombrable.
D contient une famille infinie : (X_n)_n  où X_n est la suite formée de n 1 suivis de 0.

Donc D est dénombrable.

Question 3

On note \mathcal{P}_n l’ensemble des éléments de E périodiques de période n  \in \mathbb{N}^*.
Si n \in \mathbb{N}^*, à tout élément x de \mathcal{P}_n on associe l’élément de \mathbb{N} ^n égal à  (x_0 \, ,\, \cdots \, , \, x_{n - 1} ).
On définit ainsi une application bijective de \mathcal{P}_n dans \{0 , \, 1\} ^{n} car une suite périodique de période n est entièrement définie par ses n premiers éléments.
\# \mathcal{P}_n = 2^n
E' est une réunion dénombrable d’ensembles finis, donc E' est fini ou dénombrable.
E' contient une famille infinie à savoir la famille (X_n)_n où X_n est la  suite périodique de période n dont les n premiers éléments sont 1 , \, \cdots\, , \, 1 , \, 0
(n - 1 éléments 1 suivis de 0).
Donc E' est dénombrable.

Exercice 3 : 

Question 1
Montrer que l’ensemble des parties finies de \mathbb{N} est dénombrable.

Question 2
L’ensemble des parties de \mathbb{N} n’est pas dénombrable ?

Corrigé de l’exercice 3 : 

Question 1 : 

On note \mathcal {P} l’ensemble des parties finies non vides de \mathbb{N}.
On note \mathcal {P} _ n l’ensemble des parties finies de \mathbb{N} de cardinal n.

\bullet Première méthode
On considère \mathcal{P}_n \to \mathbb{N}^n , \{a_1 ,\, \cdots\, , \, a_n\} \mapsto (a_1 ,\, \cdots\, ,\, a_n) (les a_i étant rangés par ordre strictement croissant).
\varphi_n est une application injective. Donc \mathcal{P}_n est fini ou dénombrable.

\mathcal{P}_n n’est pas fini car il contient l’ensemble infini \{ [\![k , \, k + n - 1 ]\!] \, / \,  k \in \mathbb{N} \}. donc \mathcal{P}_n est dénombrable.
Les ensembles \mathcal{P}_n forment une partition de \mathcal{P} et sont dénombrables, donc par réunion dénombrable d’ensembles dénombrables, \mathcal{P} est un ensemble dénombrable.

\bullet Deuxième méthode
On note \mathcal{Q}_n l’ensemble des parties finies de \mathbb{N} dont le plus grand élément est égal à n.
Se donner un élément de \mathcal{Q}_n revient à se donner une partie de [\![0 , n - 1]\!] et à lui ajouter l’élément n.
Donc \# \mathcal{Q}_n = 2 ^ n (car le nombre de parties de [\![0 , n - 1]\!] est égal à 2^n).

Les ensembles \mathcal{Q}_n forment une partition de \mathcal{P} et sont finis, donc par réunion dénombrable d’ensembles finis, \mathcal{P} est un ensemble dénombrable ou fini.
\mathcal{P} contient la famille infinie (\{n\})_{n \in \mathbb{N}} , donc \mathcal{P} est dénombrable.

Question 2

On suppose que l’ensemble \mathcal{Q} des parties non vides de \mathbb{N} est dénombrable.
Il existe donc une application \Phi de \mathbb{N} dans \mathcal{Q} bijective.
Pour tout n \in \mathbb{N}, on note A_n = \Phi(n).
On note B la partie de \mathbb{N} définie ainsi : n \in B \Leftrightarrow n \notin A_n\,.
B est une partie de \mathbb{N}. Il existe donc p \in \mathbb{N} tel que B = \Phi(p) = A_p\,.
Or si p \in A_p \,, \,b \notin B et si p \notin A_p\, ,\; b \in B, donc B \neq A_p\, . On aboutit à une contradiction.

L’ensemble des parties non vides de \mathbb{N} est non dénombrable. Il en est de même de l’ensemble des parties de \mathbb{N}.

Exercice 4 : 

Soit (I_a)_{a \in A} une famille d’intervalles ouverts non vides et 2 à 2 disjoints de \mathbb{R}.
A est au plus dénombrable ?

Corrigé de l’exercice 4 : 

En utilisant la densité de \mathbb {Q}, pour tout a \in A, il existe r_a \in I_a \cap \mathbb{Q}.
Si a \neq b, r_a \neq r_b car I_a \cap I_b = \varnothing.
On définit ainsi une injection f : A \to \mathbb{Q}.
Comme il existe une bijection \varphi : \mathbb{Q} \to \mathbb{N}, \varphi \circ f est une injection de A dans \mathbb{N}, alors A est fini ou dénombrable.

 

COURS DE MATHS

Les meilleurs professeurs particuliers

Pour progresser et réussir

Cours particuliers maths

Avis Google France ★★★★★ 4,9 sur 5

 

2. Exercies sur les dénombrements en maths spé

Exercice 5 :

On tire 5 cartes d’un jeu de 32 cartes. Quel est le nombre de mains contenant 2 as ?

Corrigé de l’exercice 5 :

On choisit 2 as parmi 4 de \displaystyle \binom {4} {2} = 6 façons.
Puis on choisit 3 cartes parmi les 32 - 4 = 28 cartes sans as de \displaystyle \binom {28} {3} = 3\, 276 façons.
Le nombre de mains contenant deux as est égal à 6 . 3276 = 19\, 656.

Exercice 6 :

Quel est le nombre de mains de 4 cartes d’un jeu de 32 cartes contenant 2 rois ou 3 dames ?

Corrigé de l’exercice 6 :

On ne peut pas avoir deux rois et trois dames en même temps dans une main de 4 cartes.
On note R l’ensemble des mains contenant 2 Rois et D l’ensemble des mains contenant 3 dames.

\ast \# R = 6 . 14 . 27
car on choisit 2 rois parmi 4 de \displaystyle \binom {4} {2} = 6 façons puis 2 cartes parmi les 28 qui restent de \displaystyle \binom {28} {2} = 14 . 27 façons.

\ast \# D = 4 . 28
car on choisit 3 dames parmi 4 de \displaystyle \binom {4} {3} = 4 façons puis 1 carte parmi les 28 qui restent de 28 façons.

\# (R \cup D) = \#R + \#D = 2 \, 380 car R \cap D = \varnothing.

Aviez-vous pensé à écrire que les deux ensembles sont disjoints ?

Exercice 7 :

Quel est le nombre de mains de 4 cartes contenant 2 rois ou 3 trèfles d’un jeu de 32 cartes ?

Corrigé de l’exercice 7 :

On peut obtenir une main contenant le roi de trèfle.
Soit R l’ensemble des mains contenant 2 rois et T l’ensemble des mains de 4 cartes contenant 3 trèfles.

\ast \# R = 6 . 14 . 27
car on choisit 2 rois parmi 4 de \displaystyle \binom {4} {2} = 6 façons puis 2 cartes parmi les 28 qui restent de \displaystyle \binom {28} {2} = 14 . 27 façons.

\ast \# T = 56 . 24
car on choisit 3 trèfles parmi 8 de \displaystyle \binom {8} {3} = 56 façons puis 1 carte parmi les 24 qui restent de 24 façons.

\ast \# R \cap T = 3 . 21
C’est l’ensemble des mains contenant le roi de trèfle, un autre roi et 2 autres trèfles.
On choisit un roi qui n’est pas de trèfle (3 choix), deux trèfles différents du roi de \displaystyle \binom {7} {2} = 21 façons.

\# (R \cup T) = \# R + \# T - \# (R \cap T)
\#R = 6 . 14 . 27 + 56 . 24 - 3 . 21 = 3 \,549.

Exercice 8 :

Soit E un ensemble de cardinal n. Soit A l’ensemble des parties de E ayant un nombre pair d’éléments.
Déterminer \# A.

Corrigé de l’exercice 8 :

On note p = \lfloor n / 2 \rfloor (la partie entière de n/2).

Si k \in [[0 , \,p]], on note A_k l’ensemble des parties de E à 2 \,k éléments.
La famille (A_k)_{0 \leq k \leq p} forme une partition de A.
Donc \displaystyle \# A = \sum _{k = 0} ^p \# A_k = \sum _ {k = 0} ^{p} {\binom {n} {2 \,k}}
\#A = 2 ^{n - 1} (pour le calcul de la somme, voir l’exercice 3 du §2.4. dans la partie méthodes).

Exercice 9
Soient a,\, b et n trois entiers naturels non nuls avec n \leq a + b.
En utilisant un raisonnement de dénombrement, démontrer la formule de Vandermonde :
\displaystyle \binom {a+b} {n} = \sum_{ k = \max(0 ,  n - b)}^{\min(a , \,n)}\binom {a} {k} \, \binom {b} {n- k}.

Corrigé de l’exercice 9 :

Soient A = [[1 ,\, a]] et B = [[ a + 1 , \, b + a]].
A et B sont disjoints et ont respective- ment a et b éléments. E = A \cup B = [[1 , \, a + b]].
\bullet On note \mathcal{P}_n(E) l’ensemble des parties de E ayant n éléments. \quad \quad \quad \displaystyle \# \mathcal{P}_n(E) = \binom {a + b} {n}.

\bullet On note E_k l’ensemble des parties de E formées de k éléments dans A et n - k dans B.
L’ensemble E_k est non vide
ssi 0 \leq k \leq a et 0 \leq n - k \leq b
ssi k \geq 0 \textrm{ et } k \geq n - b , \; k \leq a \textrm{ et } k \leq n.
Les ensembles (E_k) _{\max(0 , \, n - b) \leq k \leq \min(a , \, n)} forment une partition de \mathcal{P}_n(E).
\#E_k = \displaystyle \binom {a} {k} \, \binom {b} {n - k} car on doit choisir k éléments parmi a et n - k éléments parmi b.

\bullet \displaystyle \# \mathcal{P}_n(E) = \sum _ {k = \max(0 , n - b)} ^{\min(a , n)} \# \,E_k
soit \displaystyle \binom {a+b} {n} = \sum_{ k = \max(0 , n -b)}^{\min(a , n)}\binom {a} {k} \, \binom {b} {n- k}.

D’autres chapitres de mathématiques peuvent être révisés par les étudiants en CPGE, en se rendant sur les pages de cours en ligne de Maths en Maths Spé. Sont accessibles, les cours en ligne de Maths en PC, la page de cours en ligne de Maths en MP et la page de cours en ligne de Maths en PSI.

 

COURS PARTICULIERS EN LIGNE

Nous avons sélectionné pour vous les meilleurs professeurs particuliers.

POUR ACCÉLÉRER MA PROGRESSION

Cours particuliers en ligne

Avis Google France ★★★★★ 4,9 sur 5

 

2. Exercices sur les les surjections en maths spé

Exercice 10 :

Si N \in \mathbb{N}^*, on note E_N = [\![1 , \, N]\!].
Soient n et p deux entiers naturels non nuls. On note S(n , \, p) le nombre de surjections de E_n dans E_p.

Question 1 
Donner les valeurs de S(n,\, n) et de S(n ,\, p) si n < p.

Question 2
Calculer S(n , \, 2).

Question 3
Calculer S(n , \, 3).

Question 4
Calculer S(n + 1 , \, n).

Question 5
Si p \geq 1,
S(n ,\, p) = \quad \quad  p(S(n - 1 ,\, p) + S(n - 1 ,\, p - 1)).

Question 6
Montrer que k ^n =\displaystyle \sum _{k = 1} ^ p \binom {p} {k} S(n ,\,  k)

Question 7
Si q\leq k \leq p,
\displaystyle \binom {p} {k} \, \binom {k} {q} est égal à \displaystyle \binom {p} {q} \, \binom {p - q} {k - q}

Corrigé de l’exercice 10 : 

Question 1 :

\ast Une application de E_n dans lui-même est une surjection ssi elle est bijective, donc S(n,\, n) = n!.
\ast Il n’y a aucune surjection de E_n dans E_p lorsque p > n car une application de E_n dans E_p a au plus n images distinctes.

Question 2 :

Une application de E_n dans E_2 est surjective ssi elle n’est pas constante. Il y a 2 ^n applications de E_n dans E_2 et deux applications constantes, donc S(n ,\, 2) = 2^n - 2. 

Question 3

On note A l’ensemble des applications de E_n dans E_3\,.  \# A = 3^n.
On forme une partition de A de la façon suivante :
\ast A_1 est l’ensemble des applications constantes : il y en a 3.
\ast A_2 est l’ensemble des applications dont l’image est une partie à deux éléments.
Pour définir un élément de A_2\,, on se donne une partie de E_3 à deux éléments (ce qui se fait de \displaystyle \binom {3}{2} = 3 façons). Puis on définit une application surjective de E_n dans cet ensemble. En utilisant la question 2, il y a 2^n - 2 applications de ce type.
Donc \# A_2 = 3(2 ^n - 2).
\ast A_3 est l’ensemble des surjections.

Comme \#A = \#A_1 + \#A_2 + \#A_3\,,  on en déduit que  \#A_3 = 3^n - 3(2^n - 2) - 3.

Question 4 :

Pour définir une surjection de E_{n + 1} dans E_n
\ast on choisit l’élément a de E_n ayant deux antécédents : il y a n choix pour a.
\ast on se donne les deux éléments x_1 , \, x_2 de E_{n + 1} d’image égale à a : il y a \displaystyle \binom {n + 1} {2} = \frac {n(n + 1)} 2 choix.
\ast on définit une surjection (donc une bijection) de E_{n + 1} \setminus \{x_1 , \, x_2 \} dans E_n \setminus \{ a\} ce qui se fait de (n - 1)! façons.
Donc \displaystyle S(n + 1 , \, n) = n . \frac {n(n + 1)} 2 . (n-1)! \displaystyle S(n + 1, \, n) = \frac {n \, (n + 1)!} 2.

Question 5 :

On note \mathbb {S} (n ,\, p) l’ensemble des surjections de E_n dans E_p\,.
On écrit que \mathbb {S} (n ,\, p) = \mathcal {A} \cup \mathcal {B} où
\mathcal {A} est l’ensemble des surjections f de E_n dans E_p telles que la restriction de f à E_{n - 1} soit une surjection de E_{n - 1} sur E_p et \mathcal{B} est l’ensemble des surjections f de E_n dans E_{p} telles que cette restriction ne soit pas surjective .

\bullet Se donner un élément f de \mathcal{A} revient à se donner une surjection g de E_{n - 1} dans E_p et à donner f(n + 1) quelconque dans E_p (p choix pour f(n + 1)) donc \# \mathcal{A} = p \, S(n ,\, p - 1).

\bullet Pour définir un élément f de \mathcal{B},
\ast on définit la restriction f' de f à E_{n -1}\,, un seul élément a de E_p n’est pas atteint par f', on choisit cet élément (p choix), puis on définit f' qui est une surjection de E_{n - 1} sur E_p \setminus \{ a \} ce qui se fait de S(n - 1 , p - 1) façons
\ast puis on définit f(p + 1) = a.
Donc \#B = p . S(n - 1 , \, p - 1)

\ast Comme \mathcal{A} et \mathcal{B} sont incompatibles :
\# \, \mathcal{S}( n , p) = \# \, \mathcal {A} + \# \,\mathcal {B}
S(n , \, p) = p \, S(n - 1 , p) + p \, S(n - 1 ,\, p - 1 ).

Question 6 :

Si k \in [\![1 ,\, p]\!] , on note A_k l’ensemble des applications f de E_n dans E_p telles que \# f(E_n) = k.
On forme ainsi une partition de l’ensemble \mathcal {F } (E_n \, ,\, E_p), ensemble des applications de E_n dans E_p\,.
Donc \# \mathcal {F } (E_n\, , \, E_p) = \displaystyle \sum _ {k = 1} ^{p} \# A_k\,.

Se donner un élément f de A_k revient à se donner une partie G de E_p ayant k éléments (de \displaystyle \binom {p} {k} façons) puis à définir une application surjective de E_n dans G ce qui se fait de S(n , \,k) façons.
donc \displaystyle \# A_k = \binom {p} {k} \, S(n, \, k).
On obtient donc p^n = \displaystyle \sum _{k = 1} ^ p \binom {p} {k} S(n , \, k).

Question 7 :

Si q\leq k \leq p,
\alpha = \displaystyle \binom {p} {k} \, \binom {k} {q} = \frac {p!} {k! \, (p - k)!} \, \frac {k!} {q! \, (k - q)!}
\displaystyle \alpha = \frac {p!} {q! \, (p - q)! } \, \frac {(p - q)!} {(p - k)! \, (k - q)!}
soit \displaystyle \binom {p} {k} \, \binom {k} {q} = \displaystyle \binom {p} {q} \, \binom {p - q} {k - q}.

4. Exercices sur les mots de Dyck

On appelle  » mot de Dyck » une chaîne de 2 n caractères, n \in \mathbb{N}^*, formée de n lettres A et n lettres B, telle que, lorsque l’on dénombre les lettres de gauche à droite, en s’arrêtant à une lettre du mot, le nombre de A soit toujours supérieur ou égal au nombre de B. Ainsi, le seul mot de Dyck de longueur 2 est : AB. Les mots de Dyck de longueur 4 sont : AABB et ABAB.
ABAABB et AAABBB sont des mots de Dyck, alors que BA et AABBBA n’en sont pas.
Pour tout entier n \geq 1, on désigne par C_n le nombre de mots de Dyck de 2 n lettres.

Question 1
Calculer C_1\, , \, C_2\, , \, C_3 \, , \, C_4\,.

Question 2 
On pose : C_0 = 1. Montrer que, pour tout entier n > 1, \displaystyle C_n = \sum _{k = 1 } ^{n - 1} C_{k - 1} \, C_{n - k }

Question 3
Montrer que C_{n} = \displaystyle \frac 1 {n + 1} \, \binom {2 n} {n}.

👍 C_n est appelé le n-ième nombre de Catalan.

Question 4 : Une application 
Une particule se déplace sur une droite graduée en partant de l’origine et en se déplaçant à chaque minute d’une unité vers la droite ou vers la gauche.
Le nombre de façons de revenir pour la première fois à l’instant 2 n + 2 en O est égal à a \, C_{n}\,

Si toutes les réponses à ces exercices sont correctes, il faut désormais passer aux entraînements sur les annales. Mais, si vous souhaitez vous entraîner sur d’autres exercices de cours en ligne, vous avez le choix. Quelques idées de chapitres au programme de Maths Spé :

  • les intégrales à paramètre
  • les variables aléatoires
  • les probabilités
  • les espaces préhilbertiens
  • les espaces euclidiens

Contact

  • 3 rue de l'Estrapade 75005 Paris
  • contact@groupe-reussite.fr
  • 01 84 88 32 69
Qui sommes-nous ?
  • Témoignages et avis
  • Notre équipe
Nous rejoindre
  • Devenir professeur particulier
Copyright @ GROUPE REUSSITE - Mentions légales
groupe-reussite.fr est évalué 4,9/5 par 1049 clients sur Google France