c Christophe Bertault - MPSI

TD - Ensembles finis et dnombrement

! ! ! ! ! ! ! !
Exercice 1 n nk n p n nk n p
On tire simultanment 6 cartes dun jeu de tarot 21 atouts, la carte quon appelle En dduire que = , puis que = .
k pk p k k np p k
l excuse , et 14 cartes par couleur, sachant quil y a 4 couleurs, comme toujours. On
ne cherchera pas valuer numriquement les rsultats obtenus dans cet exercice, sauf si 2) On note S lapplication de RN dans lui-mme qui, toute suite
! relle (xn )nN ,
on aime se compliquer la vie. Combien de tirages diffrents peut-on obtenir contenant : n
X n
1) deux atouts et quatre trfles ? associe la suite (yn )nN dfinie par : n N, yn = xk et T lap-
k=0
k
2) six carreaux, ou bien trois carreaux, deux piques et lexcuse ?
3) exactement un atout et au moins trois as ? plication de RN dans lui-mme qui, toute suite relle
! (xn )nN , associe la suite
n
4) au plus un cur et au moins quatre atouts ?
X n
(yn )nN dfinie par : n N, yn = (1)nk xk .
k=0
k
Exercice 2 Montrer que S et T sont deux bijections de RN dans RN inverses lune de lautre.
On appellera mot toute suite de lettres, quelle ait un sens ou non. On rappelle que
la lettre y est une voyelle. Exercice 7
1) Combien de mots de 5 lettres peut-on former avec les 26 lettres de lalphabet, dans 1) On considre un ensemble fini E dont les lments sont de deux types nots 1 et
lesquels toute consonne est suivie dune voyelle et toute voyelle dune consonne ? 2. Prcisment, E contient n1 lments de type 1 et n2 lments de type 2. Soit
2) Dterminer le cardinal de lensemble E des mots de 5 lettres forms partir des k J0, n1 + n2 K. Exprimer de deux faons le nombre de parties k lments de E
26 lettres de lalphabet et tels que : que lon peut former. En dduire une jolie une formule.
n
!2
(i) la lettre q est forcment suivie de la lettre u , X n
(ii) toute consonne est suivie dune voyelle, 2) Simplifier pour tout n N.
k=0
k
(iii) toute voyelle est suivie dune consonne, une exception prs : les u
qui sont conscutifs dun q sont suivis dune voyelle autre que u ,
(iv) les deux dernires lettres ne peuvent pas tre qu . Exercice 8
Soient n, p N. Pour tout k J1, n+1K, dterminer le nombre de parties de J1, n+p +1K
n
! n
!
Exercice 3
X p+k X p+k
de cardinal (p + 1) et de maximum p + k. Simplifier ainsi et .
Soient A1 , A2 , . . . , An des ensembles. Prouver la formule du crible (ou formule de Poin- k=0
p k=0
k
n
! n
[ X X
(1)k+1


car) : card Ai = card Ai1 Ai2 . . . Aik . Exercice 9
i=1 k=1 16i1 <i2 <...<ik 6n
1) Soient G un groupe fini et x G.
Quel formule retrouve-t-on dans le cas o les Ai , i J1, nK, sont deux deux disjoints ?
a) Montrer que xn = 1G pour un certain n N .
b)nOn appelle ordre de
o x et on note o(x) le plus petit lment de lensemble
Exercice 4 n N /xn = 1G . Justifier lexistence de o(x).
Soient n, p N tels que p 6 n. Montrer, par un raisonnement combinatoire, que : n o
c) Montrer que lensemble 1G , x, x2 , . . . , xo(x)1 est un sous-groupe de G. On
! ! ! ! !

n n n n n+1 note x ce sous-groupe et on lappelle le sous-groupe de G engendr par x.
= et + = .
p np p1 p p 2) Soit E un magma associatif fini. Montrer que E possde un idempotent, i.e. un
lment x E pour lequel x2 = x.

Exercice 5 Exercice 10
Soient n, p N . Combien existe-t-il dapplications strictement croissantes de J1, nK dans
Soit E un ensemble. On associe, toute partie A de E, lapplication lindicatrice de A
J1, pK ? 
n o 1 si x A
A : E 0, 1 dfinie par : x E, A (x) = .
0 si x /A
Exercice 6 ( n oE
1) Soient E un ensemble fini de cardinal n et p, k N tels que 0 6 k 6 p 6 n. P(E) 0, 1
Montrer que lapplication est une bijection. Retrouver ainsi,
Calculer de deux faons le nombre de couples (A, B) P(E)2 tels que A B, A 7 A
card A = k et card B = p. dans le cas o E est fini, un rsultat du cours.

1
c Christophe Bertault - MPSI
TD - Ensembles finis et dnombrement

Exercice 11
1) Soit n N . On range (n + 1) chaussettes dans n tiroirs. Montrer quau moins
un tiroir contient deux chaussettes. Ce rsultat simple et essentiel est connu sous
le nom de principe des tiroirs.
2) a) Soient x R et n N . Pour tout k J0, nK, on pose k = kx kx, lment
de [0, 1[. Appliquer le principe des tiroirs aux rels k , k dcrivant J0, nK, pour
montrer le thorme dapproximation de Dirichlet suivant :
 
 p 1
(p, q) Z N / q 6 n et x  < .
q nq

b) En dduire
 que pour tout x R, lensemble des couples (p, q) Z N pour
 p  1
lesquels x  < 2 est infini.
q q
c) Dmontrer le thorme de Bzout partir de la question a) : pour tous a, b Z
premiers entre eux, il existe u, v Z tels que au + bv = 1.
d) On admet
 lirrationnalit
 de , de sorte que sin n 6= 0 pour tout n N . La
1
suite possde-t-elle une limite, et si oui laquelle ?
n sin n nN

Exercice 12 1 1
Soient p et q deux irrationnels strictement positifs tels que + = 1. On souhaite
n p oq n o
prouver le thorme de Beatty selon lequel les ensembles np et nq
nN nN

forment une partition
n o de N , i.e.nsonto disjoints de runion N tout entier.
On pose P = np et Q = nq .
nN nN
1) Montrer que les ensembles
 P et Q sontdisjoints.
2) En dduire que card (P Q) [1, N ] = N 1 pour tout N N .
3) Conclure.

Exercice 13 n o
Soit n N . On pose G = Sn / k J1, n + 1K, (n k + 1) = n (k) + 1 .
1) Montrer que G est un sous-groupe de Sn .
2) Calculer le cardinal de G.

Exercice 14
On se donne n entiers relatifs quelconques. Montrer que lon peut toujours former par
somme, en choisissant certains dentre eux, un multiple de n.