#301

Dénombrements

Khôlles - Classes prépa Thierry Sageaux, Lycée Gustave Eiel.

Exercice 1. ˇ “)
Valentin, un de mes anciens élèves s'est lancé dans la fabrication et la vente de T-shirts avec un joli
logo qui représente une jeune lle serveuse à la longue chevelure (brune, blonde ou rousse) qui porte un
plateau avec une bière (brune, blonde ou rousse). Combien existe-t-il de T-shirts diérents ?
Exercice 2. ˇ “ (Kangourou 2015)
On colorie les nombres de 1 à 5 soit en rouge, soit en bleu en respectant la consigne : la somme de
deux nombres diérents de la même couleur est, elle aussi, un nombre de la même couleur. De combien
de manières diérentes peut-on colorier les cinq nombres ?

Exercice 3. ˇ “(
Parmi quarante secrétaires, huit connaissent le russe, quinze l'anglais et neuf l'allemand. D'autre part,
quatre parlent l'anglais et l'allemand, cinq l'anglais et le russe, deux l'allemand et le russe et deux parlent
les trois langues.
Combien de secrétaires ne connaissent aucune de ces trois langues ?
Exercice 4. ˇ“
A l'aide des neuf chire 1, 2, 3, 4, 5, 6, 7, 8 et 9, combien peut-on écrire
1) De nombres de trois chires ? Quelle est leur somme ?
2) De nombres de trois chires distincts ? Quelle est leur somme ?
3) De nombres de six chires distincts ?
4) On range les nombres de six chires distincts précédents par ordre croissant. Quel est le plus petit
de ces nombres ? Quel est le 25e ? Quel est le rang du nombre 124356 ?

Exercice 5. ˇ “(
On considère un pavage carré à n lignes et n colonnes. On dispose de p jetons tous identiques.
1) Combien y a-t-il de dispositions diérentes des jetons sachant que les p jetons doivent être sur des
cases diérentes ?
2) Combien y a-t-il de dispositions diérentes des jetons sachant que les p jetons doivent être sur des
cases diérentes avec un jeton par ligne et un jeton par colonne au maximum ?

Exercice 6. ˇ “)
Déterminer le nombre de suites croissantes d'entiers a1 , . . . , an avec n ≥ 4 telles que a1 = 1, a4 = 4
et il existe (k, l) tel que ak = 2 et al = 3.
Exercice 7. ˇ “ Un sport ! Un vrai ! Le curling !
Au curling, deux équipes de quatre s'arontent, chaque joueur jetant deux pierres de façon à être le
plus près possible de la cible. A la n des lancers, on compte le nombre de pierres gagnantes comme à la
pétanque.
1) Si on a huit joueurs, combien de matchs peut-on organiser ?
2) Sur les huit pierres disponibles pour l'équipe A, il y en a deux fêlées. De combien de façon le
premier joueur peut faire ses deux lancers avec une seule pierre fêlée.
3) En trois manches, l'équipe A a marqué 6 points. Quelles sont les répartitions possibles des points
de l'équipe A pour les trois manches consécutives ?

Exercice 8. ˇ “(

25 mars 2024 1 Thierry Sageaux

#301 Dénombrements
Florent possède deux otteurs, trois wishs et quatre voiles.
De combien de façons peut-il s'équiper ?

Exercice 9. ˇ “(
En informatique, le système de classication des couleurs RVB utilise les trois couleurs primaires
Rouge, Vert Bleu 1 . Pour coder les couleurs on aecte à chacune des trois couleurs primaires un octet
(soit une valeur sur les 256 possibles de 0 à 255).

Sachant que l'oeil humain est capable de diérencier un demi-million de couleur et d'en reconnaître
30 000, est-ce que le codage est assez important pour coder toutes les nuances perceptibles ?

Exercice 10. ˇ “( (OFM 2016)

2016 points sont alignés sur une droite ? De combien de manières peut-on les colorier en rouge ou
bleu, de sorte que deux points voisins quelconques soient de couleur diérente, et que chaque couleur soit
utilisée au moins une fois ?

Exercice 11. ˘ “ (Collègue d'anglais - extrait de journal américain)

Texte original : Taking a leaf out of Major's book, Mrs Maguire decided to number her six good pupils
from 1 to 6 and her bad pupils from 1 to 4 and put all to into a single line. No two baddies were to be
next to each other. The goodies had to be lined up from left to right in increasing order ; and the baddies
from left to right in decreasing order. How many ways are there of doing that ?
Dans une classe de dix élèves, il y a six "bons" et quatre "mauvais". Les bons sont numérotés de 1 à
6 et les mauvais de 1 à 4. On aligne les élèves dans l'ordre croissant pour les bons et décroissant pour les
mauvais. Sachant que deux mauvais ne doivent pas être à côté, de combien de façons peut-on les ranger ?

Exercice 12. ˘ “ Le 960-Chess (Fisher Random)

Dans cette variante du jeu d'échecs proposée par Bobby Fisher, les pièces majeures sont placées sur
la dernière rangée avec seulement trois règles :
• Les deux fous sont sur des cases de couleurs opposées,
• Le roi est entre les deux tours,
• Les pièces noires sont placées symétriquement face aux pièces blanches.
Pourquoi l'appelle-t-on le 960 ?

Exercice 13. ˇ “ (The New York Times 2010)

Taking a leaf out of Major Major's book, Mrs Maguire decided to number her six good pupils from
1 to 6 and her bad pupils from 1 to 4 and put all ten into a single line. No two baddies were to be next
to each other. The goodies had to be lined up from left to right in increasing order and the baddies from
left to right in decreasing order.
How many ways are there of doing that ?
1. Il s'agit du système additif car l'on projette les couleurs avec un projecteur à la diérence du système soustractif que
l'on retrouve pour le peintre qui mélange ses trois couleurs primaires qui sont Rouge, Jaune et Bleu à la lumière du jour.

2 Thierry Sageaux
#301 Dénombrements
Exercice 14. ˇ “ (OFM 2016)
Un palindrome est un nombre dont l'écriture décimale ne change pas si on inverse l'ordre des chires.
Par exemple, 3773 est palindrome (mais pas 0770). Un nombre à quatre chires (abcd)10 est dit équilibré
si a + b = c + d. Par exemple, 2736 est équilibré.
Déterminer tous les nombres équilibrés à quatre chires qui sont somme de deux palindromes à quatre
chires.

Exercice 15. ˘ “ (FFJM 2021 - 1

4nale)
Dans l'espace, on se donne cinq points en position générale (i.e trois d'entre eux ne sont jamais alignés
et quatre d'entre eux ne sont jamais coplanaires). Si l'on considère toutes les paires de plans obtenus à
partir de trois de ces cinq points, combien de droites d'intersection obtient-on ?

Exercice 16. ˘ “ (TFJM 2019)

Un grand père a n petits-enfants. Il les ordonne par âge et commence la distribution des chocolats. Il
possède k boîtes contenant respectivement a1 , a2 , . . . , ak chocolats. Il donne la première boîte au premier
de ses petits-enfants qui prend un chocolat et passe la boîte au suivant et ainsi de suite, le dernier
repassant la boîte au premier jusqu'à ce qu'il n'y ait plus de chocolats dans la boîte.
Ensuite, il y a deux congurations :
• A : Le grand-père donne la boîte à l'enfant suivant le dernier ayant mangé.
• B : Le grand père donne la deuxième boîte au deuxième petit-enfant et ainsi de suite.
1) Dans une première partie, on suppose que les ai sont tous égaux.
a) Dans la conguration A, est-il possible que la répartition soit équitable à un moment ? Quels
moments ?
b) Dans la conguration B, est-il possible que la répartition soit équitable à un moment ?
2) Même question si on suppose que ai = i pour tout i.
3) Dans cette partie, on pose que tous les ai sont distincts. Est-il possible que la répartition ne soit
jamais équitable ?

Exercice 17. ˇ “ (MEJ 2019)

Anaïs et Briac se présente pour représenter les 30 élèves de la classe à la course d'escargot. Au nal,
Anaïs a gagné avec 20 votes pour elle et 10 pour Briac.
Lors du dépouillement, l'assesseur lit les bulletins un à un.
1) Quel est le nombre de tirages diérents ?
2) Quel est le nombre de tirages pour lesquels Anaïs a toujours été devant Briac ?

Exercice 18. ˇ “
1) Déterminer le nombre d'injections d'un ensemble
P E à p éléments dans un ensemble F à n éléments.
2) Soit E un ensemble à n éléments, calculer card X .
X∈P(E)

Exercice 19. ˇ “( (Animath 2018)

Soit S un sous-ensemble de [[1, 30]] tel que la somme de éléments distincts de S n'est jamais divisible
par 5. Combien d'éléments un tel ensemble S peut-il avoir au maximum ?

Exercice 20. ˇ “(
Dans sa bibliothèque, Donald possède trois livres de géographie, deux livres d'économie et un de
politique pour les nuls.
1) S'il les range de façon aléatoire sur l'unique étagère de sa bibliothèque, de combien de façons peut-il
le faire ?
2) Il se rend compte nalement qu'il a trois fois le même livre de géographie (manuel de quatrième)
et deux fois le même livre d'économie. De combien de façons peut-il les ranger ?
3) Et si l'on suppose qu'il ne sépare jamais les livres de géographie ?

3 Thierry Sageaux
#301 Dénombrements
Exercice 21. ˇ “(
1) De combien de façons peut-on colorier un drapeau en trois bandes de couleurs à l'aide des trois
couleurs : bleu, blanc, rouge ? On demande seulement que l'on puisse distinguer les trois bandes une
fois colorié.
2) Idem mais avec n bandes.

Exercice 22. ˇ“
Un club de tennis regroupe huit joueurs. Ils souhaitent organiser un tournoi au format coupe : quatre
quarts de nales, deux demi-nales et nale. On imagine la coupe complète jusqu'au vainqueur. Combien
de coupes diérentes peut-on organiser ?

Exercice 23. ˇ “(
Combien existe-t-il de triplets d'entiers distincts de [[1, 100]] tels que la moyenne de deux d'entre eux
soit égale au troisième.

Exercice 24. ˇ “(
On a quatre garçons et sept lles. On veut constituer une équipe de football pour participer au tournoi
du lycée. Les règles sont strictes : il faut cinq joueurs et au moins trois garçons. D'autre part, Albertine
et Albert refusent de jouer ensemble.
Combien d'équipes peut-on former ?

Exercice 25. ˇ “(
Sur 100 étudiants, 65 ont réussi l'anglais, 77 les mathématiques et 74 le français. En outre, au plus
47 ont réussi le français et l'anglais, au plus 51 le français et les mathématiques ; enn 57 l'anglais et les
mathématiques.
Quel est le nombre maximal d'étudiants ayant réussi les trois matières ?

Exercice 26. ˘ “ Champions League 2018-2019

Lors de la phase de poules, deux clubs par poule sont qualiés pour les 8e de nale (il y a donc huit
poules ! !). Un tirage est organisé parmi les 16 équipes. Les matchs doivent répondre à trois règles :
i. Opposer un premier et un deuxième de poule.
ii. Ne pas être un match déjà joué lors des phases de poule.
iii. Ne pas voir s'opposer deux équipes d'un même pays.
Voici le tableau des clubs qualiés.
Poule A B C D
Premier Dortmund Barcelona PSG Porto
Deuxième Athletico Madrid Tottenham Liverpool Schalke
Poule E F G H
Premier Bayern Manchester C. Real Madrid Juventus
Deuxième Ajax Lyon Roma Manchester U.
1) Combien de congurations diérentes existe-t-il pour les huitièmes de nale si on ne tient pas
compte des règles ?
2) Si on ne tient compte que de la première règle ?
3) Si on ne tient compte que des deux premières ?
4) Si on tient compte de toutes les règles ?
On donne les nationalités des clubs : Athletico, Réal et Barcelona (Espagne), PSg et Lyon (France),
Schalke, Dortmund et Bayern (Allemagne), Liverpool, Manchester U., Manchester C. et Tottenham
(G.-B.), Juve et Roma (Italie), Ajax (Hollande), Porto (Portugal).

4 Thierry Sageaux
#301 Dénombrements
Exercice 27. ˇ“
On suppose que card E = n. Que vaut S = card A ? (trois preuves)
P
A∈P(E)

Exercice 28. ¯
1) De combien de façons peut-on remplir au hasard une grille de 9 × 9 avec 9 fois chacun des chires
de [[1, 9]] ?
2) Parmi ces grilles, combien correspondent eectivement à des grilles de Sudoku ?

Exercice 29. ˇ“
Quel est le nombre de suites croissantes de n termes dans [[1, n]] ?
Exercice 30. ˇ “
1) On se donne 100 droites en position générale (i.e. non parallèles et non concourantes). En combien
de secteurs a-t-on partagé le plan ?
2) Bonus : Combien faut-il de couleur pour colorier les secteurs sans que deux secteurs liés par un
segment soient de même couleur ?
Exercice 31. ˇ“
Un nombre entier naturel est dit ascendant s'il contient au moins deux chires et si chaque chire
est strictement plus petit que tous les chires à sa droite.
Combien existe-t-il de nombres ascendants possédant au plus neuf chires ?
Exercice 32. ˇ“
Soit E un ensemble à n éléments. Quel est le nombre de couples (X, Y ) ∈ P(E)2 tels que X ∩ Y soit
un singleton ?
Exercice 33. ˇ “ ( 21 -nale FFJM 2018)
Les nombres descendants : Un nombre à plusieurs chire du deuxième chire (en partant de la gauche)
est inférieur ou égal à tous les chires situés à sa gauche. Ainsi, les nombres 764, 322 et 555 sont descen-
dants, mais pas 823.
Combien existe-t-il de nombres descendants à trois chires.
Exercice 34. ˇ“
A l'EuroMillions, on doit cocher cinq numéros de [[1, 50]] et deux étoiles de [[1, 11]]. Un ticket est
gagnant si au moins deux numéros sont bons, ou si un numéro et au moins deux étoiles sont bons. Le
reste est perdant.
Quelle est la probabilité de perdre ?
Exercice 35. ˇ“
Soit E un ensemble à n éléments : on se propose de calculer S = card(X ∩ Y ).
P
(X,Y )∈(P(E))2
1) Méthode 1 :
a) Pour toute partie Z ∈ P(E) à k éléments, rechercher le nombre de couples (X, Y ) tels que
X ∩ Y = Z.
b) En déduire la valeur de S .
2) Méthode 2 :
a) Soient X et Y des parties de E . Montrer que {X × Y, X × Y , X × Y, X × Y } forme une partition
de E 2 .
φ : (P(E))2 −→ (P(E))2
b) Retrouver la valeur de S en utilisant l'application dont on
(X, Y ) 7−→ (X, Y )
montrera la bijectivité.
Exercice 36. ˇ“

5 Thierry Sageaux
#301 Dénombrements
Quel est le nombre d'anagrammes de PERMUTATION avec les voyelles dans l'ordre alphabétique ?
Exercice 37. ˇ“
Combien existe-t-il de triplets d'entiers (x, y, z) ∈ (N\{0})3 tels que x + y + z = 60.
Exercice 38. ˇ“
Sheldon a eu un train pour son Noël. Il peut mettre bout à bout des wagons identiques de 10cm et
de 20cm. Il veut construire un train de 150cm de long avec sa locomotive préférée devant. De combien de
façons peut-il le faire ?
Exercice 39. ˇ“
Quel est le nombre de mots de douze lettres sur l'alphabet {a, b, c, d} contenant un nombre pair de
'd' ?
Exercice 40. ˇ“
On voudrait savoir quel est le nombre de permutations des entiers 1 à 8 de sorte que deux nombres
consécutifs ne se succèdent jamais (i.e. 32 est possible, mais pas 23).
Exercice 41. Nombres de Catalan
Soient x1 , . . . , xn n réels. Pour calculer la somme x1 + · · · + xn , on place des parenthèses de façon
à n'avoir que des additions de deux nombres à eectuer. Soit tn le nombre de manières de placer les
parenthèses (on pose t1 = 1).
1) Déterminer t2 , t3 , t4 .
2) Trouver une relation de récurrence entre tn et t1 , . . . , tn−1 .

Exercice 42. ˇ “(
1) On considère n points distincts du plan en position générale (trois points quelconques ne sont pas
alignés). Combien ces points déterminent-ils
a) de segments ?
b) de triangles ?
c) de quadrilatères ?
d) de polygônes à p côtés ?
2) Soit un polygône à n côtés.
a) Quel est le nombre de diagonales de ce polygône ?
b) En combien de points intérieurs au polygône se coupent-elles ?

Exercice 43. Grilles de Fleissner

Dans le livre de Jules Verne, Mathias Sandorf est utilisé un codage à base de grilles, dites grilles de
Fleissner du nom d'un colonnel autrichien ayant écrit un livre de cryptographie au XIXe siècle.
Si l'on considère une grille de Fleissner 6 × 6, il s'agit d'un carré constitué de 36 petits carrés. On
découpe alors 9 de ces petits carrés de sorte que, si l'on tourne la grille d'un quart, un demi ou trois
quarts de tours, les trous ne se superposent jamais.
Pour coder, on pose la grille sur une feuille, on écrit le début du message dans les neuf trous puis on
fait une rotation quart de tour et on écrit la suite jusqu'à avoir fait un tour complet. On obtient alors le
message.

6 Thierry Sageaux
#301 Dénombrements
Il est dit que l'on peut créer 262 144 grilles diérentes. Est-ce vrai ?
Exercice 44. Permutations de couples
On doit placer autour d'une table ronde un groupe de 2n personnes, n hommes et n femmes, qui
constituent n couples. Combien existe-t-il de dispositions . . .
1) au total ?
2) en respectant l'alternance des sexes ?
3) sans séparer les couples ?
4) en remplissant les deux conditions précédentes ?

Exercice 45. Parties ne contenant pas d'éléments consécutifs

1) Combien y a-t-il de parties à p éléments de {1, . . . , n} ne contenant pas d'éléments consécutifs ?
(Indication : Si {x1 , . . . , xp } est une telle partie avec x1 < x2 < · · · < xp , considérer l'ensemble
{x1 − 1, . . . , xp − p})
2) Soit tn le nombre de parties de {1, . . . , n} de cardinal quelconque sans éléments consécutifs.
a) Montrer que tn+2 = tn+1 + tn , t2n+1 = t2n + t2n−1 , et t2n = t2n − t2n−2 .
b) Calculer t50 .

Exercice 46. ˇ“
Soit E un ensemble de cardinal n. On note Γpn le nombre de combinaisons avec répétition de p éléments
de E .
1) Calculer Γ1n , Γ2n , Γ3n .
2) Soit x ∈ E . Combien de fois x gure-t-il dans l'ensemble des combinaisons avec répétition de p
éléments de E ?
p n + p − 1 p−1
3) Montrer que Γpn = Γn .
n n
En déduire Γn .
p

4) Application : Combien y a-t-il de suites de n entiers naturels dont la somme est égale à p ?

Exercice 47. Les trous de Kaplansky

Soient n et k deux entiers naturels non nuls. Quels est le nombre de p-listes croissantes (xi )1≤i≤p de
[[1, n]] telles qu'entre deux termes consécutifs il y ait au moins k entiers, c'est-à-dire telles que ∀i ∈ [[1, p−1]],
xi+1 − xi > k .

Exercice 48. ˘“
Soit n ∈ N\{0} et soit p ∈ N quel est le nombre de sous-ensembles de [[1, n]] de cardinal p ne contenant
aucun couple d'entiers consécutifs ?
Exercice 49.
Neuf voyageurs attendent le train pour Libourne en gare de Bordeaux.
1) S'ils ont tous des billets de 2nde classe et qu'ils ont le choix entre cinq wagons de 2nde classe,
calculer le nombre de manières de répartir ces voyageurs entre ces cinq wagons.
2) Si trois d'entre eux, seulement, ont des billets de 1ère , qu'il y a deux wagons de 1ère classe et cinq
wagons de 2nde classe, calculer le nombre de façons de répartir ces voyageurs entre les wagons.
3) On sait maintenant que sur les cinq wagons de 2nde classe il reste neuf places seulement.
a) Combien de répartitions possibles de ces places entre ces wagons peut exister ?
b) Cette répartition étant connue du contrôleur et si tous les voyageurs sont eu deuxième classe,
de combien de façons diérentes peut-il les installer ?
Exercice 50.
L'alphabet est composé de 26 lettres dont 6 voyelles. On appelle mot toute suite de lettres ayant un
sens ou non.
1) Combien existe-t-il de mots de quatre lettres ?

7 Thierry Sageaux
#301 Dénombrements
2) Combien existe-t-il de mots de quatre lettres constitués de quatre lettres diérentes ?
3) Combien existe-t-il de mots de quatre lettres commençant et se terminant par une voyelle ?
4) Combien existe-t-il de mots de quatre lettres contenant au moins une voyelle ?
5) Combien existe-t-il de mots de quatre lettres écrits uniquement avec les lettres A et B, chaque
lettre apparaissant au moins une fois ?
6) Combien existe-t-il de mots de quatre lettres constitués d'exactement deux lettres diérentes ?

Exercice 51.
A l'entrée d'un immeuble, on dispose d'un clavier de 12 touches : trois lettres : A, B et C et les neufs
chires non nuls. Le code de l'ouverture de la porte est composé d'une lettre suivie d'un nombre de quatre
chires pouvant être répétés.
1) Combien existe-t-il de codes diérents ?
2) Combien y a-t-il de codes
a) Comportant au moins le chire 7 ?
b) Pour lesquels tous les chires sont pairs ?
c) Pour lesquels les quatre chires sont diérents ?
d) Pour lesquels les quatre chires forment une suite strictement croissante ?

Exercice 52. Concours Général 2012 Un facteur doit distribuer le courrier dans une rue. Celle-ci ne
comporte qu'une seule rangée de maisons régulièrement espacées et numérotées 1, 2, . . . , n où n est un
entier supérieur ou égal à 2. Le facteur doit distribuer une lettre par maison. Pour cela, il laisse son vélo à
la maison 1, y dépose le courrier correspondant, et ensuite distribue les lettres au hasard, puis revient à la
maison 1 récupérer son vélo. Il eectue ainsi un trajet, représenté par les numéros successifs des maisons
où il a déposé le courrier.
Par exemple, si n = 5, un trajet possible est 1, 5, 2, 4, 3, 1. La distance totale parcourue, appelée
longueur du trajet, vaut 12 dans ce cas car |?5 − 1| + |2 − 5| + |4 − 2| + |3 − 4| + |1 − 3| = 12.
Un autre trajet possible est 1, 3, 5, 4, 2, 1 de longueur 8.
1) Combien y a-t-il de trajets possibles ?
2) a) Montrer que tout trajet est de longueur supérieure ou égale à 2(n − 1).
b) Combien y a-t-il de trajets de longueur minimale ?
3) a) Dans le cas n = 5 et n = 6, déterminer la longueur maximale d'un trajet et donner un exemple
de trajet de longueur maximale.
b) Pour n quelconque, déterminer la longueur maximale d'un trajet.
4) On tire un trajet au hasard (tous les trajets sont équiprobables). Quelle est l'espérance de la
longueur du trajet ?
Exercice 53. ¯ (Promys 2017)
n personnes sont réparties dans trois comités de telle sorte que chaque comité ait au moins un membre
et personne ne soit dans les trois comités. Une personne n'est donc pas nécessairement dans un comité.
1) Combien faut-il de personnes au minimum ?
2) Si n = 3, de combien de façons ceci peut-il être fait ?

Exercice 54. ˘ “ Nombre de surjections

1) Déterminer le nombre de surjections d'un ensemble à n + 1 éléments sur un ensemble à n éléments.
2) On note dans la suite Pnk le nombre de partitions d'un ensemble à n éléments en k classes. Montrer
que Pnk = Pn−1
k−1 k
+ kPn−1 pour 2 ≤ k ≤ n − 1.
3) Calculer, en fonction de Pnk le nombre de surjections d'un ensemble à n éléments sur un ensemble
à p éléments.
4) Montrer que le nombre de surjections Nn,p d'un ensemble E à n éléments dans un ensemble F à
p éléments est :
p p!
(−1)i (p − i)n .
P
Nn,p =
i=0 i!(p − i)!

8 Thierry Sageaux
#301 Dénombrements
Exercice 55. ˇ “ Tour de magie
On prend 21 cartes. On fait choisir une carte au public et on leur demande de mélanger.
On récupère les cartes. On en fait trois tas de 7 cartes. On demande au public dans quel tas est la
carte. On met ce tas au milieu des précédents. On recommence deux fois de plus. A la n de la troisième
fois, la carte en question est au milieu du dernier tas désigné.
Pourquoi ?

9 Thierry Sageaux
#301 Dénombrements
Solutions des exercices

Exercice 1.
32 = 9.
Exercice 3.
Avec la formule du crible, on trouve 23 secrétaires qui parlent au moins une de ces trois langues et
donc 17 qui n'en parlent aucune.
Exercice 4.
1) On peut écrire 93 tels nombres. on peut faire la somme des unités : 81 9×10
2 = 3645, des dizaines
et des centaines, ce qui donne à chaque fois le même résultat, soit une somme de 3645 + 10 × 3645 +
100 × 3645 = 3645 × 111 = 404 595 .
2) On trouve A39 = 504 nombres. Avec la même astuce, on somme les nombres en colonnes : 56 ×
(1 + 2 + 3 + · · · + 9) × 111 = 279 720 .
3) A69 = 60 480 .
4) Le plus petit est 123456, le 25e est 123564 et 124356 est le 121e .

Exercice
5.
1) np .
2

2) n n
Apn .



p n(n − 1)(n − 2) . . . (n − p + 1) = p

Exercice 6.
On choisit la place des premiers rangs avec 2 et 3, soit n−2
.


2

Exercice 7.
1 4

1) = 35.
2 8
2) Soit la première pierre est fêlée, soit c'est la seconde : 2 × (2 × 6) = 24
3) On met dans l'urne les trois manches que l'on tire six fois avec remises (la même manche pouvant
revenir plusieurs fois) et sans

ordre (un point reste un point quel que soit sa place dans le tirage). Il
s'agit donc de Γ63 = 3+6−1
3 = 56
Exercice 8.
2 × 3 × 4 = 24.
Exercice 9.
2563 = 16 777 216. Donc oui pour la diérenciation et, a fortiori, la reconnaissance.
Exercice 10.
3 × 22015 − 6.
Exercice 11.
En ne respectant que la condition d'ordre, il a 10 4 = 210 façons de le faire. Il reste à enlever les cas

défavorables correspondant à deux mauvais côte à côte.

S'il y en a deux côte à côte exactement, on a 3 × 73 = 105 possibilités : le coecient binomial étant
le nombre de places pour les trois insertions où vont les mauvais et le facteur trois représentant l'endroit
où on en met deux.
S'il y a deux paires de mauvais côté à côte, cela donne 7


2 = 21
S'il y en a trois côte à côte exactement, on a 2 × 2 = 42 possibilités.
7

S'ils sont tous les quatre à côté, il y a sept possibilités.

Soit un résultat nal : 210 − 105 − 42 − 7 − 21 = 35 .
Exercice 12.
Parce que c'est le nombre de congurations possibles.

10 Thierry Sageaux
#301 Dénombrements
Nb de cases entre deux tours 1 2 3 4 5 6
Nb de cong. possibles pour les tours 6 5 4 3 2 1
Nb de cases pour le roi 1 2 3 4 5 6
Nb de possibilités pour les fous 6 6 4( 13 ) 6( 23 ) 6 4( 5 ) 6( 5 ) 6
2 3

Nb de possibilités pour la dame 3 3 3 3 3 3

Nb de possibilité pour les cavaliers 1 1 1 1 1 1
Total 108 180 192 216 156 108
Soit 960 possibilités.
Exercice 13.
We line up the goodies and count the possible places for the baddies : 7. We need to pick 4 places
among the 7. The sorting gives 74 = 35 possibilities.

Exercice 14.

Exercice 15.
Il serait faux de penser que l'on peut prendre le nombre de triplets de points, soit 53 = 10 plans et

les intersections de ces plans, soit 2 = 45 droites. En eet, on peut retomber sur la même droite.
10

Il faut regarder quand un seul point est commun aux deux plans : 5 × 3 =
15 droites.
Et quand la droite obtenue est celle passant par deux des cinq points : 52 = 10 droites.
Soit au total 25 droites.
Exercice
17.
1) 30
10 = 30 145 015 nombre de marche sur un quadrillage, du point (0, 0) au point (10, 30).
Exercice 18.
n!
1) Apn =
(n − p)!
n n
2) On doit calculer la somme card(X) = n
= n2n−1 d'après un exercice classique fait en
P P

p p
p=0 p=0
cours.
Exercice 19.
18.

Exercice 20.
1) Il s'agit d'un tirage avec ordre et sans remise des six places pour chacun des livres. Soit un arran-
gement A66 = 6! = 720 .
2) On reprend le calcul précédent mais on doit quotienter par l'ordre sur les trois livres de géographie :
720
3! = 6 et celui sur les deux livres d'économie : 2! = 2. Ce qui donne = 60 .
6×2
3) On imagine alors que les trois livres de géographie ne forment qu'un seul et même livre, soit
4! = 24 .

Exercice 21.
1) Avec les trois couleurs, il y en a 3! = 6 ; avec deux couleurs, il y en a 3
× 2 = 6 et c'est tout. Soit


2
12 au total.
2) 3 × 2n−1 .

Exercice 22.
Le nombre de quarts de nales est 7 × 5 × 3× = 105 car le premier joueur peut avoir 7 adversaires
diérents, le suivant non attribué, 5 et ainsi de suite.

11 Thierry Sageaux
#301 Dénombrements
Pour les vainqueurs, il y a 2 = 16 possibilités. 4

Il faut faire attention aussi à l'ordre des quarts de nales. Il y a 3 ordres possibles (AB-CD, AC-BD,
AD-BC).
Rien que pour les quarts, on a donc 105 × 16 × 3 = 5 040.
Les demi-nales sont xées par les quarts. Il reste le choix des gagnants : 4 choix possibles. Et pour
le nale, 2 choix possibles.
Donc au total, il y a : 5 040 × 4 × 2 = 40 320 .
Exercice 23.

Il y en a
50 50
= 2450 .


2 + 2

Exercice


24.3
6

4 7 4
= 72 .

6

3 2 − 2 1 + 4 1

Exercice 25.
On utilise le crible de Poincaré (avec des notations implicites) :
f + a + m − f a − f m − am + f am ≤ 100 ⇔ f am ≤ 39 .

Exercice 26.
1) Il ne sert à rien de dénombrer le nombre de paires. Il faut dénombrer le nombre de mots de 16
lettres, soit 16! et diviser par les ordres : 28 pour les paires elles-mêmes et 8! pour les huit paires dans
16!
la liste. Au total, cela fait 8 = 2 027 025 .
8!2
2) On procède de la même façon en croisant deux listes de deux mots de 8 lettres, soit (8!)2 et on
divise par l'ordre sur les paires qui vaut 8!. Il reste 8! = 40 320 . On peut le voir aussi en se disant que
l'on fait un tirage ordonné des huit équipes arrivées deuxièmes, chacune se retrouvant face à l'équipe
arrivée première, dans l'ordre.
3) On rajoute la deuxième condition, i.e. il va falloir enlever des possibilités aux cas précédents. On
utilise la formule du crible : 8! − 81 7! + 82 6! − 83 5! + 84 4! − 85 3! + 86 2! − 87 1 + 1 = 14 733 .

4) Les exceptions sont trop nombreuses pour une stratégie globale... Un arbre (long) ou un programme
(court) donne toutes les possibilités : 3694 .
Exercice 27.
n n
n n−1
= n2n−1 .
P
P

•S= p p = pn p−1
p=0 p=0
• On écrit successivement tous les éléments des parties de E . Chaque élément est écrit le nombre
de fois égal au nombre de parties de E\{a}
P :2
n−1
. Donc on trouve encore n2n−1 .
card A + card Ā = card(A ∪ Ā = n2n . Donc S = n2n−1 .
P P
• 2S =

Exercice 29.
Il faut choisir le nombre de sauts : S'il y a k sauts, il faut choisir k + 1 termes de [[1, n]], soit n
, puis


k+1
n−1 n−1
n−1 2
choisir les k valeurs d'indices qui correspondent aux sauts : n−1
, d'où n n−1
.

P

P

k k+1 k = k
k=1 k=1

Exercice 30.
1) Par récurrence sur le nombre de secteurs avec n droites, noté an . On a an+1 = an + n + 1 et
n
a0 = 1. En posant un+1 = an+1 − an = n + 1, on trouve par télescopage
P
uk = an − a0 ⇔
k=1
n(n + 1)
an = 1 + .
2

12 Thierry Sageaux
#301 Dénombrements
2) Deux. Par récurrence directe.
Exercice 31.
Il s'agit d'un tirage sans ordre et sans remise parmi les neufs chires (le zéro ne peut apparaître).
D'autre part, l'ordre est imposé par la décroissance des chires dans le nombre. Ainsi, il existe
9 9 9 9 9
= 502 .






2 + 3 + ··· + 9 = 29 − 1 − 0

Exercice 32.
n × 3n−1 . On choisit le singleton (n choix possibles), puis pour chaque élément de E\(X ∩ Y ), on
choisit s'il est dans X , Y ou ni l'un ni l'autre.
Exercice 33.
Tirage avec remise et sans ordre (l'ordre est donné par les conditions de décroissance). Γ310 = 10+3−1


3 =
220, mais il faut retirer le triple 0, soit 219 solutions.

Exercice 34.
Nombre de tickets sans numéro
bon : 45 11
. Nombre de tickets avec un bon numéro et zéro ou une



5 2
étoile seulement : 51 45 .


 9
2 9


4 2 + 1 1
Le nombre total de combinaisons est 50 11
, soit une probabilité de 0, 922 .



5 2

Exercice 35.
1) a) Les k éléments sont xés et appartiennent à
la fois à X et à Y . On complète X en rajoutant l
éléments venant des n − k restants. Il y a n−k
l façons de le faire. A chaque fois, il reste n − k − l
éléments et il y a 2n−k−l façons de compléter Y , autant que de parties d'un ensemble à n − k − l
éléments, ce qui donne le nombre cherché :
n−k
n−k


2n−k−l = 3n−k
P
Nk = l
l=0

par le binôme de Newton.

On peut aussi supposer que l'on a xé les k éléments et qu'il reste à placer les n − k autres
éléments, soit dans X\(X ∩ Y ), soit dans Y \(X ∩ Y ), soit dans E\(X ∪ Y ). Un arbre donne
directement trois choix par éléments, donc 3n−k possibilités.
n n n−1
b) Ainsi, S = n n−1 n−1
3n−k = n(1 − 3)n−1 n4n−1 .




3n−k = 3n−k = n
P P P
k k n k−1 k
k=0 k=1 k=0
2) a) Il s'agit bien d'un recouvrement car X × Y ∪ X × Y ∪ X × Y ∪ X × Y = E × E . De plus, il est
disjoint car, par exemple, il n'existe pas d'élément (x, y) dans X × Y et dans X × Y . On a donc
bien aaire à une partition.
b) Cette application est clairement bijective (avec pour bijection réciproque, elle-même). Ainsi,
quand on regarde le nombre d'éléments de P(E)2 , on trouve 2n × 2n = 4n . Et l'on peut subdiviser
en 4n−1 quadruplets donnés par la partition précédente.
Il sut maintenant de voir que si on xe x ∈ E , chaque élément (x, x) est toujours dans un
seul des quatre éléments de chaque quadruplet. Dans la somme, on compte donc 4n−1 fois chaque
x de E , soit n4n−1 au total.

Exercice 36.
6!
Pour les consonnes, on a = 360 possibilités du fait des deux 'T'. Il reste donc 7 places possibles
2!
pour les voyelles avec remise et sans ordre (l'ordre étant imposé par l'ordre alphabétique), soit Γ57 = 462.
Soit au total, 462 × 360 = 166 320 .
Exercice 37.

13 Thierry Sageaux
#301 Dénombrements
• Première méthode : Cela revient à découper le segment [0, 60] en trois morceaux. Il faut donc
2 = 1711 .
choisir deux entiers entre 1 et 59, soit 59

• Seconde méthode : On pose x′ = x − 1, y ′ = y − 1 et z ′ = z − 1. On a (x, y, z) ∈ N3 et

x + y + z ′ = 57. On peut le voir comme 57 objets dont on doit choisir de les mettre dans x′ , y ′ ou z ′ , ce
′ ′

qui donne Γ357 = 1711.

Exercice 38.
• Première méthode : Avec 15 petits, d'une seule façon ; avec 13 petits et 1 grand, de 14 façons ;
avec 11 petits et 2 grands, de Γ212 = 13
2 = 78 façons et en continuant, de Γ10 = 280, Γ8 = 330, Γ6 = 252,

3 4 5

Γ4 = 84 et Γ2 = 8. Soit au total, 987 .

6 7

• Seconde méthode : Par récurrence, soit x30 le nombre cherché, on a x0 = 1, x2 = 1 et xn =

xn−2 + xn−4 . On obtient la suite de Fibonacci et x30 = F17 = 987.

Exercice 39.
• Première méthode : En diminuant le nombre de d :

2 + 3 × Γ4 + 3 × Γ6 + 3 × Γ8 + 3 × Γ11 + 1 = 8 390 656 .

312 + 310 × Γ11 8 9 6 7 4 5 2 3

• Seconde méthode : On note xn le nombre de mots de n lettres contenant un nombre pair de

fois le d. On a alors xn = 3xn−1 + 4n − xn−1 = 2xn−1 + 22n car on place a, b, c à la n d'un mot de n − 1
lettres contenant un nombre pair de fois le d OU un d à la n d'un mot de n − 1 lettres ayant un nombre
22n + 2n
impair de d. On trouve par récurrence xn = 2n−1 + 2n + · · · + 22n−2 = = 22n−1 + 2n−1 et le
2
même résultat en découle.
Exercice 40.
• Première méthode : Soit xn ce nombre pour les nombres de 1 à n. On a x2 = 1, x3 = 3 et
xn+1 = nxn + (n − 1)xn−1 car on rajoute n + 1sur une des n places possibles OU on intercale n + 1 entre
deux consécutifs (comptés comme un seul chire). Ce qui donne x8 = 16 687 .
• Seconde méthode :On note  Ei l'ensemble des permutations telles que i et i + 1 se succèdent,
7
pour i ∈ [[1, 7]]. On veut card Ei . On utilise le crible et le fait que card(Ei1 ∩Ei2 ∩· · ·∩Eik ) = (8−k)!.
S
i=1
On a alors
 7

card 7 7 7 7 7 7 7
S







Ei = 1 7! − 2 6! + 3 5! − 4 4! + 5 3! − 6 2! + 7 1! = 23 633
i=1

Donc il y a 8! − 23 633 = 16 687 solutions.

Exercice 41.
1) 1,2,5.
n−1
2) tn = tk tn−k .
P
k=1

Exercice 42.
1) a) n2 .

b) n3 .

c) Attention, pour quatre points, il y a n4 quadrilatères non croisés. Mais il faut rajouter les deux

croisés pour chaque quadruplet. Soit au total 3 4 .

n

d) De la même façon, n polygônes non croisés. Il reste à compter les croisés. Sinon, on compte


p
le nombre de choix de points p et pour p points, on xe un sommet et ses deux liaisons : p−1
n



2
puis à un des deux points choisi, on associe un autre point
: p
− 3 choix, puis p − 4 et ainsi de suite
jusqu'à ce qu'il n'y ait plus de choix. Soit au total : np p−1 2 (p − 3)!.

14 Thierry Sageaux
#301 Dénombrements
2) a) n
.


2

b) n
2 .

Exercice 43.
Le message d'abord : "Il est vraiment trop dur cet exercice. Merde !"
Et il y a bien 49 = 262 144 grilles possibles.

Exercice 44.
1) (2n)!.
2) 2(n!)2 .
3) 2n+1 × n!.
4) 4 × n!.

Exercice 45.
1) {x1 − 1, . . . , xp − p} est une partie quelconque de {0, . . . , n − p}, donc N = Cn−p+1
p
.
2) b) 32951280099.

Exercice 46.
2 . Γ1 = 1, Γ2 = 4 et Γn =
1) Γ1n = n. Γ21 = 1 et Γ2n = n+1 3 .
n+2

3 3 3

de E , on obtient pΓpn éléments. Et

2) Si l'on écrit toutes les combinaisons à répétition de p éléments
p
comme les n éléments de E apparaissent un même nombre de fois, on a écrit Γpn fois le x.
n
p−1
3) Il existe combinaisons contenant x. Et dans ces combinaisons, x apparaît Γnp−1 +
Γp−1
n Γp−1
n
n
fois.
p p − 1 p−1 n + p − 1 p−1
Donc Γpn = Γp−1
n + Γn = Γn .
n n p
n+p−1 n+p−2 n+1 1
Ainsi Γn = n+p−1 .


Γpn
= × × ··· × p
p p−1 2
4) On associe à chaque xi de E le nombre de fois mi où il est écrit dans une combinaison à répétition
de p éléments de E . On a alors m1 + m2 + · · · + mn = p où mi ∈ N pour tout i ∈ [[1, n]]. On a donc une
bijection de l'ensemble des combinaisons à répétition de p éléments de E dans l'ensemble des suites
de n entiers naturels dont la somme vaut p.

Exercice 47.
On cherche une p liste telle que 1 ≤ x1 < x2 − k < x3 − 2k < · · · < xp − (p − 1)k ≤ n − (p − 1)k. Il
y a une bijection entre l'ensemble des p-listes (xi ) et des p-listes (yi ) telles que 1 ≤ y1 < y2 < · · · < yp ≤
n − (p − 1)k . Soit n−(p−1)k possibilités.


p

Exercice 48.
On imagine une partie {a1 , a2 , . . . , ap } répondant aux contraintes.
On peut créer la bijection qui à chaque liste de ce type associe la listedes p nombres
 de [[1, n + 1 − p]] :
n+1
a1 < a2 − 1 < a3 − 2 < · · · < ap − (p − 1). Donc p ≤ n + 1 − p, i.e. p ≤ .
2
On trouve doncn+1−p
possibilités.


p

Exercice 52.
1) (n − 1)!
2) a) En numérotant m0 , m1 , . . . , mn les numéros des maisons visitées (avec m0 = mn = 1). Il existe
i tel que mi = n. Et

l = |m1 − m0 | + · · · + |mi − mi−1 | + |mi+1 − mi | + · · · + |mn − mn−1 | ≥ 2(n − 1)

| {z } | {z }
≥|mi −m0 |=n−1 ≥|mn −mi |=n−1

15 Thierry Sageaux
#301 Dénombrements
en utilisant l'inégalité triangulaire.
b)On remarque que 1, n, n − 1, . . . , 1 est de longueur minimale 2(n − 1). On montre facilement
que la minimalité est conservée si et seulement si il n'y a qu'une série croissante jusqu'à n et une
décroissante jusqu'à 1, soit 2n−2 trajets.
3) a) • Si n = 5 : La distance 4 (entre 1 et 5) ne peut être atteinte qu'une fois. La distance 3 est
réalisée entre 1 et 4 ou entre 2 et 5 mais ne peut être réalisée plus d'une fois si la distance 4 est
atteinte. De même, la distance 2 ne peut être réalisée plus de deux fois si 3 et 4 sont atteintes. Il
ne reste que des distances 1. Soit
l = 4 + 3 + 2 × 2 + 1 = 12.
• Si n = 6 : Idem et on trouve l = 5 + 4 + 3 × 2 + 2 + 1 = 18.
b) On note m0 , . . . , mn un trajet. On dénit une suite d'indices entre lesquels m croît ou décroît.
On pose b1 = 0 et considérerh1 le plus grand indice k ≥ b1 tel que mk > mk−1 . On dénit ensuite b2
comme le plu sgrand indice k ≥ h1 tel que mk < mk−1 . On construit ainsi de suite deux séquences
b1 = 0, . . . , bk , bk+1 = n et hn , . . . , hk telles que (mi ) est croissante entre bi et hi puis décroissante
entre hi et bi+1 .
La longueur du trajet est alors
l = mh1 − mb1 + mh1 − mb2 + · · · + mhk − mbk + mhk − mbk+1
= 2(mh1 + · · · + mhk ) − 2(mb1 + · · · + mbk )
= 2(mh1 − mb1 + mh2 − mb2 + · · · + mhk − mbk )
≤ 2((n − 1) + (n − 3) + · · · + (n − 2k + 1)) ≤ 2k(n − k).
n
La fonction k 7−→ k(n − k) atteint son maximum en k = ⌊ ⌋. Donc
2
n  n  n2
l ≤ 2⌊ ⌋ n − ⌊ ⌋ = ⌊ ⌋.
2 2 2
4) L'espérance E est donnée par
X n
XX
(n − 1)!E = l(m) = |mk − mk−1 |
k=1
X n−1
XX X
= |m1 − 1| + |mk − mk−1 | + |mn−1 − 1|
k=2

n
On a n!
. Idem pour |mn−1 − 1|.
P P P
|m1 − 1| = (n − 2)! (i − 1) = 2
i=2
Et
X X X
|mk − mk−1 | = |x − y| = 2 (y − x)
2≤x̸=y≤n 2≤x≤y≤n
X X
=2 (y − t − 1) = 2 1
1≤t≤y≤n 1≤t≤y≤n
 
n n(n − 1)(n − 2)
=2 = .
3 3

n(n + 1)
Tout calcul fait, on trouve E = .
3

Exercice 53.

16 Thierry Sageaux
#301 Dénombrements
1) - Il faut au moins deux personnes. Auquel cas, il y a n2 = 12. On obtient ce nombre soit directement
avec un arbre ou un tableau, soit en utilisant le crible de Poincaré : n2 =.
2) 3 × 3 × 1 + 3 × 3 × 3 + 3! = 24.

Exercice 54.
1) Il sut de choisir les deux éléments qui ont la même image, soit n+1 2 , ainsi que leur image

commune, soit n possibilités. Ensuite, il faut déterminer les images des n − 1 restant de l'ensemble de
départ qui établissent une bijection sur les n − 1 éléments restants de l'ensemble d'arrivée, soit (n − 1)!
possibilités. Ce qui fait au total :

n+1

(n + 1)! n(n + 1) n(n + 1)!
n 2 × (n − 1)! = n! = n! = .
(n − 1)!2! 2 2

2) Soit E un ensemble à n éléments et soit a ∈ E un élément xé. Il y a Pnk partitions de E en k

classes. Parmi ces partitions,
- il y a celles dans lesquelles a est dans un singleton, on les identie trivialement aux partitions en
k − 1 classes de E\{a}, et il y en a Pn−1k−1
,
- et celles dans lesquelles a n'est pas isolé. On les dénombre en partitionnant E\{a} en k classes puis
en adjoignant a à l'une de ces k classes, soit kPn−1k
possibilités.
Au total, cela donne bien la relation voulue : Pn = Pn−1
k k−1
+ kPn−1k

3) On suppose ici que n ≥ p. Si l'on veut créer une surjection d'un ensemble à n élément sur un
ensemble à p éléments, il faut d'abord déterminer le nombre de partitions en p classes de l'ensemble
de départ qui possède n éléments, soit Pnp . Ensuite, il faut choisir la façon d'envoyer les p classes sur
les p éléments de l'ensemble d'arrivée, soit p! possibilités. Au total, il y a p!Pnp surjections.
p p!
4) Par récurrence sur n : Hn : ∀k ≥ n, Nk,p = (−1)i (p − i)k .
P
i=0 i!(p − i)!

17 Thierry Sageaux