Exercices de dénombrement

Pages associées

Ensembles finis

  1. 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.
  2. Montrer qu’une partie de N est finie si et seulement si elle est majorée.
    Pour le sens direct, on peut utiliser la somme ou le maximum des éléments de la partie.
  3. 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.

Calculs combinatoires

  1. 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.
  2. 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 ?
  3. 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.
  4. Les 38 élèves de la classe font une course. De combien de manières peuvent se répartir les trois premières places ?
  5. 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.
  6. 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 ».
  7. 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 ?
  8. 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, cur, 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.
  9. On note E l'ensemble des nombres à 5 chiffres dont chaque chiffre est entre 1 et 6.
    1. Calculer le cardinal de E.
    2. Combien de ces nombres sont-ils écrits avec des chiffres tous différents ?
    3. Combien de ces nombres sont-ils écrits avec des chiffres tous identiques ?
    4. Combien de ces nombres ont des chiffres placés dans un ordre strictement croissant ?
    5. Soit n un nombre entier à cinq chiffres (donc entre 10000 et 99999). Montrer que x est un nombre de E dont les chiffres vont croissant de gauche à droite si et seulement si n − 10000 + 123 s'écrit avec cinq chiffres strictement croissants de gauche à droite.
      Combien existe-t-il de tels nombres ?
  10. Pour tout (n, k) ∈ (N)2, le nombre d'entiers strictement positifs et inférieurs à n qui sont divisibles par k s'écrit E(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.
  11. 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.