Exercices de dénombrement

Ressources

Cours

Méthodologie

Ensembles finis

Exercice
Soient E et F deux ensembles finis non vides. Montrer que si Card(E) ≤ Card(F) alors il existe une injection de E dans F.
Exercice
Montrer que tout ensemble infini admet au moins une partie stricte infinie.
On peut enlever un point et montrer que ce qui reste est infini par l’absurde.
Exercice
Calculer le nombre d’applications qui ne sont pas injectives entre deux ensembles finis non vides.
On peut calculer d’abord le nombre d’applications qui sont injectives.
Exercice
Soit E un ensemble fini de cardinal nN. Combien y a-t-il de couples (A, B) de parties de E tels que AB = ∅ ? tels que AB = E ? Combien y a-t-il de paires {A, B} de parties de E tels que AB = ∅ ?
D’après C. Degrave et D. Degrave, Probabilités et statistiques, Bréal 1990, énoncé 105
Exercice
Pour tout (n, p) ∈ (N)2, on note Sn, p le nombre de surjections de ⟦1 ; n sur ⟦1 ; p.
  1. Montrer que pour tout (n, p) ∈ (N)2 tel que n < p on a Sn, p = 0.
  2. Pour tout nN, calculer Sn, n, Sn, 1, Sn, 2 et Sn+1, n.
  3. Montrer que pour tout (n, p) ∈ (N)2 on a pn = k=1n (kp) Sn, k.

Groupes d’élèves

Exercice
Les 38 élèves de la classe font une course. De combien de manières peuvent se répartir les trois premières places ?
Exercice
On choisit aléatoirement quatre élèves distincts d'une classe de 46, de façon équiprobable.
  1. Combien y a-t-il de combinaisons possibles ? Si vous êtes élève de cette classe, combien y a-t-il de combinaisons qui vous contiennent ?
  2. Le lendemain, on choisit à nouveau quatre élèves distincts en suivant le même procédé, donc en gardant la possibilité qu'un élève choisi la veille soit choisi à nouveau. Calculer le nombre de tirages possibles sur les deux jours ainsi que le nombre de tirages sans répétition.
  3. Reprendre les questions précédentes en supposant cette fois qu'on note l'ordre dans lequel les élèves sont choisis chaque jour.
Exercice
On souhaite répartir les 38 élèves de la classe en binômes de façon à ce que dans chaque binôme, les deux élèves proviennent de séries différentes. Il y a 3 élèves issus de la série L, 17 élèves issus de la série ES et 18 élèves issus de la série S.
  1. Montrer qu’il est nécessaire d’apparier les trois élèves issus de L avec deux élèves issus de S et un élève issu de ES.
  2. Calculer le nombre de manières de choisir quel élève issu de L ira avec un élève issu de ES, puis calculer le nombre de manières de compléter ces trois binômes.
  3. Pour chaque répartition des trois élèves issus de L, calculer le nombre de manières de répartir les élèves restants.
  4. En déduire le nombre de partitions de toute la classe en binômes d’élèves issus de séries différentes.

Chiffres et lettres

Exercice
Dans l’ensemble des entiers à exactement 6 chiffres, dénombrer
Exercice
Soit n et k deux entiers naturels non nuls.
  1. Dénombrer les suites de k entiers dans ⟦1 ; n qui soient strictement croissantes.
  2. Si (un) est une suite de nombres entiers naturels, montrer qu’elle est croissante si et seulement si la suite (un + n) est strictement croissante.
  3. En déduire le nombre de suites de 6 chiffres qui soient croissantes dans ⟦1 ; 9⟧.
Exercice
Soit (p, n) ∈ (N)2 tel que pn. Combien y a-t-il de combinaisons de p éléments dans ⟦1 ; n qui ne contiennent pas deux entiers consécutifs ?
C. Degrave et D. Degrave, Probabilités et statistiques, Bréal 1990, énoncé 106
Exercice
Pour tout (n, k) ∈ (N)2, le nombre d'entiers strictement positifs et inférieurs à n qui sont divisibles par  k s'écrit n/k.
  1. Calculer le nombre d'entiers entre 1 et 100 qui sont divisibles par 2 (respectivement par 3, par 5, par 7).
  2. Pour tout ensemble S ⊂ {2 ; 3 ; 5 ; 7} non vide, calculer le nombre d'entiers entre 1 et 100 qui sont divisibles par tous les éléments de S.
  3. En déduire le nombre d'entiers entre 1 et 100 qui sont divisibles par l'un au moins des éléments de {2 ; 3 ; 5; 7}.
  4. Tous les autres entiers entre 1 et 100 sont des nombres premiers, à l'exception de 1. Calculer le nombre de nombres premiers inférieurs à 100.
Exercice
Combien de codes de trois lettres peut-on former de façon à alterner voyelles et consonnes ?
Exercice
En utilisant seulement les lettres a et b, combien peut-on écrire de mots (avec ou sans signification) de 10 lettres ? de 2n lettres (avec nN*) ? et en imposant que chacune de ces deux lettres apparaisse autant de fois dans le mot ?
Exercice
En assimilant un mot à une liste de lettres, une anagramme d’un mot m = l1l2ln est un mot de même longueur dans lequel chaque lettre apparait autant de fois que dans le mot m. Par exemple, le mot « label » est une anagramme de « balle ». On considère ici tous les anagrammes possibles, qu’ils aient une signification ou non (« aebll » est aussi une anagramme de « balle »).
  1. Calculer le nombre d’anagrammes différentes du mot « nombre ».
  2. Calculer le nombre d’anagrammes différentes du mot « somme ».
    On pourra calculer d’abord le nombre d’emplacements possible pour les deux lettres « m ».
  3. Calculer le nombre d’anagrammes différentes du mot « anagramme ».

Jeux

Exercice
Un domino comporte deux nombres entiers (égaux ou distincts) non ordonnés entre 0 et 6. Combien y a-t-il de dominos distincts ?
On peut compter séparément les dominos doubles (comportant deux fois le même nombre) et les autres.
Exercice
De combien de façons peut-on disposer deux tours de couleurs différentes sur un jeu d’échecs pour qu’elles soient en situation de prise directe ? Reprendre la question avec des fous, des reines ou des cavaliers.
Exercice
De combien de manières peut-on placer huit pions identiques sur un échiquier de façon à ce que chaque ligne et chaque colonne ne comporte qu’un seul pion ? et si les pions sont tous distincts ?
Exercice
Chaque carte d’un jeu de 32 cartes est caractérisée par son rang (7, 8, 9, 10, valet, dame, roi ou as) et sa couleur (pique, cœur, trèfle ou carreau). Chaque couple (rang, couleur) est représenté par une carte. Une main est une combinaison de 5 cartes. Calculer le nombre de mains différentes, puis dénombrer chacun des types de mains décrits ci-dessous. Dénombrer aussi les intersections entre ces divers types de mains, ainsi que les mains qui ne rentrent dans aucun de ces types.