Programme de mathématiques BCPST, première année · semestre 1
Outils 7 – Dénombrement
Rechercher dans cette partie du programmeTexte officiel du programme
Le but de ce chapitre est de mettre en place un vocabulaire efficace pour décrire (ou modéliser) et analyser les problèmes combinatoires, ainsi que quelques résultats fondamentaux associés. Les résultats de ce chapitre seront justifiés intuitivement, sans recours à des démonstrations formelles. De façon générale, on évitera tout excès de technicité dans les dénombrements.
Tous les ensembles considérés dans ce chapitre sont finis.
Dans les définitions qui suivent, on suppose que $\mathrm{card}(E) = n$.
| Contenus | Capacités et commentaires |
|---|---|
Cardinal, notation $\mathrm{card}(E)$ ou $\#E$. | On définit le cardinal grâce à la notion intuitive de nombre d’éléments. En particulier, deux ensembles en bijection ont même cardinal. |
Cardinal d’une union disjointe. Formule $\mathrm{card}(A \cup B) = \mathrm{card}A + \mathrm{card}B - \mathrm{card}(A \cap B)$. | |
Cardinal d’un produit cartésien. | $\mathrm{card}(E \times F)$ est aussi le nombre de façons de choisir de façon indépendante un élément de $E$ et un élément de $F$. |
Un élément de $E^p$ est appelé un $p$-uplet ou une $p$-liste de $E$. Il y a $n^p$ $p$-uplets de $E$. | $\mathrm{card}(E^p)$ est le nombre de façons de choisir successivement $p$ objets parmi $n$ objets distincts, avec d’éventuelles répétitions. |
Un $p$-uplet est dit sans répétition lorsque ses éléments sont distincts deux à deux. il y a $n(n-1)\cdots(n-p+1)$ $p$-uplets sans répétition de $E$. | Le nombre de $p$-uplets sans répétition est le nombre de façons de choisir successivement $p$ objets parmi $n$ objets distincts, sans répétition. |
Un $n$-uplet de $E$ contenant exactement une fois chaque élément de $E$ est appelé une permutation de $E$. Il y a $n!$ permutations de $E$. | $n!$ est le nombre de façons de choisir successivement tous les objets d’un ensemble, sans répétition. |
Si $p \leq n$, une $p$-combinaison de $E$ est une partie de $E$ à $p$ éléments. Il y a $\dbinom{n}{p}$ $p$-combinaisons de $E$. Cardinal de l’ensemble des parties de $E$. | $\dbinom{n}{p}$ est le nombre de façons de choisir simultanément $p$ objets parmi $n$ objets distincts. On peut sur cette base réinterpréter la formule du binôme. |
Calcul de probabilité
On jette 3 fois un dé à 6 faces, et on note \(a, b\) et \(c\) les résultats succe ...
exo7 129
Soit \(A= \{a_1, a_2, a_3, a_4\}\) et \(B= \{b_1, b_2, b_3, b_4 ,b_5\}\). Écrire ...
exo7 130
Soit \(E\) un ensemble à \(n\) éléments. Quel est le nombre d’éléments de ...
exo7 1392
Soit \(G\) un groupe fini de cardinal \(2n\) ( ...
exo7 2105
Soit \(n\) et \(p\) deux entiers, \(p\leq n\). D ...
exo7 2115
Soit \(G\) un groupe d’ordre pair. Montrer qu’il existe un élément \(x\in G\), ...
exo7 221
Démontrer que \(C_n^kC_{n-k}^{p-k}=C_p^kC_n^p\) (pour \(0\le k \le p \le n\)). En ...
exo7 223
Démontrer que \(C_n^p=C_{n-1}^p+C_{n-1}^{p-1}\) pour \(1\le p \le n-1\).
exo7 230
Démontrer les formules suivantes :
exo7 231
Soient \(E\) un ensemble non vide et \(X ,Y\) une partition de ...
exo7 232
Soit \(E\) un ensemble, \(a \in E\) et ...
exo7 236
Pour \(A,B\) deux ensembles de \(E\) on note ...
exo7 237
Soit \(E\) un ensemble à \(n\) éléments, et ...
exo7 238
Déterminer le nombre de mots distincts que l’on peut former avec \(6\) voyelles et ...
exo7 239
On considère les mains de \(5\) cartes que l’on peut extraire d’un jeu de \(52\) ...
exo7 240
Soient \(A,A' ,B ,B'\) quatre ensembles tels que : ...
exo7 241
Soient \(A\) et \(B\) deux sous ensembles finis d’un ensemble ...
exo7 242
Soient \(1 \leq k \leq n\). Déterminer le nombre de \(k\)-uplets ...
exo7 243
(principe des bergers) Soient \(E ,F\) deux ensembles avec ...
exo7 244
Montrer par récurrence sur \(n\) que si ...
exo7 245
Soit \(p_{n}(k)\) le nombre de permutations de \(\{1,...,n\}\) ayant ...
exo7 246
Soit \(E\) un ensemble de cardinal \(nm\in \Nn^{*}\), où ...
exo7 247
L’histoire: \(n\) personnes apportent chacune un cadeau à une fête, et chacun tire au sort un cadeau dans le tas f ...
exo7 2667
Soit \(n\in\N^*\). Calculer la somme des nombres d’inversions de toutes les permutations de ...
exo7 2903
Soit \(E\) un ensemble fini de cardinal \(n\). Calculer ...
exo7 2905
Soient \(n,p \in \N\). On note \(\Gamma_n^p\) le nombre de ...
exo7 2909
Soient \(a,b,c \in \N\). Démontrer que ...
exo7 2912
Combien y a-t-il de bijections \(f\) de \(\{1,\dots,12\}\) dans lui-mê ...
exo7 2913
On doit placer autour d’une table ronde un groupe de \(2n\) personnes, \(n\) homm ...
exo7 2915
Soient \(A_1, \dots, A_n\) \(n\) ensembles finis.
exo7 2916
Soient \(A_1, \dots, A_n\) \(n\) ensembles finis, et ...
exo7 2917
Soit \(E\) un ensemble fini à \(n\) élémen ...
exo7 2918
Quel est le nombre de parties à \(p\) éléments de ...
exo7 2923
Soient \(x_1,\dots,x_n\) \(n\) réels. Pour calculer la somme ...
exo7 2976
Soit \(G\) un groupe fini et \(H,K\) deux sous-groupes de ...
exo7 2986
Soit \(G\) un groupe n’ayant pas de sous-groupe non trivial. Montrer que \(G\) es ...
exo7 2990
Soit \(G\) un groupe fini tel que : \(\forall\ x \in G,\ x^2 = e\).
exo7 355
Un groupe de \(N\geq 2\) personnes se réunit. Montrer qu’au moins deux personnes ont serré le meme nombre de mains ...
exo7 3878
Soit \(f : {[a,b]} \to {\R}\) monotone. Pour \(x \in {]a,b[}\), on pose ...
exo7 4401
Pour \(n \in \N\) on pose ...
exo7 5278
(***) Trouver une démonstration combinatoire de l’identité \(\sum_{}^{}C_n^{2k}=\sum_{}^{}C_n^{2k+1}\) ou encore d ...
exo7 5279
Combien y a-t-il de partitions d’un ensemble à \(pq\) éléments en \(p\) classes a ...
exo7 5280
Combinaisons avec répétitions. Montrer que le nombre de solutions en nombres entiers \(x_i\geq0\) de l’équation ...
exo7 5281
Combien y a-t-il de nombres de \(5\) chiffres où \(0\) figure une fois et une seu ...
exo7 5282
Quelle est la probabilité \(p_n\) pour que dans un groupe de \(n\) personnes choi ...
exo7 5284
On part du point de coordonnées \((0,0)\) pour rejoindre le point de coordonnées ...
exo7 5285
De combien de façons peut-on payer \(100\) euros avec des pièces de \(10\), ...
exo7 5287
Combien y a-t-il de surjections de \(\{1,...,n+1\}\) sur \(\{1,...,n\}\) ?
exo7 5288
Soit \((P)\) un polygone convexe à \(n\) sommets. Combien ce polygone a-t-il de d ...
exo7 5290
Soit \(P_n^k\) le nombre de partitions d’un ensemble à \(n\) éléments en ...