37 Denombrements Corrige
37 Denombrements Corrige
37 Denombrements Corrige
Dénombrements : corrigé
Exercice no 1
1) Le nombre de mains est le nombre de parties à 5 éléments d’un ensemble à 32 éléments. Il y en a
32 32 × 31 × 30 × 29 × 28
= = 8 × 31 × 29 × 28 = 201 376.
5 5×4×3×2
2) Il y a quatre couleurs (carreau, cœur, pique trèfle) et quatre hauteurs (à l’as, au roi, à la dame et au valet). Au total,
il y a 4 × 4 = 16 quintes floches.
16 1
La probabilité d’avoir une quinte floche est donc = = 0, 000079 . . .
201 376 12 586
3) Chaque carré d’as peut être accompagné d’une carte choisie parmi les 28 qui ne sont pas des as. Il y a donc 28 carrés
d’as. Comme il y a 8 hauteurs possibles, il y a 28 × 8 = 224 mains contenant un carré.
224 1
La probabilité d’avoir un carré est donc = = 0, 0011 . . .
201 376 899
4) Il y a 4 couleurs (carreau, cœur, pique ou trèfle). Le nombre de mains contenant 5 carreaux est le nombre de parties à
5 éléments d’un ensemble à 8 éléments. Il y en a
8 8 8×7×6
= = = 8 × 7 = 56,
5 3 3×2
et donc au total, 4 × 56 = 224 mains contenant 5 cartes de couleurs identiques. On doit enlever à ces mains les quintes
floches au nombre de 16 (qui sont à ranger dans la catégorie des quintes floches et pas la catégorie des couleurs). Il reste
224 − 16 = 208 couleurs.
208 13
La probabilité d’avoir une couleur est donc = = 0, 00103 . . .
201 376 12 586
5)
Comptons le nombre de mains contenant un full aux as par les rois (brelan d’as et paire de roi). Il y a 4 brelans d’as et
4
= 6 paires de rois. Il y a donc 4 × 6 = 24 mains contenant un full aux as par les rois. Maintenant, il y a 8 hauteurs
2
possibles pour le full et pour chacune de ces hauteurs, il y a 7 hauteurs pour la paire soit au total 8 × 7 = 56 hauteurs
pour le full. Il y a donc 24 × 56 = 1344 mains contenant un full.
1 344 6
La probabilité d’avoir un full est donc = = 0, 0066 . . .
201 376 899
6) Comptons le nombre de suites à l’as. Il y a 4 as, 4 rois, 4 dames, 4 valets et 4 dix et donc 45 mains contenant la
séquence As, roi, dame, valet, dix. Une suite peut commencer à l’as, au roi, à la dame ou au valet et donc il y a 4 × 45 = 46
mains contenant 5 cartes qui se suivent. On doit retirer de ces mains celles qui fournissent une quinte floche et il reste
46 − 16 = 4080 mains contenant une suite.
10 752
La probabilité d’avoir un brelan est donc = 0, 053 . . .
201 376
8 4
8) Il y a = 28 hauteurs possibles des deux paires et pour chaque hauteur = 6 doubles paires possibles. Donc,
2 2
8 4 4
× × = 28 × 6 × 6 = 1 008 doubles paires possibles. On a ensuite 24 possibilités de compléter ces deux paires
2 2 2
par une cinquième carte. Il y a 1 008 × 24 = 24 192 mains contenant deux paires.
24 192
La probabilité d’avoir deux paires est donc = 0, 12 . . .
201 376
4
9) Il y a 8 × = 48 paires. On complète par une 3ème, 4ème et 5ème carte soit 28 × 24 × 20 possibilités. L’ordre dans
2
28 × 24 × 20
lequel on reçoit ces cartes n’a pas d’importance et il y a donc 48 × = 107 520.
3×2
Avec un jeu de trente-deux cartes, il y a 107 520 mains contenant une paire.
107 520
La probabilité d’avoir une paire est donc = 0, 53 . . .
201 376
Exercice no 2
Le nombre de mains est le nombre de parties à 5 éléments d’un ensemble à 32 éléments. Il y en a
32 32 × 31 × 30 × 29 × 28
= = 8 × 31 × 29 × 28 = 201 376.
5 5×4×3×2
1) On prend une carte parmi les 4 rois et 4 cartes parmi les 28 qui ne sont pas des rois. Au total,
4 28 28 × 27 × 26 × 25
× =4× = 4 × 7 × 9 × 13 × 25 = 81 900
1 4 4×3×2
mains contenant exactement un roi.
2) On prend 2 cartes parmi les 8 piques et 3 cartes parmi les 24 qui ne sont pas des piques. Au total,
8 24 8 × 7 24 × 23 × 22
× = × = 4 × 7 × 4 × 23 × 22 = 56 672
2 3 2 3×2
mains contenant exactement deux piques.
3) On prend 2 cartes parmi les 8 piques et 2 cartes parmi les 8 cœrus et 1 cartes parmi les 16 qui ne sont ni des piques,
ni des cœurs. Au total,
8 8 16
× × = 28 × 28 × 16 = 12 544
2 2 1
mains contenant exactement deux piques et deux cœurs.
24 24 × 23 × 22 × 21 × 20
4) Le nombre de mains contenant 0 carreau est = = 4 × 23 × 22 × 21 = 42 504 et le nombre
5 5×4×3×2
8 24 24 × 23 × 22 × 21
de mains contenant 1 carreau est × = 8× = 8 × 23 × 22 × 21 = 85 008. Le nombre de mains
1 4 4×3×2
Exercice no 5
Exercice n 6 o
pq pq − q (p − 1)q
Il y a choix possibles d’une première classe. Cette première classe étant choisie, il y a = choix
q q q
q pq (p − 1)q q
possibles de la deuxième classe... et choix possibles de la p-ème classe. Au total, il y a ...
q q q q
choix possibles d’une première classe, puis d’une deuxième ...puis d’une p-ème.
pq (p − 1)q q
Maintenant dans le nombre ... , on a compté plusieurs fois chaque partition, chacune ayant été
q q q
compté un nombre égal de fois.
On a compté chaque partition autant de fois qu’il y a de permutations des p classes à savoir p!. Le nombre cherché est
donc :
1 pq (p − 1)q q 1 (pq)! ((p − 1)q)! (2q)! q! (pq)!
... = ... = .
p! q q q p! q!((p − 1)q)! q!((p − 2)q)! q!q! q!0! p!(q!)p
Exercice no 7
∀n ∈ N∗ , an,0 = 1 (unique solution : 0 + 0 + ... + 0 = 0) et ∀k ∈ N, a1,k = 1 (unique solution : k = k).
Soient n > 1 et k > 0. an+1,k est le nombre de solutions en nombre entiers positifs xi de l’équation x1 +...+xn +xn+1 = k. Il
y a an,k solutions telles que xn+1 = 0 puis an,k−1 solutions telles que xn+1 = 1 ... puis an,0 solutions telles que xn+1 = k.
Donc, ∀n ∈ N∗ , ∀k ∈ N, an+1,k = an,k + an,k−1 + ... + an,0 (et on rappelle an,0 = a1,k = 1).
k
X k
X k
X
n+i−1 n+i n+i−1 n+k n+k
an+1,k = an,i = =1+ − =1+ −1= ,
i i+1 i k+1 k+1
i=0 i=0 i=1
Ensuite,
n−1
Y n−1
X n−1
X
1 k 1 k 1 k
pn > ⇔ (1 − )6 ⇔ ln 1 − 6 ln ⇔ − ln 1 − > ln 2.
2 365 2 365 2 365
k=1 k=1 k=1
Ainsi,
√
1 n(n − 1) 2 1 + 1 + 2920 ln 2
pn > ⇐ > ln 2 ⇔ n − n − 730 ln 2 > 0 ⇔ n > = 22, 9 . . . ⇔ n > 23.
2 730 2
Finalement, dans un groupe d’au moins 23 personnes, il y a plus d’une chance sur deux que deux personnes au moins
aient la même date d’anniversaire.
Exercice no 10 (C’est long à lire et inutile pour Sup et Spé)
1) Notre calendrier est 400 ans périodique (et presque 4 × 7 = 28 ans périodique). En effet,
a) la répartition des années bissextiles est 400 ans périodique (1600 et 2000 sont bissextiles mais 1700, 1800 et 1900 ne le
sont pas (entre autre pour regagner 3 jours tous les 400 ans et coller le plus possible au rythme du soleil))
b) il y a un nombre entier de semaines dans une période de 400 ans. En effet, sur 400 ans, le quart des années, soit 100
ans, moins 3 années sont bissextiles et donc sur toute période de 400 ans il y a 97 années bissextiles et 303 années non
bissextiles.
1900 , 1901 → 1928, 1929 → 1956, 1957 → 1984, 1985 → 2012, 2013 → 2040, 2041 → 2068, 2069 → 2096,
2097 → 2100 , 2101 → 2128, 2129 → 2156, 2157 → 2184, 2185 → 2200 , 2201 → 2228, 2229 → 2256,
2257 → 2284, 2285 → 2299 .
4) On montre ensuite que sur toute période de 28 ans sans siècle non bissextile, le premier de l’an tombe un même nombre
de fois chaque jour de la semaine (lundi, mardi,..). Quand on passe d’une année non bissextile à l’année suivante, comme
une telle année contient un nombre entier de semaines plus un jour, le 1er de l’an tombe un jour plus tard l’année qui suit
et deux jours plus tard si l’année est bissextile. Par exemple,
1er janvier 1998 : jeudi, 1er janvier 1999 : vendredi, 1er janvier 2000 : samedi, 1er janvier 2001 : Lundi, 1er janvier
2002 : Mardi, 1er janvier 2003 : Mercredi, 1er janvier 2004 : Jeudi, 1er janvier 2005 : samedi...
Notons A,B,C,D,E,F,G les jours de la semaine. Sur une période de 28 ans sans siècle non bissextile finissant par exemple
une année bissextile, on trouve la séquence suivante :
ABCD FGAB DEFG BCDE GABC EFGA CDEF (puis çà redémarre ABCD...) soit 4A, 4B, 4C, 4D, 4E, 4F, et 4G.
5) Il reste à étudier les périodes à exception (encadrées dans le 3)).
Détermination du 1er janvier 1900. Le 1er janvier 2015 était un jeudi . Il en est donc de même du 1er janvier 2015-28 =
1987 et des premiers janvier 1959, 1931 et 1903 puis on remonte : 1903 Jeudi 1902 Mercredi 1901 Mardi 1900 Lundi (1900
n’est pas bissextile). Le premier de l’an 1900 était un Lundi.
Les premiers de l’an 2000, 2028 , 2056 et 2084 sont des samedis, 2088 un jeudi, 2092 un mardi, 2096 un dimanche et donc
2097 mardi 2098 mercredi 2099 jeudi 2100 vendredi.
2101 est un samedi de même que 2129, 2157, 2185 ce qui donne de 2185 à 2200 inclus la séquence :
S D L Ma J V S D Ma Me J V D L Ma Me
2201 est un jeudi de même que 2285 ce qui donne de 2285 à 2299 inclus la séquence : J V S D Ma Me J V D L Ma Me V
SD
Le décompte des Lundis , mardis ... des périodes à exceptions est : 6D 4L 6Ma 5Me 5J 6V 4S. Dans toute période de 400
ans, le 1er de l’an tombe 2 fois de plus le dimanche que le samedi et donc plus souvent le dimanche que le samedi.
Exercice no 11
On pose « H = vers le haut » et « D = vers la droite ». Un exemple de chemin de (0, 0) à (p, q) est le mot DD...DHH...H
où D est écrit p
fois et H est écrit q fois. Le nombre de chemins cherché est le nombre d’anagrammes du mot précédent.
p+q
Il y en a (nombre de choix de l’emplacement du D).
q
Exercice no 12
On note respectivement x, y et z le nombre de pièces de 10, 20 et 50 centimes. Il s’agit de résoudre dans N3 l’équation
10x + 20y + 50z = 10000 ou encore x + 2y + 5z = 1000.
k
Soit k ∈ N. x+2y = k ⇔ x = k−2y et donc l’ensemble des solutions dans N2 de cette équation est (k − 2y, y), 0 6 y 6
2
k k
ou encore (k − 2y, y), 0 6 y 6 E . Le nombre de solutions de cette équation est E + 1.
2 2
1000 − 5z
Pour 0 6 z 6 200 donné, le nombre de solutions de l’équation x + 2y = 1000 − 5z est E + 1. Le nombre de
2
solutions en nombres entiers de l’équation x + 2y + 5z = 1000 est donc
Enfin
200
X X100 X100 X100
−5z −5(2k − 1) −5(2k) 5
E = E +E = E −5k + − 5k = (−10k + 2)
2 2 2 2
z=0 k=1 k=1 k=1
100 × 101
= 200 − 10 .
2
Le nombre de solutions cherché est donc 100701 − 50300 = 50401. Il y a 50401 façons de payer 100 euros avec des pièces
de 10, 20 et 50 centimes.
Exercice no 13
1)
n
X X
card(Sn ) − card(A1 ∪ A2 ... ∪ An ) = card(Sn ) − card(Ai ) + card(Ai ∩ Aj )
i=1 i<j
X
− ... + (−1)k card(Ai1 ∩ ...Aik ) + ...
i1 <i2 <...<ik
Ai est l’ensemble des permutations qui fixent i. Il y en a (n − 1)! (nombre de permutations de {1, ..., n} \ {i}). Ai ∩ Aj est
l’ensemble des permutations qui fixent i et j. Il y en a (n − 2)!. Plus généralement, card(Ai1 ∩ ... ∩ Aik ) = (n − k)!.
n n
D’autre part, il y a n = entiers i dans {1, . . . , n} puis couples (i, j) tels que i < j et plus généralement, il y a
1 2
n
k-uplets (i1 , ..., ik ) tels que i1 < i2 < ... < ik . Le nombre de dérangements est
k
Xn X n
n! (−1)k
n! + (−1)k × (n − k)! = n! .
k!(n − k)! k!
k=1 k=0
1
Montrons que cette suite tend très rapidement vers = 0, 36... quand n tend vers l’infini.
e
Xn Z1
−x −1 (−1)k n+1 (1 − t)n −t
La formule de Taylor-Laplace appliquée à la fonction x 7→ e fournit ∀n ∈ N, e = +(−1) e dt.
k! 0 n!
k=0
1
Ceci montre que pn tend très rapidement vers .
e
Exercice no 14
Soit n un naturel non nul. Dire que f est une surjection de J1, n + 1K sur J1, nK équivaut à dire que deux des entiers de
{1, ..., n + 1} ont même
image k par f et que les autres ont des images deux à deux distinctes etdistinctes
de k. On choisit
n+1 n+1
ces deux entiers : choix et leur image commune : n images possibles ce qui fournit n choix d’une paire
2 2
de {1, ..., n + 1} et de leur image commune. Puis il y a (n − 1)! choix des images des n − 1 éléments restants. Au total, il y
n(n + 1) n × (n + 1)!
a (n − 1)! × n = surjections de J1, n + 1K sur J1, nK.
2 2
Exercice no 15
Soit n > 5. De chaque sommet part n − 1 droites (vers les n − 1 autres sommets) dont 2 sont des cotés et n − 3 des
n(n − 3)
diagonales. Comme chaque diagonale passe par 2 sommets , il y a diagonales.
2
n(n − 3)/2
Ces diagonales se recoupent en points distincts ou confondus. Dans ce décompte, chaque sommet a été
2
n−3
compté autant de fois que l’on a choisi une paire de deux diagonales passant par ce sommet à savoir . Maintenant,
2
il y a n sommets.
Réponse :
n(n − 3)/2 n−3 1 n(n − 3) n(n − 3) (n − 3)(n − 4) n(n − 3)
−n = −1 −n = (n(n − 3) − 2 − 4(n − 4))
2 2 2 2 2 2 8
n(n − 3) 2
= (n − 7n + 14)
8
n(n − 3)(n2 − 7n + 14)
Les diagonales se recoupent en points distincts ou confondus et distincts des sommets ou encore
8
n(n − 3)(n2 − 7n + 14)
en points au maximum.
8
Exercice no 16
1) On a bien sûr P(1) = 2. Soit n > 1. On trace n droites vérifiant les conditions de l’énoncé. Elles partagent le plan
en P(n) régions. On trace ensuite Dn+1 , une (n + 1)-ème droite. Par hypothèse, elle coupe chacune des n premières
droites en n points deux à deux distincts. Ces n points définissent (n + 1) intervalles sur la droite Dn+1 . Chacun de ces
(n + 1) intervalles partage une des P(n) régions déjà existantes en deux régions et rajoute donc une nouvelle région. Ainsi,
P(n + 1) = P(n) + (n + 1).
Soit n > 2.
n−1
X n−1
X n
X n(n + 1)
P(n) = P(1) + (P(k + 1) − P(k)) = 2 + (k + 1) = 1 + k=1+
2
k=1 k=1 k=1
n2 + n + 2
=
2
ce qui reste vrai pour n = 1.
n(n + 1) n2 + n + 2
∀n > 1, P(n) = 1 + = .
2 2
2) On a bien sûr Q(1) = 2. Soit n > 1. On trace n plans vérifiant les conditions de l’énoncé. Ils partagent l’espace en
Q(n) régions. On trace ensuite Pn+1 , un (n + 1)-ème plan. Par hypothèse, il recoupe chacun des n premiers plans en n
n(n + 1)
droites vérifiant les conditions du 1). Ces n droites délimitent P(n) = 1 + régions sur le plan Pn+1 . Chacune
2
n n2 + 5
n3 + 5n + 6
∀n > 1, Q(n) = =1+ .
6 6
Exercice no 17
Soient n et k des entiers naturels tels que 2 6 k 6 n − 1.
Soit E un ensemble à n éléments et a un élément fixé de E.
k
Il y a Pn partitions de E en k classes. Parmi ces partitions, il y a celles dans lesquelles a est dans un singleton. Elles
k−1
s’identifient aux partitions en k − 1 classes de E \ {a} et sont au nombre de Pn−1 . Il y a ensuite les partitions dans lesquelles
a est élément d’une partie de cardinal au moins 2. Une telle partition est obtenue en partitionnant E \ {a} en k classes puis
k k k−1 k
en adjoignant à l’une de ces k classes au choix l’élément a. Il y a k × Pn−1 telles partitions. Au total, Pn = Pn−1 + kPn−1 .
k
Valeurs de Pn pour 1 6 k, n 6 5.
k 1 2 3 4 5
n
1 1 0 0 0 0
2 1 1 0 0 0
3 1 3 1 0 0
4 1 7 6 1 0
5 1 15 25 10 1
k
Exprimons maintenant en fonction des Pn le nombre de surjections d’un ensemble à n éléments sur un ensemble à p
éléments. Soient En et Ep désignent des ensembles à n et p éléments respectivement.
Si p > n, il n’y a pas de surjections de En dans Ep .
On suppose dorénavant p 6 n. La donnée d’une surjection f de En sur Ep équivaut à la donnée d’une partition de
l’ensemble En en p classes (chaque élément d’une même classe ayant même image par f) puis d’une bijection de l’ensemble
des parties de la partition vers Ep .
p
Au total, il y a donc p!Pn surjections d’un ensemble à n éléments dans un ensemble à p éléments pour 1 6 p 6 n.
Exercice no 18
Soit Y0 une partie fixée de E. Notons k le cardinal de Y0 . k est un élément de J0, nK. Le nombre de couples (X, Y0 ) ∈ (P(E))2
tels que X ⊂ Y0 est encore le nombre de parties X de Y0 à savoir 2k .
n
Soit k ∈ J0, nK fixé. Il y a parties Y de E de cardinal k et pour chaque partie Y de E de cardinal k, il y a 2k couples
k
2 n 2
(X, Y) ∈ (P(E)) tels que X ⊂ Y. Au total, il y a × 2k couples (X, Y) ∈ (P(E)) tels que X ⊂ Y et card(Y) = k.
k
2
Le nombre de couples (X, Y) ∈ (P(E)) tels que X ⊂ Y est donc
n
X n k
2 = (1 + 2)n = 3n .
k
k=0
X X
card(X ∩ Y) + card X ∩ Y
2S1 =
(X,Y)∈(P(E))2 (X,Y)∈(P(E))2
X X
card(X ∩ Y) + card X ∩ Y card(X),
= =
(X,Y)∈(P(E))2 (X,Y)∈(P(E))2
puis
X X X
card(X) + card X = card(E)
2 × 2S1 =
(X,Y)∈(P(E))2 (X,Y)∈(P(E))2 (X,Y)∈(P(E))2
2
= card(E) × card P(E)2 = n × (2n ) ,
n22n
et donc S1 = = n22n−2 . D’autre part,
4
X X X
card(X ∪ Y) = card X ∪ Y = card X ∩ Y
S2 =
(X,Y)∈(P(E))2 (X,Y)∈(P(E))2 (X,Y)∈(P(E))2
X
= (n − card (X ∩ Y)) = n22n − S2 = n22n − n22n−2 = 3n22n−2 .
(X,Y)∈(P(E))2
S1 = n22n−2 et S2 = 3n22n−2 .
Exercice no 20
1) Une loi de composition interne sur E est une application de E × E dans E (et réciproquement). Le nombre de lois de
composition interne sur E est donc
n(n(n+1)/2) .
3) Il y a n choix possibles de l’élément neutre. Pour chaque choix i tel que ai soit élément neutre, les valeurs des ai ∗ aj ,
1 6 j 6 n et des aj ∗ ai , 1 6 j 6 n, sont imposées. Sinon, le nombre de choix pour les aj ∗ ak , j 6= i, k 6= i, est encore le
2
nombre d’applications de ({a1 , . . . , an } \ {ai }) vers {a1 , . . . , an }. Le nombre de lois de composition interne sur E possédant
un élément neutre est donc
n × n((n−1) ) = nn −2n+2 .
2 2