Sujet : Algèbre, Ensembles et applications, Dénombrement

[http://mp.cpgedupuydelome.fr] édité le 10 septembre 2013

Dénombrement

Exercice 1[ 01529 ][correction]
SoientEetFdeux ensembles finis de cardinaux respectifsnetp.
Combien y a-t-il d’injections deEdansF?

Exercice 2[ 01530 ][correction]
SoientE={1     n}etF={1     p}avecn6p∈N.
Combien y a-t-il d’applications strictement croissantes deEversF?

Exercice 3[ 01531 ][correction]
Combien existe-t-il de relation d’ordre total sur un ensembleEànéléments ?

Exercice 4[ 01532 ][correction]
On trace dans un planndroites en position générale (i.e. deux d’entre elles ne
sont jamais parallèles ni trois d’entre elles concourantes). Combien forme-t-on
ainsi de triangles ?

Enoncés

Exercice 5[ 01533 ][correction]
Soientp q∈Netn∈[0 p+q]. Proposer une démonstration par dénombrement
de l’égalité
n
X
np+q!=k=0kp! n−kq!

Exercice 6[ 01534 ][correction]
SoientEetFdeux ensembles finis non vides de cardinaux respectifsnetp.
On noteSnple nombre de surjections deEsurF.
a) CalculerSn1,SnnetSnppourp > n.
b) On supposep6net on considèreaun élément deE.
On observant qu’une surjection deEsurFréalise, ou ne réalise pas, une
surjection deE\ {a}surF, établirSpn=p(Spn−−11+Spn−1).
c) En déduire
p
Spn=kX=0(−1)p−kpk!kn

Exercice 7[ 01535 ][correction]
Pourn∈N?etp∈N, on noteΣpnle nombre denuplets(x1     xn)∈Nntels
quex1+∙ ∙ ∙+xn=p.
a) DéterminerΣ0nΣ1nΣ2nΣp1etΣp2.
b) Etablir
∀n∈N?,∀p∈N,Σpn+1= Σ0n+ Σ1n+∙ ∙ ∙+ Σpn
c) En déduire que
Σpn=n+p!
−1
p

Exercice 8[ 01536 ][correction]
SoitEun ensemble ànéléments.
a) SoitXune partie àpéléments deE.
Combien y a-t-il de partiesYdeEdisjointes deX?
b) Combien y a-t-il de couples(X Y)formés de parties disjointes deE?

Exercice 9[ 01537 ][correction]
SoitEun ensemble ànéléments. Combien y a-t-il de partiesXetYdeEtelles
queX⊂Y?

Exercice 10[ 01538 ][correction]
SoitAune partie d’un ensembleEànéléments. On posep=CardA.
a) Combien y a-t-il de partiesXdeEcontenantA?
b) Combien y a-t-il de partiesXdeEàm∈ {p     n}éléments contenantA?
c) Combien y a-t-il de couples(X Y)de parties deEtels queX∩Y=A?

Exercice 11[ 01539 ][correction]
SoitEun ensemble ànéléments. Calculer
XCard(X) etXCard(X∩Y)
X⊂E XY⊂E

Exercice 12[ 01540 ][correction]
Combien y a-t-il dep-cycles dans(Sn◦)?

1

Diffusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 10 septembre 2013

Corrections

Exercice 1 :[énoncé]
Sin > p, il n’y a pas d’injections possibles.
Sin= 0, il y a une injection : l’application vide.
Si0< n6palors on peut écrireE={x1     xn}avec lesxideux à deux
distincts.
Pour former une injection deEdansF:
On choisitf(x1)dansF:pchoix.
On choisitf(x2)dansF\ {f(x1)}:p−1choix.
...
On choisitf(xn)dansF\ {f(x1)     f(xn−1)}:p−n+ 1choix.
Au total, il y ap×(p−1)× ∙ ∙ ∙ ×(p−n+ 1) =(pp−!n)!choix.

Corrections

Exercice 2 :[énoncé]
Une applicationf:E→Fstrictement croissante est entièrement déterminée par
son image qui est une partie formée denéléments deF. Il y anp!parties àn
éléments dansFet donc autant d’applications strictement croissantes deEvers
F.

Exercice 3 :[énoncé]
Une relation d’ordre total surEpermet de définir une bijection de{1     n}vers
Eet inversement.
Par suite, il y a exactementn!relations d’ordre total possibles.

Exercice 4 :[énoncé]
Notonstnle nombre de triangles formés.
t0=t1=t2= 0ett3= 1.
Pour toutn>3,tn+1=tn+n(n2−1)car la nouvelle droite définit, en plus des
précédents,n(n2−1)nouveaux triangles (correspondants au choix de deux droites
parmi les précédentes).
Par suite
tn+1=Pnk(k2−1)=21Pnk2−21Pnk=n(n21+1)(2n+1)−n(n+4)1=n(n6(1)+n−1).
k=1k=1k=1

2

Exercice 5 :[énoncé]
SoitEun ensemble àp+qéléments séparé en deux parties disjointesE0etE00de
cardinauxpetq.
Il y a exactementp+q!parties ànéléments dansE.
n
Or pour former une partie ànélément deE, on peut pour chaquek∈[0 n]
commencer par choisirkéléments dansE0avant d’en choisirn−kdansE00. Il y a
p! nq−k!possibilités pour chaquek∈[0 n]puis au total
k
k=nP0kp! qn−k!possibilités d’où l’identité.

Exercice 6 :[énoncé]
a) SiFest un singleton, il n’y a qu’une application à valeurs dansFet celle-ci est
surjective.Sn1= 1.
Si CardE=CardF <+∞alors les surjections deEsurFsont aussi les
bijections. Par suiteSnn=n!.
Si CardE <CardF, il n’existe pas de surjections deEsurF. AinsiSpn= 0.
b) Une surjection deEsurFtelle que sa restriction àE\ {a}soit surjective peut
prendre n’importe quelle valeurs ena. Il y en apSpn−1.
Une surjection deEsurFtelle que sa restriction àE\ {a}ne soit pas surjective
doit prendre enala valeur manquante. Il y appossibilité pour choisir la valeur en
p−1
aetSnp−−11surjections deE\ {a}surF\ {f(a)}. Au total, il y en apSn−1.
Au final
Snp=p(Spn−−11+Snp−1)

c) Montrons la propriété par récurrence surn∈N?.
Pourn= 1.p= 1,S11= 1etk=P01(−1)1−kk1!k= 1.
Supposons la propriété établie au rangn−1>1.
Pourp= 1:S1n= 1etnkP=0(−1)1−knk!k= 1.
Pour16p6n:

Spn=p(Snp−−11+Spn−1) =pkp=X−01(−1)p−1−kkp−1!kn−1+pk=Xp0(−1)p−kpk!kn−1

Diffusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 10 septembre 2013

En combinant les deux sommes en exploitant la formule de Pascal
p
Spn=X(−1
k=0)p−kppk−−11!kn−1

puis en exploitant

on parvient à

Récurrence établie.

pkp−−11!=kpk!

Snp=k=Xp0(−1)p−kpk!kn

Corrections

Exercice 7 :[énoncé]
a)Σn0= 1: seul len-uplet nul est de somme égale à 0.
Σn1=n: lesn-uplets de somme égale à 1 sont formés d’un 1 et den−1zéros.
Σ2n=n+n(n2−1)=n(n+)12: lesn-uplets de somme égale à 2 sont ou bien formé de
1 deux et den−1zéros, ou bien de 2 uns et den−2zéros.
Σp1= 1: seul le 1-uplet(p)est de somme égale àp.
Σp2=p+ 1: les couples de somme égale àpsont(0 p)(1 p)    (p0).
b) Le nombre den+ 1uplets(x1  xn xn+1)∈Nntels quex1+∙ ∙ ∙+xn+1=p
avecxn+1=k∈[0 p]estΣpn−k.
Donc
Σpn+1= Σ0n+ Σ1n+∙ ∙ ∙+ Σnp
c) Par récurrence surn∈N?, montrons
∀n∈N?Σpn=n+pp−1!

Pourn= 1: ok
Supposons la propriété établie au rangn>1
∀p∈NΣpn+1= Σn0+∙ ∙ ∙+ Σnn=n−01!+1n!+∙ ∙ ∙+n+pp−1!=pn+p!

Récurrence établie.

Exercice 8 :[énoncé]
a) Autant que de parties deE\X:2n−p
b)pPn=0pn!2n−p= (1 + 2)n= 3n.

Exercice 9 :[énoncé]
Pourk∈ {0     n}, il y akn!partiesYà unkéléments dansE.
Pour une telle partieY, il y a2kpartiesXincluses dansY.
n
Au total, il y ak=Pn0k!2k= (1 + 2)n= 3ncouples(X Y)∈℘(E)2tels que
X⊂Y.

Exercice 10 :[énoncé]
a) Autant que de parties deE\A:2n−p
b) Autant que de parties deE\Aàm−péléments : !.
n−p
m−p
c) Une foisXàméléments contenantAdéterminé il y a2n−mchoix deY
possibles et donc
mPn=pnm−−pp!2n−n−pnk−p!2n−p−k= (1 + 2)n−p= 3n−p.
m=P
k=0

Exercice 11 :[énoncé]
Pourk&