Correction TD 10 : dénombrement

I Dénombrement

Correction 1. Anagrammes d’ANANAS :

• Méthode 1 :
On commence par compter le nombre de permutations des lettres comme si elles étaient toutes
distinctes : on obtient alors 6! anagrammes possibles. Il faut alors compter le nombre de fois où
l’on a compté plusieurs fois le même mot : 3! permutations pour les A, et 2! permutations pour
6!
les N. Finalement on obtient : = 60 anagrammes différents.
3!2!
• Méthode 2 :
On essaye de remplir les 6 emplacements lettres par lettres (comme au jeu du pendu). Commen-
çons par choisir la place des A : on doit choisir 3 emplacements parmi 6, et ce sans ordre (car
l’ordre des A n’a pas d’importance, ce sont les mêmes lettres), et sans répétition car on ne peut
pas placer deux lettressur le même emplacement. On a donc des combinaisons de 3 lettres parmi
6
6 emplacements, soit possibilités. On doit ensuite placer les 2 N parmi les 3 emplacements
 3
3
restants, on a donc possibilités. Enfin, il ne reste qu’une possibilité pour la place du S. Ainsi,
2
   
6 3
on a × = 60 possibilités.
3 2

Correction 2. Rangement de billes dans des boîtes :

Exercice très classique qui correspond à la répartition de billes dans des boîtes distinctes selon que les
billes sont différentes ou non et que les boîtes peuvent contenir plusieurs billes ou non.
1. Comme les prospectus sont tous identiques, l’ordre dans lequel on les distribue dans les boîtes
n’intervient pas. De plus, comme les boîtes ne peuvent pas contenir plus d’un prospectus, il n’y
a pas de répétition possible. Ainsi, on est dans un cas où l’on doit choisir les 7 boîtes aux lettres
qui vont contenir un prospectus
  parmi 10 boîtes aux lettres, ce choix se faisant sans ordre et sans
10
répétition. Il y a donc façons de le faire.
7
2. Ici les prospectus sont tous différents et on peut par exemple imaginer qu’ils sont empilés selon
un certain ordre (prospectus alimentaire puis bancaire...). Ici, lorsque vous allez choisir les boîtes
aux lettres dans lesquelles vous allez mettre vos prospectus, l’ordre dans lequel vous choisissez
vos boîtes à lettre intervient car tous les prospectus sont différents. Cela ne va donc pas donner
le même résultat si vous choisissez d’abord la boîte aux lettres numéro 3 (qui reçoit donc le
prospectus alimentaire) puis la boîte aux lettres numéro 6 (qui reçoit donc le prospectus ban-
caire) ou si vous choisissez d’abord la boîte aux lettres numéro 6 (qui reçoit donc le prospectus
alimentaire) puis la boîte aux lettres numéro 3 (qui reçoit donc le prospectus bancaire). De plus,
comme chaque boîte ne peut pas en recevoir plus d’un, il n’y a pas de répétition possible. Il s’agit
donc de choisir 7 boîtes aux lettres parmi 10 en tenant compte de l’ordre et pas de répetition.
10! 10!
On a donc = façons de faire (ou alors 10 choix pour la première boîte aux lettres
(10 − 7)! 3!
choisie, puis 9 choix pour la seconde boîte aux lettres choisie...).
3. Ici, il s’agit de choisir 7 boîtes aux lettres parmi 10 avec cette fois-ci à la fois de l’ordre mais aussi
des répétitions car on peut mettre plusieurs prospectus dans chaque boîte aux lettres. On est
dans le cas où il y a à la fois de l’ordre et des répétitions. Le nombre de façons de faire correspond
aux nombres de 7−uplet d’éléments pris parmis 10 avec répétitions possibles. Il y a donc 107

BCPST1-Lycée Chaptal Page 1 2021/2022

 façons de faire. Une autre façon de voir les choses est la suivante : on a 10 choix possibles pour le
premier prospectus, 10 choix possibles pour le deuxième prospectus... et 10 choix pour le 7-ième
prospectus. Ainsi, on a bien 107 façons de faire.
4. Là, on est dans un cas où il n’y a pas d’ordre : en effet, les prospectus étant tous identiques,
l’ordre dans lequel on les distribue n’intervient pas. Par contre il y a de la répétition car plusieurs
prospectus peuvent être mis dans la même boîte aux lettres. Ici, la seule façon de faire est de
considérer les 7 prospectus et de rajouter les 9 séparations entre les 10 boîtes aux lettres. On
a donc en tout 16 emplacements possibles et il faut choisir la place des 9 séparations parmi
ces 16 places, sans ordre (les séparations
  sont identiques) et sans répétition (un seul objet par
16
emplacement). On obtient ainsi façons de faire.
9
Correction 3. Tirage de jetons dans une urne
1. On est dans un cas où l’ordre et la répétition interviennent puisque les jetons sont tirés succes-
sivement et avec remise.
(a) A chaque tirage, on a 13 choix : 13 choix pour le premier tirage, 13 choix pour le second...
Ainsi, on obtient 136 résultats possibles.
(b) i. Pour obtenir exactement un jeton noir, on doit : choisir à quel tirage on va tirer le jeton
noir : il y a 6 choix possibles. Ensuite pour chaque choix de numéro de tirage, on a : 8
choix possibles de jetons noirs et pour les 5 autres tirages, on a 5 possibilités à chaque
fois (5 jetons blancs). Ainsi, on obtient : 6 × 8 × 55 résultats possibles.
ii. On passe à l’ensemble complémentaire. Si on note A l’ensemble des tirages avec au moins
un jeton noir et E l’ensemble des tirages possibles, on a : Card(A) = Card(E)−Card(A).
Et A est l’ensemble des tirages sans aucun jeton noir. On a donc Card(A) = 56 : à chaque
tirage, on a 5 choix de jetons (les 5 jetons blancs) et il y a 6 tirages ordonnés. Ainsi, on
obtient Card(A) = 136 − 56 .
iii. On note A l’ensemble des tirages avec au plus un jeton noir. C’est l’union disjointe de B
l’ensemble des tirages avec exactement aucun jeton noir et de C l’ensemble des tirages
avec exactement un jeton noir. Or on a déjà vu que : Card(B) = 56 et Card C = 6×8×55 .
Ainsi, on obtient que : Card(A) = Card(B) + Card(C) = 56 + 6 × 8 × 55 .
iv. Pour avoir 2 fois plus de jetons noirs que de blancs avec 6 tirages, la seule solution est
de tirer 2 jetons blancs et 4 jetons
  noirs. On commence par fixer la place des 2 jetons
6
blancs parmi les 6 tirages : . Les jetons noirs étant alors placés dans les places
2
restantes. Puis il y a 52 choix
  pour les jetons blancs et 84 choix possibles pour les jetons
6
noirs. On obtient au final × 52 × 84 résultats possibles.
2
2. On est dans un cas où l’ordre intervient mais où il n’y a pas répétition puisque les jetons sont
tirés successivement et sans remise.
(a) Il s’agit donc ici de choisir 6 jetons parmi 13 jetons avec ordre et sans remise, on obtient
13! 13!
donc des 6 listes sans répétition, soit = . Une autre façon de le voir est de
(13 − 6)! 7!
dire : pour le premier tirage, j’ai 13 choix, pour le deuxième tirage, j’ai 12 choix... et pour le
13!
dernier tirage, j’ai 8 choix. Ainsi, on a : 13 × 12 × 11 × 10 × 9 × 8 = résultats possibles.
7!
(b) i. Pour obtenir exactement un jeton noir, on doit : choisir à quel tirage on va tirer le jeton
noir : il y a 6 choix possibles. Ensuite pour chaque choix de numéro de tirage, on a :
8 choix possibles de jetons noirs et pour les 5 autres tirages, on doit choisir 5 jetons
parmi 5 sans remise mais avec ordre : 5 × 4 × 3 × 2 × 1 = 5!. Ainsi, on obtient : 6 × 8 × 5!
résultats possibles.
ii. On passe à l’ensemble complémentaire. Si on note A l’ensemble des tirages avec au moins
un jeton noir et E l’ensemble des tirages possibles, on a : Card(A) = Card(E)−Card(A).
Et A est l’ensemble des tirages sans aucun jeton noir. On a donc Card(A) = 0. En effet,
comme il n’y a pas de remise et que l’on fait 6 tirages alors qu’il n’y a que 5 jetons blancs,
13!
il n’y a aucun tirage sans jeton noir. Ainsi, on obtient Card(A) = Card(E) = .
7!

BCPST1-Lycée Chaptal Page 2 2021/2022

 iii. On note A l’ensemble des tirages avec au plus un jeton noir. C’est l’union disjointe de B
l’ensemble des tirages avec exactement aucun jeton noir et de C l’ensemble des tirages
avec exactement un jeton noir. Or on a déjà vu que : Card(B) = 0 et Card C = 6×8×5!.
Ainsi, on obtient que : Card(A) = Card(C) = 6 × 8 × 5!.
iv. Pour avoir 2 fois plus de jetons noirs que de blancs avec 6 tirages, la seule solution est
de tirer 2 jetons blancs et 4jetons
 noirs. On commence par fixer la place des 2 jetons
6
blancs parmi les 6 tirages : . Les jetons noirs étant placés dans les places restantes.
2
Puis il y a 5 × 4 choix pour les jetons
  blancs et 8 × 7 × 6 × 5 choix possibles pour les
6
jetons noirs. On obtient au final × 5 × 4 × 8 × 7 × 6 × 5 résultats possibles.
2
3. On est alors dans un cas où il n’y a ni ordre ni répétition car les jetons sont tirés simultanément.
(a) Il s’agit
 donc
 de choisir 6 jetons parmi 13 jetons sans ordre et sans répétition. On obtient
13
donc résultats possibles.
6
(b) i. On doit choisir 1 jeton noir parmi les 8 et 5 jetons blancs parmi les 5. En fait la poignée
de jetons que vous devez obtenir doit contenir les 5 jetons
  blancs
 et un jeton noir. On
8 5
a donc 8 résultats possibles ce qui est bien égal à × .
1 5
ii. On passe à l’ensemble complémentaire. Si on note A l’ensemble des tirages avec au moins
un jeton noir et E l’ensemble des tirages possibles, on a : Card(A) = Card(E)−Card(A).
Et A est l’ensemble des tirages sans aucun jeton noir. On a donc Card(A) = 0. En effet,
comme il n’y a pas de remise et que l’on tire 6 jetons alors qu’il n’y a que 5 jetonsblancs,

13
il n’y a aucun tirage sans jeton noir. Ainsi, on obtient Card(A) = Card(E) = .
6
iii. On note A l’ensemble des tirages avec au plus un jeton noir. C’est l’union disjointe de B
l’ensemble des tirages avec exactement aucun jeton noir et de C l’ensemble des tirages
avec exactement un jeton noir. Or on a déjà vu que : Card(B) = 0 et Card C = 8.
Ainsi, on obtient que : Card(A) = Card(C) = 8.
iv. Pour avoir 2 fois plus de jetons noirs que de blancs avec 6tirages,
  laseule solution est de
5 8
tirer 2 jetons blancs et 4 jetons noirs. On obtient donc × résultats possibles.
2 4
Correction 4. Rangement de billes dans des boîtes :
On est dans le cas classique où il faut répartir 8 objets (différents ou distincts) parmi 13 singes distincts
(ou boîtes), chaque singe pouvant en avoir soit 0 ou 1 ou plusieurs.
1. (a) Les fruits sont différents donc le choix de nos singes se fait avec ordre. Et il n’y a pas de
répétitions possibles dans le choix des singes car chaque singe peut recevoir au plus un fruit.
13! 13!
On doit donc compter le nombre de 8-listes parmi les 13 singes, donc il y a =
(13 − 8)! 5!
distributions possibles.
(b) Les fruits sont différents donc le choix de nos singes se fait avec ordre. Et il y a des répétitions
possibles dans le choix des singes car chaque singe peut recevoir 0, 1 ou plusieurs fruits. On
doit donc compter le nombre de 8-listes avec répétition parmi les 13 singes, donc il y a 138
distributions possibles.
On peut aussi refaire le raisonnement : j’ai 13 choix pour la banane, 13 choix pour la pomme,
13 choix pour la poire...en tout, j’ai donc 138 distributions possibles.
2. (a) Les fruits sont tous identiques donc le choix de nos singes se fait sans ordre. Et il n’y a pas
de répétitions possibles dans le choix des singes car chaque singe peut recevoir au plus  un 
13
fruit. On doit compter le nombre de combinaisons de 8 singes parmi 13, donc il y a
8
distributions possibles.
(b) Les fruits sont tous identiques donc le choix de nos singes se fait sans ordre. Et il y a des
répétitions possibles dans le choix des singes car chaque singe peut recevoir 0, 1 ou plusieurs
fruits. On est dans le cadre du choix de 8 singes parmi les 13 singes et ce choix se fait sans

BCPST1-Lycée Chaptal Page 3 2021/2022

 ordre et avec répétition. La seule manière de modéliser cela est de rajouter à nos 8 fruits
identiques 12 séparations entre les singes. On a donc en tout 20 emplacements différents
possibles et il faut choisir la place des 12 séparations parmi ces 20 places disponibles sans
ordre (les
 séparations
 sont identiques) et sans répétition (un seul objet par séparation). On
20
a donc distributions possibles.
12
Correction 5. Tirage de boules dans une urne

1. On est dans un cas où il y a ordre et répétition. Un résultat est un 6-uplet de boules pris dans
un ensemble de 13 boules. On a donc 13 choix pour le premier tirage, 13 choix pour le second
tirage... et ainsi on obtient 136 résultats possibles.
2. (a) On a 5 choix possibles pour le premier tirage, 5 choix possibles pour le second tirage,...,
puis 5 choix possibles pour le cinquième tirage et 8 choix possibles pour le dernier tirage.
Au final, on obtient 55 × 8 résultats possibles.
(b) Pour obtenir exactement une boule noire, on doit : choisir à quel tirage on va tirer la boule
noire : il y a 6 choix possibles. Ensuite pour chaque choix de numéro de tirage, on a : 8
choix possibles de boules noires et pour les 5 autres tirages, on a 5 possibilités à chaque fois
(5 boules blanches). Ainsi, on obtient : 6 × 8 × 55 résultats possibles.
(c) On passe à l’ensemble complémentaire. Si on note A l’ensemble des tirages avec au moins
une boule noire et E l’ensemble des tirages possibles, on a : Card(A) = Card(E) − Card(A).
Et A est l’ensemble des tirages sans aucune boule noire. On a donc Card(A) = 56 : à chaque
tirage, on a 5 choix de boules (les 5 boules blanches) et il y a 6 tirages ordonnés. Ainsi, on
obtient Card(A) = 136 − 56 .
(d) On considère que l’on veut strictement plus de boules noires que blanches. C’est donc la
réunion disjointe de 0 boule blanche et 6 boules noires ou 1 boule blanche et 
5 boules
 noires
6
6 5
ou 2 boules blanches et 4 boules noires. On obtient ainsi : 8 + 6 × 5 × 8 + × 5 × 84 .
2
2
Correction 6. Jeu de cartes :
1. On est dans un cas où il n’y a pas d’ordre ni de répétition.
 Il s’agit donc de choisir 8 cartes parmi
52
52 sans ordre ni répétition. On obtient donc mains différentes.
8
2. Une solution est de passer par le complémentaire. Si on pose A : ensemble des mains possibles avec
au moins un as et E : ensemble des mains possibles. On obtient : Card(A) = Card(E) − Card(A).
De plus, on a : A : ensemble des mains possibles sans aucun as et ainsi il s’agit de choisir 8
cartes
  non  parmi 52 mais parmi 48 car on enlève les 4 as. On obtient ainsi : Card(A) =
 plus
52 48
− .
8 8
3. Là encore on peut passer par l’ensemble complémentaire. Si on pose B : ensemble des mains
possibles avec au moins (un coeur ou une dame) et E : ensemble des mains possibles. On obtient :
Card(B) = Card(E) − Card(B). De plus, on a : B : ensemble des mains possibles sans coeur et
sans dame et ainsi il s’agit de choisir 8 cartes non plus parmi 52 mais parmi 36 car on enlève les
52 36
13 coeurs et les 3 dames restantes. On obtient ainsi : Card(A) = − .
8 8
4. Il faut faire attention à l’as de coeur. On note C : l’ensemble des mains possibles avec exactement
un as et exactement un coeur mais sans l’as de coeur, D l’ensemble des mains possibles avec l’as
de coeur et aucun coeur et as pour les autres cartes et E l’ensemble des mains possibles avec
exactement un as et un coeur. On a bien E = C ∪ D et les deux ensembles C et D sont
bien disjoints. Ainsi, on obtient Card(E) = Card(C) + Card(D). Le cardinal de C s’obtient
en choisisant une carte parmi les 3 as ne contenant pas l’as de coeur, une carte parmi les 12
cartes de coeur sans l’as de coeur et les 6 cartes restantes
 parmi  les 36 cartes restantes n’étant
3 12 36
ni des coeur ni des as. On a donc : Card(C) = . Pour D, il faut prendre l’as de
1 1 6
coeur, soit une seule possibilité, puis il faut prendre les 7 cartes restantes parmi les 36 autres

BCPST1-Lycée Chaptal Page 4 2021/2022

  
36
cartes n’étant ni des coeurs ni des as. On obtient ainsi Card(D) = 1 × . Ainsi, on a :
      7
3 12 36 36
Card(E) = + .
1 1 6 7
5. On commence  par faire le choix de la couleur, on a donc 2 choix parmi 4 sans ordre et sans
4
répétition : . Une fois le choix de la couleur fait, il faut prendre nos 8 cartes parmi les cartes
2
de ces deux couleurs à savoir on doit prendre 8 cartes parmi les 26 cartes des deux couleurs
choisies. On a compté en trop le cas  où nos 8 cartes étaient en fait toutes prises de la même
26
couleur. Il faut donc retirer à le nombre de possibilités que l’on a d’avoir pris en fait 8
8  
13
cartes de la même couleur, à savoir : 2 × . On le compte 2 fois car il y a deux couleurs.
      8
4 26 13
Finalement, on obtient : −2 .
2 8 8
6. On veut choisir au plus deux couleurs, c’est-à-dire exactement une ou bien exactement deux.
On a calculé le nombre de tirages avec exactement deux couleurs à la question précédente.  
13
De plus, pour choisir des cartes d’une seule couleur, on a 4 choix pour la couleur, puis
8
possibilités pour les tirages. Comme les tirages d’une couleur et de deux couleurs sont disjoints,
le cardinal
  de  l’union
 des deux ensembles
 est la somme des cardinaux, et on en déduit que l’on
4 26 13 13
a −2 +4 possibilités.
2 8 8 8
7. On commence par faire le choix de la plus petite carte : on a 6 choix pour la valeur de la plus
petite carte : du 2 au 7. Une fois ce choix fait, cela détermine le choix des 8 autres valeurs puisque
les valeurs doivent se suivrent strictement. Par exemple, si la plus petite carte est un 4 ensuite on
doit
  avoir un 5,6,7,8,9,10,Valet. Puis, comme il y a 4 couleurs par valeur, on obtient finalement :
6
× 48 .
1
Correction 7. Paires de chaussures :
1. Il y a 20 chaussures en tout (on considère que toutes les chaussures sont distinctes même les
chaussures
  de la même couleur) et on en prend 2. Il n’y a pas d’ordre ni de répétition et on a :
20
tirages possibles.
2
2. Si on note E l’ensemble des tirages où l’on obtient deux chaussures de la même couleur, on a :
E = EN ∪ EM ∪ EB avec EN ensemble des tirages avec 2 chaussures de la couleur noire et pareil
pour EM et EB . Comme il y a respectivement 10 chaussures noires, 6 chaussures marrons et 4
chaussures blanches et que ces trois ensembles EN , EM et EB sont des ensembles disjoints, on
obtient      
10 6 4
Card(E) = Card(EN ) + Card(EM ) + Card(EB ) = + + .
2 2 2
3. On fait le choix d’une chaussure de pied droit par exemple
 et  à chaque choix fait, on fait le choix
10 10
d’une chaussure de pied gauche. On obtient alors : = 10 × 10 = 100.
1 1
4. Si on note A l’ensemble des tirages où l’on obtient deux chaussures de la même couleur avec une
chaussure droite et une chaussure gauche, on a : A = AN ∪ AM ∪ AB avec AN ensemble des
tirages avec 2 chaussures de la couleur noire avec une chaussure droite et une chaussure gauche
et pareil pour AM et AB . Ainsi, on obtient

Card(A) = Card(AN ) + Card(AM ) + Card(AB ) = 5 × 5 + 3 × 3 + 2 × 2.

Correction 8. Tournoi de tennis

1. • Une façon de voir les choses est de se dire que l’on compte le nombre de façons de classer
tous les joueurs : on ordonne tous les joueurs de tennis du tournoi : il y a donc de l’ordre
et pas de répétition possible et on a (2n)! possibilités. Ensuite pour faire les matchs, on

BCPST1-Lycée Chaptal Page 5 2021/2022

 regroupe tous les joueurs ordonnés par paire : le 1 joue contre le 2, le 3 joue contre le 4....
Ici, pour chaque match, on a compté comme 2 possibilités : Bertrand joue contre Fred et
Fred joue contre Bertrand. Donc il faut diviser par 2n car il y a n matchs. Ainsi, on obtient :
(2n)!
organisations possibles du premier tour.
2n
• Une autre façon de voir les choses est la suivante : on choisit d’abord 2 joueurs parmi les
2n joueurs pour jouer le match numéro 1, puis 2 autres joueurs parmi les joueurs restants,
à savoir parmi les 2n − 2 joueurs restants, puis encore 2 autres joueurs parmi les 2n − 4
joueurs restant....chaque choix de 2 joueurs parmi les joueurs restants se fait sans répétition
et sans ordre car le match est le même si on commence par choisir M.X puis M.Y ou si on
commence par choisir M.Y puis M.X : ainsi l’ordre n’intervient pas. Ainsi, le choix des 2
joueurs se fait sans ordre et sans répétition donc des combinaisons à 2 éléments. Finalement,
on obtient          
2n 2n − 2 2n − 4 4 2
× × ... × .
2 2 2 2 2
Si on écrit les coefficients binomiaux sous forme de factorielle, il y a beaucoup de simplifi-
(2n)!
cations et on obtient bien le même résultat, à savoir : .
2n
2. Si l’ordre des matchs n’est plus pris en compte, il faut en plus diviser par le nombre de permu-
(2n)!
tations possibles des matchs, à savoir n!. On obtient alors n .
2 n!
Correction 9. Sudoku
On commence par numéroter les différents pions. Si p > n, il n’y a pas de manière possible. Si p ≤ n, on
a : on prend le jeton numéroté 1, il y a n2 places possibles. Le premier jeton étant placé, cela supprime
toute une ligne et toute une colonne entière et il y a donc (n − 1)2 places possibles pour le deuxième
jeton....on continue ainsi jusqu’au jeton numéro p. On obtient ainsi

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

Mais il faut ensuite supprimer l’ordre que l’on a mis en numérotant les jetons : à toute disposition
NON numérotée correspond p! dispositions numérotées (le nombre de façons de permuter les p jetons).
N n2 (n − 1)2 . . . (n − p + 1)2
Ainsi, on obtient = .
p! p!
Correction 10. Nombre d’appels à M. X

1. On commence parchoisir les k positions des appels à M. X : on doit donc choisir k places parmi
n
les n places : choix possibles. Une fois que le choix des appels de M. X est fait, pour les
k
autres appels, on a le choix de N − 1 individus (car on ne peut pas appeler M. X) et il y a de
l’ordre et de la répétition. Ainsi, pour chaque appel, on a N − 1 choix et cela pour les n − k
 
n
appels restantes. Finalement, on obtient : (N − 1)n−k résultats où M. X est appelé k fois.
k

  ici par faire le choix des k places où M. X a été appelé parmi les r premiers appels,
2. On commence
r
à savoir . Pour les r − k autres appels compris dans les r premiers appels, on ne doit plus
k
rappeler M. X et ainsi, on a (N − 1)r−k choix. Ensuite pour tous les appels après le r-ième appel,
on peut faire le choix d’un individu quelconque d’où N n−r choix possibles. Au final, on obtient
 
r
(N − 1)r−k N n−r résultats où M. X est appelé k fois au cours des r premiers appels.
k
3. Il faut que M. X ait été appelé k − 1 fois au cours des t − 1 premiers appels, puis qu’on l’appelle
au t-ième appel, et ensuite qu’on appelle n’importe quel individu. En raisonnant comme préce-
 
t−1
demment, on obtient (N − 1)t−k N n−t résultats où M. X est appelé pour la k-ième fois
k−1
au t-ième appel.

BCPST1-Lycée Chaptal Page 6 2021/2022

 Correction 11. Codes :
1. Ici, l’ordre intervient et des répétitions sont possibles. Ainsi, on obtient 3 choix pour la lettre
et pour chaque lettre choisie, on obtient ensuite une 3-liste prise parmi les 9 chiffres. Ainsi le
nombre de codes différents est : 3 × 93 .
2. (a) Ici l’ordre intervient toujours mais il n’y a pas de répétition possible car les 3 chiffres doivent
être distincts. On compte donc le nombre de 3-listes sans répétition parmi les 9 chiffres, et
on obtient 3 × (9 × 8 × 7) codes différents lorsque les trois chiffres sont distincts.
(b) On note A l’ensemble des codes contenant au moins le chiffre 7. On a : Card(A) = 3 ×
93 − Card(A). Et ici, A est l’ensemble des codes ne contenant pas le chiffre 7. Ainsi, on a :
Card(A) = 3 × 83 et
Card(A) = 3 × 93 − 3 × 83 .
(c) Tous les chiffres doivent être pairs donc il s’agit de ne prendre que les chiffres 2, 4, 6 et 8.
Ainsi, on obtient, comme il y a toujours de l’ordre et des répétitions possibles : 3 × 43 .
(d) On cherche le nombre de façons de choisir 3 chiffres parmi 9 :
• sans ordre, puisqu’une fois les nombres choisis, l’ordre est imposé : les chiffres doivent
être entrés dans l’ordre croissant (donc que l’on choisisse 1, 2 puis 3 ou 3, 2, puis 1, cela
revient au même, dans tous les cas on rentrera 1, 2, 3 pour le code),
• sans répétition, car comme l’ordre doit être strict, les nombres doivent distincts.
 
9
On cherche donc le nombre de combinaisons de 3 éléments parmi 9, on obtient donc
3
possibilités
  pour les chiffres. En ajoutant les 3 choix possibles pour les lettres, on a donc
9
3× possibilités.
3
Correction 12. Nombres
1. Lorsqu’un nombre a strictement moins de r chiffres, on rajoute des 0 non significatifs à gauche.
Ainsi, quitte à rajouter des 0 non significatifs à gauche, un résultat est une r-liste d’éléments pris
parmi les 10 chiffres avec répétitions possibles. Il y a donc 10r nombres de r chiffres au plus.
2. Pour avoir r chiffres exactement, le nombre ne peut pas commencer par 0 donc il n’y a que 9
choix possibles pour le premier chiffre le plus à gauche. Ensuite, il y a pour chaque chiffre 10 choix
possibles avec ordre et répétitions possibles. Ainsi le nombre de nombre de r chiffres exactement
est 9 × 10r−1 .
3. Pour avoir r chiffres exactement, il ne faut pas de 0 au début à gauche : il y a donc 9 choix
possibles. Ce premier nombre de gauche a étant choisi, le reste constitue une r −1-liste d’éléments
pris parmi {0, . . . 9}\{a} car on ne peut pas reprendre a. Ainsi, si r −1 > 9, c’est-à-dire si r > 10 :
9!
il n’y a pas de tel nombre. Sinon, on a : 9 × tels nombres.
(9 − (r − 1))!
Correction 13. Nombres bis Pour que des entiers soient strictement inférieurs à 10p , il faut
qu’ils aient p chiffres au plus. Ainsi, quitte à rajouter des 0 non significatifs à gauche, on peut considérer
qu’ils ont exactement p chiffres. La somme des chiffres doit faire 3, il y a donc trois ensembles disjoints
possibles : l’ensemble A où le chiffre 3 figure et ainsi, tous les autres chiffres sont 0 ; l’ensemble B où
il y a un 2 et un 1 qui figurent et tous les autres chiffres sont 0 et enfin l’ensemble C où il y a trois
1 qui figurent et tous les autres chiffres sont 0. Ces trois ensembles sont bien disjoints donc en notant
E l’ensemble des entiers strictement inférieur à 10p dont la somme des chiffres est égale à 3, on a :
E = A ∪ B ∪ C. Et Card E = Card A + Card B + Card C car les trois ensembles sont disjoints. Or
Card A = p : il y a autant de choix possibles que de choix de la case où mettre le 3 ou encore je choisis
la place où va être mon 3 et tout le reste, c’est des 0 donc p choix possibles. Card B = p(p − 1) : il s’agit
de 2-listes sans répétition car on choisit les deux places pour le 1 et le 2 et l’ordre intervient ici. En effet
un nombre avec un 1 à la place 3 et un 2 à laplace  7 n’est pas le même nombre que si le 2 est à la place
p
3 et le 1 à la place 7. Par contre, Card C = car comme c’est le même nombre, l’ordre n’intervient
3  
p
pas ici : on choisit les 3 emplacements du 1 sans ordre. On a donc finalement p + p(p − 1) +
3
possibilités.

BCPST1-Lycée Chaptal Page 7 2021/2022

 Correction 14. Nombres ter
1. Un résultat est une liste ordonnée sans répétition. On a donc 6! nombres de 6 chiffres distincts
avec 1,2,3,4,5,6.
2. On compte pour cela tous ceux qui sont plus petits que lui. On commence par le premier chiffre
le plus à gauche : tous les nombres commençant par 1,2 ou 3 sont plus petit que lui : ainsi, il
en a : 5! nombres qui commencent par 1, 5! nombres qui commencent par 2 et 5! nombres qui
commencent par 3. Si un nombre commence par 4, pour savoir s’il est plus grand ou plus petit
que 453216, il faut regarder son deuxième chiffre en partant de la gauche. S’il vaut 1,2,3 (pas
4 car on ne peut pas avoir de répétitions) alors tous ces nombres sont plus petits que 453216.
Il y en a 4! qui commence par 41, 4! qui commencent par 42...et si le nombre commence par
45, il faut alors regarder le troisième chiffre en partant de la gauche... On obtient à la fin :
3 × 5! + 3 × 4! + 2 × 3! + 2! = 446. Il y a donc 446 nombres avant lui, il est donc le 447-ième.
3. Pour sommer tous ces nombres, une façon de faire est de sommer par unités, dizaine, cen-
taine...séparément. Commençons par sommer les unités : il y a 5 ! nombres qui se terminent
par 1, 5 ! qui se terminent par 2, 5 ! qui se terminent par 3....5 ! qui se terminent par 6. Ainsi,
pour les unités on obtient : (5! × 1 + 5! × 2 + 5! × 3 + · · · + 5! × 6) × 100 = 5! × 21 × 100 . On refait
le même raisonnement pour les dizaines : il y a 5! × 21 × 101 dizaines. Ainsi, au final on obtient :
5! × 21 × (100 + 101 + · · · + 105 ) = 5! × 21 × 111111.

Correction 15. Rangement de billes dans des boîtes :

1. On commence par reformuler l’exercice sous la forme suivante : on a n billes identiques et on doit
les répartir dans p boîtes distinctes. On note alors xi le nombre de billes qu’on met dans la boîte
i. Comme les nombres (x1 , x2 , . . . , xp ) ne peuvent pas être nuls, les boîtes ne peuvent donc pas
être vides (elles pourront l’être dans le 2. et on pourra alors raisonner comme d’habitude dans le
cas de répartition de n objets identiques à répartir dans p boîtes distinctes chaque boîte pouvant
en contenir 0,1 ou plusieurs). Ici, comme les boîtes ne peuvent pas être vides, on doit faire un
peu attention : si on représente nos n billes par des ronds et les p − 1 séparations parmi ces n
objets par des barres, on a : par exemple ◦| ◦ ◦| ◦ | ◦ ◦◦. Ainsi, on doit répartir les separations
parmis les n − 1 emplacements qui se trouvent entre les billes (mais on ne peut pas mettre deux
séparations à la suite car on aurait des boites vides). Si l’on représente les emplacement possibles
des séparations par des points, on aurait ainsi les possibilités suivantes : ◦. ◦ . ◦ . ◦  . ◦ . ◦ .◦.Il s’agit
n−1
donc de choisir p − 1 séparations parmi les n − 1 espaces disponibles. Il y a donc façons
  p−1
n−1
de faire ceci et donc solutions (x1 , x2 , . . . , xp ) ∈ (N? )p de l’équation x1 + x2 + . . . xp = 0.
p−1
2. Il y a deux façons de faire :
• On peut utiliser le résultat précédent. Soit (x1 , . . . , xp ) ∈ Np et posons, pour tout i ∈
{1, . . . , p} : yi = xi +1. On a alors : (x1 , . . . , xp ) ∈ Np est solution de l’équation x1 +· · ·+xp =
n si et seulement si (y1 , . . . , yp ) est solution de l’équation y1 +· · ·+yp = n+p dans ? p
 (N ) . Par
n+p−1
conséquent, d’après la question précédente (en remplaçant n par n + p), il y a
p−1
solutions (x1 , . . . , xp ) de l’équation x1 + · · · + xp = n dans Np .
• On peut retrouver ce résultat par un raisonnement direct. Cette fois-ci, il s’agit bien de
répartir nos n objets dans p boîtes distinctes, chaque boîte pouvant en contenir 0, un ou
plusieurs. On est donc exactement dans le cadre d’application du cours : on considère donc
nos n ronds blancs et on rajoute p−1 barres (ou billes noires) qui modélisent les séparations.
Par exemple, pour n = 4 et p = 5, ◦ ◦ || ◦ | ◦ | représente le quintuplet (2, 0, 1, 1, 0) solution
de x1 + x2 + · · · + x5 = 4 dans N5 . Il s’agit donc de répartir les p − 1 barres (ou 
billes noires)

n+p−1
parmi les n + p − 1 emplacements (n objets et p − 1 séparations) : on a donc
p−1
possibilités. On retrouve bien le résultat précédent.

BCPST1-Lycée Chaptal Page 8 2021/2022

II Formules démontrées à l’aide du dénombrement

Correction 16. Chemins le long d’un quadrillage

1. Vous pouvez commencer par faire un exemple avec par exemple n = 5 pour comprendre comment
cela fonctionne.
• A chaque déplacement, il y a deux choix possibles : soit vers la droite, soit vers le haut. Ainsi,
un chemin croissant est une succession de déplacements de type d (vers la droite) et de type
h (vers le haut). L’ordre intervient car le chemin n’est pas le même si on a commencé par
se déplacer vers la droite puis vers le haut ou si on a fait l’inverse. De plus, il y a répétition
possible car on peut bien entendu se déplacer plusieurs fois vers le haut et plusieurs fois vers
la droite. Ainsi, un chemin croissant de longueur n est un n-uplet d’éléments h ou d. Il y en
a 2n choix possibles.
• Au bout de n déplacements, on atteint un point de la forme (k, p) avec k + p = n, soit
p = n − k. Ainsi les points atteints sont les points (k, n − k), avec k ∈ {0, . . . , n}, qui
correspondent à la diagonale du carré n × n. Il y a donc n + 1 points distincts.
2. (a) Pour relier A et B, il suffit de faire successivement m déplacements vers la droite et n dé-
placements vers le haut et ceci dans n’importe quel ordre. On a donc m + n déplacements
à faire au total. On commence par choisir le nombre de façon de placer les m déplacements
la droite: on doit choisir m déplacements parmi n + m, sans ordre et sans répétition,
vers 
n+m
soit . Il n’y a ensuite plus le choix pour les autres déplacements, qui sont néces-
m  
m+n
sairement des déplacements vers le haut. On obtient donc : chemins croissants
m
permettent de relier A et B.

(b) Comme dans la question précédente, pour relier A et Ck , il suffit de faire successivement k
déplacements vers la droite et p−k déplacements vers le  soit p−k+k = p déplacements
haut,
p
au total. Avec le même raisonnement, on obtient donc chemins possibles de A jusqu’à
k
Ck .
Puis pour relier Ck et B, il suffit de faire successivement m − k déplacements vers la droite
et n − (p − k) déplacementsvers le haut,  soit m − k + n − (p − k) = m + n − p déplacements
m+n−p
au total. On obtient donc chemins possibles de Ck à B (on remarque que ce
m−k
nombre de chemins est bien nul dès  quek >m où que p− k > n).
p m+n−p
Ces choix sont successifs, on a donc × chemins possibles pour aller de A
k m−k
à B en passant par Ck .
On veut en déduire une autre formule pour le nombre de chemins de A à B. Pour aller de
A à B, au bout de p déplacements, on est forcément sur un point de la forme (k, p − k),
avec k ∈ {0, . . . , p}. Il suffit donc de sommer ces différentes possibilités, et on obtient
p   
X p m+n−p
Sachant que les termes de la somme sont nuls dès que k > m, et en
k m−k
k=0
identifiant avec le résultat trouvé à la question précédente, on a donc :
m     
X p m+n−p m+n
= .
k m−k m
k=0

Pour retrouver la formule de Vandermonde, il suffit de faire un changement dans le nom des
variables, et poser M = m + n − p, N = p et R = m. On obtient alors
R     
X N M M +N
= ,
k R−k R
k=0

ce qui est bien la formule voulue.

BCPST1-Lycée Chaptal Page 9 2021/2022

 Correction 17. Formule du multinôme (deuxième question plus dure)
(p + q + r)!
1. On raisonne ici comme pour les anagrammes. On obtient donc mots différents.
p!q!r!
2. Calcul de (a + b + c)n :
Le terme général est de la forme ap bq cr avec p + q + r = n. De plus, un tel terme va apparaître
lorsque l’on développe complétement (a + b + c)n autant de fois que l’on peut former de mots de
n lettres en utilisant p fois la lettre a, q fois la lettre b et r fois la lettre c. Ainsi, le terme ap bq cr
(p + q + r)!
devra être sommé fois. On obtient ainsi que
p!q!r!
n n−p
X X (p + q + r)!
(a + b + c)n = ap bq cr .
p!q!r!
p=0 q=0

En effet, on commence par choisir p variant de 0 à n, puis il faut choisir q variant de 0 à n − p

et enfin pour r, on est obligé de prendre r = n − p − q.
De plus, comme r = n − p − q, on a :
  
(p + q + r)! n! n n−p n! (n − p)! n!
= et = × = .
p!q!r! p!q!(n − p − q)! p q p!(n − p)! q!(n − p − q)! p!q!(n − p − q)!
  
(p + q + r)! n n−p
On a donc : = . En remplaçant dans la somme, on obtient bien le
p!q!r! p q
résultat voulu, à savoir :
n n−p
X X nn − p
n
(a + b + c) = ap bq cn−p−q .
p q
p=0 q=0

Correction 18. Démonstration d’une formule par le dénombrement

1. Il s’agit ici de dénombrer le nombre de mots formés avec des A et des B. L’ordre intervient donc
et il y a répétitions possibles : on peut prendre plusieurs fois la lettre A et plusieurs fois la lettre
B. Un tel mot est donc une (p + q + 1)-liste de deux lettres et on obtient ainsi

Card(M) = 2p+q+1 .

2. • On veut que le p + 1-ième A se trouve en p + k-ième position. Cela signifie que les p + k − 1
premières lettres comporte p lettres A. Pour les p+k −1 premières lettres, il y a donc autant
 que de façons de placer ces p lettres A parmi les p + k − 1 lettres : on a donc
de possibilités

p+k−1
choix possibles. Ensuite la p + k-ième lettre est un A et il y a donc une seule
p
possibilité. Puis, pour les q − k + 1 lettres restantes, il n’y a pas de restriction : on a donc
2q−k+1 possibilités. Au final, on obtient
 
p + k − 1 q−k+1
Card(Nk ) = 2 .
p

• Il est cair que (N1 , . . . Nq+1 ) est un système complet de N puisque le p + 1-ième A se trouve
entre la position p + 1 et la position p + q + 1 et les Ni sont bien 2 à 2 disjoints. Par
conséquent, on a
q+1 q+1  
X X p + k − 1 q−k+1
Card(N ) = Card(Nk ) = 2 .
p
k=1 k=1

3. En utilisant un raisonnement similaire pour R (le q + 1-ième B pouvant se trouver entre la

position q + 1 et la position p + q + 1), on obtient, en remplaçant simplement p par q dans la
formule précédente,
p+1 p+1  
X X q + k − 1 p−k+1
Card(R) = Card(Rk ) = 2 .
q
k=1 k=1

BCPST1-Lycée Chaptal Page 10 2021/2022

 4. Comme un mot de M comporte p + q + 1 lettres, il comporte nécessairement ou bien au moins
p + 1 lettres A, ou bien au moins q + 1 lettres B, ce qui s’écrit M = N ∪ R. Ensuite, N ∩ R
désigne l’ensemble des mots de M comportant au moins p + 1 lettres A et q + 1 lettres B, ce
qui n’est pas possible car un mot de M a p + q + 1 lettres seulement. Ainsi, N ∩ R = ∅. Par
conséquent
Card(M) = Card(N ) + Card(R)

p+1
  q+1  
P p + k − 1 q−k+1 X q + k − 1 p−k+1
= 2 + 2
k=1 p q
k=1

p
  q  
P p + k q−k X q + k p−k
= 2 + 2
k=0 p q
k=0

en posant k 0 = k − 1 dans les deux sommes. En utilisant alors la question 1, on obtient

p   q  
X p + k q−k X q + k p−k
2 + 2 = 2p+q+1 .
p q
k=0 k=0

5. On applique alors la formule précédente pour p = q et cela nous donne

p   p  
X p + k p−k X p + k p−k
2 + 2 = 22p+1 .
p p
k=0 k=0
On divise alors par 2 de chaque côté et on obtient
p  
X p + k p−k
2 = 22p .
p
k=0

Si on pose alors k0 = p + k, on a :
p   2p  
X p + k p−k X k 2p−k
2 = 2 = 22p .
p p
k=0 k=p

On obtient bien la formule voulue.

Correction 19. Soit E un ensemble de cardinal n ∈ N? .
1. Notons C l’ensemble des couples (A, B) de parties de E vérifiant B ⊂ A :
n o
C = (A, B) ∈ (P(E))2 , B ⊂ A .
Il s’agit donc de calculer le cardinal de C. On commence par remarquer que si A est une partie
de E fixée, il y a autant de couple (A, B) ∈ (P(E))2 vérifiant B ⊂ A que de parties B de A,
c’est-à-dire 2Card(A) au total. Il semble donc naturel de dénombrer C en discutant sur le nombre
d’éléments de A.
Pour tout p ∈ {0, . . . , n}, notons Cp l’ensemble des couples (A, B) de C tels que Card(A) = p.
On a clairement C = C0 ∪ C1 ∪ · · · ∪ Cn puisqu’une partie A de E a un cardinal compris entre 0
et n. Ensuite les Ci sont 2 à 2 disjoints : en effet, un couple (A, B) de Ci n’appartient à aucun
autre Cj pour i 6= j puisque Card(A) = i 6= j. Ainsi, on obtient que
n
X
Card(C) = Card(Cp ).
p=0
 
n
Soit alors p ∈ {0, . . . , n}. Il y a parties A de E de cardinal p et pour chacune d’entre elles,
p
il y a 2Card(A) p
  = 2 choix possibles de B vérifiant B ⊂ A (comme on l’a vu). Par conséquent, Cp
n p
contient 2 éléments. Finalement, en utilisant la formule du binôme de Newton, on a
p
n  
X n p
Card(C) = 2 = 3n .
p
p=0

BCPST1-Lycée Chaptal Page 11 2021/2022

 2. Comme A ∩ B = ∅ ⇔ B ⊂ A, il y a autant de couples (A, B) de parties de E vérifiant A ∩ B = ∅
que de couples (A, B) vérifiant B ⊂ A. Le raisonnement fait ci-dessus peut être repris pour A et
il y a donc 3n couples (A, B) de parties de E vérifiant A ∩ B = ∅.
3. • Choisir une partition (A, B, C) de E à 3 éléments revient à choisir un couple (A, B) tel que
A ∩ B = ∅. En effet, on n’a alors plus le choix pour C : il faut prendre C = A ∪ B. La
réponse est donc une nouvelle fois 3n .
• Retrouvons ce résultat par un raisonnement plus direct. Choisir une répartition de E, c’est
regrouper les éléments de E en 3 paquets différents ordonnés que l’on numérote par exemple
a, b, c. Il s’agit donc de répartir n éléments distincts (les éléments de E) dans les 3 boîtes
a,b et c, chaque boîte pouvant contenir 0, un ou plusieurs éléments. On est donc dans un
cadre de répartition de n éléments distincts dans 3 boîtes distinctes avec répétition possible.
On retrouve bien 3n .
Remarque : On a considéré ici les partitions comme une liste de 3 parties et donc avec un ordre :
en clair la partition (∅, ∅, E) est différente de la partition (E, ∅, ∅). Si on avait choisi de voir une
partition comme la donnée de 3 parties {A, B, C} (c’est-à-dire sans tenir compte de l’ordre) 2 à
2 disjointes et recouvrant E, il y en a moins. Plus précisemment, on a comptabilisé 3! = 6 fois le
même partage lorsque l’ordre compte (nombre de façons de permuter ces 3 parties). C’est tout le
temps le cas sauf quand deux d’entre elles sont vides et l’autre vaut E, auquel cas on seulement
comptabilisé trois fois : (E, ∅, ∅), (∅, ∅, E) et (∅, E, ∅) alors que cela correspond au même partage
{∅, ∅, E}. Dans ce cas, il y aurait donc

3n − 3 3n−1 + 1
+1=
3! 2
façons de partager E en trois.

BCPST1-Lycée Chaptal Page 12 2021/2022