Exercices de dénombrement

Ressources

Cours

Méthodologie

Ensembles finis

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
Soit E un ensemble fini de cardinal n ∈ N∗. Combien y a-t-il de couples (A, B) de parties de E tels que A ∩ B = ∅ ? tels que A ∪ B = E ? Combien y a-t-il de paires {A, B} de parties de E tels que A ∩ B = ∅ ?
D’après C. Degrave et D. Degrave, Probabilités et statistiques, Bréal 1990, énoncé 105
Exercice
ENS 2016 exercice 2 question 3
Soient A et B deux ensembles finis tels que card(A) = card(B) = card(A ∩ B). Montrer que A = B.

Combinaisons

Exercice
Calculer les coefficients du triangle de Pascal jusqu’à la ligne 10.
Exercice
Calculer les coefficients binomiaux (59 parmi 62), (37 parmi 41), (14 parmi 18), (39 parmi 45), (10 parmi 18), (3 parmi 14).
Exercice
Pour tout (n, p) ∈ N2 tel que p ≤ n, ∑k=pn (pk) = (p+1n+1).

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
Dans une classe avec un nombre pair d'élèves, on souhaite répartir les élèves deux par deux.
  1. De combien de manières peut-on choisir un premier groupe de deux élèves ? puis un deuxième ?
  2. Justifier que le nombre de manières de construire une liste de groupes de deux s'écrit n!/2n/2, où n est le nombre d'élèves.
  3. De combien de manières aurait-on pu obtenir la même répartition des élèves mais dans un ordre différent ?
  4. En déduire le nombre de répartitions possibles sans ordre sur les groupes de deux.
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
Combien de codes de trois lettres peut-on former de façon à alterner voyelles et consonnes ?
Exercice
Soit n et k deux entiers naturels non nuls.
  1. Dénombrer les listes de k entiers dans ⟦1 ; n⟧ qui soient strictement croissantes.
  2. Si (x1, … , xn) est une liste de nombres entiers naturels, montrer qu’elle est croissante si et seulement si la suite (x1 + 1, … , xn + n) est strictement croissante.
  3. En déduire le nombre de listes de 6 chiffres qui soient croissantes dans ⟦1 ; 9⟧.
Exercice
Soit (p, n) ∈ (N∗)2 tel que p ≤ n. 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
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 n ∈ N*) ? 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 = l1l2…ln 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
Pour tout entier n ≥ 0, on note an le nombre de suites de n lancers d’une pièce à pile ou face, dans lesquelles un nombre impair de piles suivi d’une face survient pour la première fois au bout des n lancers.
  1. Calculer a2, a3, a4, a5.
  2. Montrer que pour tout entier n ≥ 3 on a an = an−1 + an−2.
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.

Urnes

Exercice

On tire 6 fois de suite une boule d’une urne qui en contient 10, numérotées de 0 à 9, et on note les 6 numéros obtenus.

  1. En supposant qu’on remet à chaque tirage la boule tirée dans l’urne (et qu’elle peut donc être tirée à nouveau), combien de séries de 6 numéros peut-on obtenir ?
  2. Si au contraire, on ne remet pas les boules tirée dans l’urne, combien de séries de 6 numéros peut-on obtenir ?
  3. On remet toutes les boules tirées dans l’urne et on recommence, mais cette fois on ne remet une boule dans l’urne que si elle porte le numéro 0. Combien de séries peut-on trouver sans jamais tirer 0 ? en ne le tirant qu’une fois ? deux fois ? trois fois ?

Ensembles d’applications

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
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
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 n ∈ N∗, 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 (k parmi p) Sn, k.

Problèmes

Problème : Tour opérateur

Un graphe est une figure dans laquelle des points (appelés sommets) peuvent être reliés par des traits (appelés arêtes), comme dans la figure ci-contre.

On dispose d’un graphe à 5 sommets tous reliés par des arêtes. Ces arêtes peuvent par exemple représenter des voies de chemin de fer reliant cinq villes, mais les trains ne peuvent pas changer de voies lorsque celles-ci se croisent à l’extérieur des villes.

  1. Combien d’arêtes sont présentes dans ce graphe ? (Indiquer leur nombre ne suffit pas, il faut expliciter le raisonnement.)
  2. De combien de manières peut-on organiser une visite des 5 villes successivement sans voir deux fois la même ville ?
  3. De combien de manières peut-on organiser une boucle au départ de la ville A pour voir une seule fois chacune des autres villes et revenir à la ville A à la fin ?
  4. On souhaite maintenant parcourir successivement toutes les voies reliant ces cinq villes, sans repasser deux fois par la même voie. Combien de fois passera-t-on par chaque ville ? Montrer que la première ville est nécessairement aussi la dernière du parcours.
Problème : Repunits
On appelle repunit tout nombre entier ne s’écrivant qu’avec le chiffre 1 en base 10. Et on note E l’ensemble des entiers naturels qui divisent l’un des repunits.
  1. Montrer par récurrence sur n ∈ N∗ que 10n−1 est un multiple de 9.
  2. Montrer par récurrence sur n ∈ N∗ que le nombre entier s’écrivant avec n chiffres 1 vaut (1)/(9)(10n − 1).
  3. Montrer que tout nombre repunit est impair et n’est pas divisible par 5. En déduire que E est inclus dans l’ensemble des entiers naturels impairs non divisibles par 5.
  4. Soit b un entier naturel impair non divisible par 5. Montrer qu’il existe deux repunits distincts qui ont le même reste dans la division euclidienne par b. En déduire que b divise un repunit.
  5. Conclure.
Problème : Nombres premiers
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.
Problème : Coefficients binomiaux de rang pair
  1. Donner les valeurs des coefficients binomiaux de la forme (k parmi 7).
  2. En déduire ∑j=03 (2j parmi 7).
  3. Pour tout n ∈ N, expliciter la valeur de ∑k=0n (k parmi n) puis de ∑k=0n (−1)k × (k parmi n).
  4. En déduire la valeur de la somme de coefficients de rang pair : ∑k=0k pairn (k parmi n)
Problème : Code d’entrée

Une entrée d’immeuble est contrôlée par la saisie d’un code à 4 chiffres sur un appareil fixé au mur.

  1. Combien y a-t-il de codes possibles ?
  2. En examinant attentivement les touches de l’appareil, on s’aperçoit que 4 touches sont plus usées que les autres. En supposant que les 4 touches doivent être utilisées pour saisir le code, combien cela laisse-t-il de possibilités ?
  3. L’usure étant plus nette sur 3 touches, on suppose qu’en fait les 4 chiffres doivent être composés avec ces 3 touches. Justifier alors qu’une touche doit être utilisée 2 fois, et calculer le nombre de codes possibles.
Problème : Bataille

Deux joueurs mélangent chacun un paquet de 10 cartes numérotées de 1 à 10, et les posent en pile devant eux face cachée. Ils révèlent successivement et en même temps le numéro de leur première carte. Si les deux numéros sont différents, celui qui a tiré le plus grand gagne. Sinon, les joueurs gardent la carte suivante face cachée, et révèlent le numéro de la troisième, et ainsi de suite jusqu’à ce qu’il y ait un gagnant ou que les paquets soient épuisés.

  1. De combien de manières chaque paquet peut-il être mélangé avant tirage ?
  2. Dénombrer les tirages possibles au premier coup.
  3. Dénombrer les situations qui font qu’un joueur gagne au deuxième tirage.
  4. À quelle condition les joueurs finissent ex-aequo ? De combien de manières cela peut-il se produire ?
Problème

Soit n un entier supérieur ou égal à 2.

  1. Montrer que pour tout k ∈ ⟦2, n⟧, on a k(k − 1) (k parmi n) = n(n−1) (k−2 parmi n−2).
  2. En déduire une expression de ∑k=2nk(k − 1) (k parmi n) en fonction de n.
  3. Développer l’expression de la fonction x ↦ (1 + x)n et calculer sa dérivée seconde.
  4. Retrouver la valeur de la somme donnée en question 2.

Ajouts

Exercice

On souhaite connaitre le nombre de sigles de 3 lettres que l’on peut former avec la contrainte qu’il n’y ait pas deux voyelles consécutives.

  1. Dénombrer les sigles de 3 lettres sans aucune voyelle.
  2. Dénombrer les sigles de 3 lettres avec une seule voyelle.
  3. Dénombrer les sigles de 3 lettres avec deux voyelles en respectant la contrainte.
  4. Dénombrer les sigles de 3 lettres en respectant la contrainte et qui contiennent la voyelle Y.