Exercice N°113: Entiers naturels, dénombrement
8 pages
Français

Exercice N°113: Entiers naturels, dénombrement

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

⋆⋆⋆⋆⋆⋆≃⋆ ´ MPSI Lycee Rabelais Semaine du 12 aoutˆ 2011 Entiers naturels, d´enombrements Propri´et´es de N, r´ecurrence 4. Combien existe-t-il de couples (A,B) tels que A∩B =∅ et A∪B =E? Exercice 1 : D´emontrez que pour tout entier n≥ 1, n(2n+1)(7n+1) est divisible Exercice 8 : Soit (n,p) ∈ N ×N . On note S le nombre de surjections de F n,p n par 6. sur F . p 1. D´eterminez S lorsque n,p Exercice 2 : Montrez que pour tout entier n≥ 2, – n≤p 1 1 3n – lorsque p = 1 et n∈N 1+ +···+ > . 2 2 2 n 2n+1 2. Pour k∈F , on note A ={f :F →F |f est surjective, et f(1) =k}. p k n p D´emontrez que Card (A ) =S +S et d´eduisez-en que k n−1,p n−1,p−1 n+1 Exercice 3 : Montrez que ∀n∈N ,1!3! ···(2n+1)!≥ (n+1)! . S =p [S +S ] n,p n−1,p n−1,p−1 Exercice 4 : D´emontrez que pour tout entier n≥ 1 la propri´et´e suivante est vraie : Pour tout n-uplet (a ,...,a ) de r´eels sup´erieurs ou ´egaux `a 1 , 3. D´eduisez-en finalement la formule : 1 n p n−1 X 2 (a ×···×a +1)≥ (a +1)×···×(a +1). p 1 n 1 n p−k n S = (−1) k n,p k k=0 Exercice 5 : Le but de l’exercice est de d´eterminer l’ensembleE des applications f :N→N v´erifiant : Exercice 9 : Soit (n,p)∈N ×N pour tout entier n∈N, f◦f(n) ⇐⇒ 25 > 24. Donc n+1 4 4 4 5 (n+2) k=1 la propri´et´e est v´erifi´ee pour n = 2. 2n+3 Y • H´er´edit´e soit n≥ 2 tel que (n+2) n+2 k=n+3 1 1 3n ≥ (n+2)! × 1+ +···+ > . n+1 2 2 (n+2) 2 n 2n+1 n+2 ≥ (n+2)! On a alors 1 1 1 3n 1 1+ +···+ + > + 2 2 2 2 2 n (n+1) 2n+1 (n+1) n+1 • Ccl.

Sujets

Informations

Publié par
Nombre de lectures 251
Langue Français

MPSILyc´eeRabelias

Pr´et´opri,N´rseedercncerue

Entiersnaturels,de´nombrements

Exercice 1 :neitremo´eDeuqzertntuotruopn≥1,n(2n+ 1)(7n est divisible+ 1)
par 6.

Exercice 2 :Montrez que pour tout entiern≥2,

1+212+  +n12>2n3+n1
Exercice 3 :Montrez que∀n∈N⋆1! 3!  (2n+ 1)!≥(n+ 1)!n+1

Exercice 4 :uotruoettneirD´emontrezquepn≥tseetnav:eiarvriopprlauiest´´e1
Pour tout n-uplet(a1     an)x`aua1osruge´u´puseireeesled´r,

2n−1(a1×    ×an+ 1)≥(a1+ 1)×    ×(an+ 1)

Exercice 5 :te´eedtdescecierxe’ledtubeLbmelneesre’lmrniEdes applications
f:N→Nv´ent:rifia

pour tout entiern∈N f◦f(n)< f(n+ 1)

1. Soitf∈Etnome´D.rezquepourtoutenitrep∈N, lademi-droiteDp={k∈
N|k≥p}est stable parfuqeider`--ae’tsc,f(Dp)⊂ Dp.
2.De´duisez-enquefest strictement croissante et que pour tout entiern∈N,
f(n)< n+ 1.
3. Concluez.

Exercice 6 :
1D´montrezenutilisantunere´currencefortequetoutentiern∈N⋆e´rc’stied
. e
mani`ereuniquesouslaformen= 2p(2qo`u(,)1+p q)∈N2.
2.End´eduirequeN≃N2.
3.Conside´rezlaprojectionp:N2→N ? ! ? Injective. Est-elle surjective

Dtnemone´erbm

Exercice 7 :SoientEun ensemble de cardinaln,A B∈P(E) deux parties deE.
1.Decombiendefa¸consdiffe´rentespeut-onchoisirlecouple(A B) ?
2. Combien existe-t-il de couples (A B) tels queA∩B=∅?
3. Combien existe-t-il de couples (A B) tels queA∪B=E?

1

Semainedu12aoˆut2011

4. Combien existe-t-il de couples (A B) tels queA∩B=∅etA∪B=E?

Exercice 8 :Soit (n p)∈N⋆×N⋆. On noteSnple nombre de surjections deFn
surFp.
1.D´eterminezSnplorsque
–n≤p
– lorsquep= 1 etn∈N⋆
2. Pourk∈Fp, on noteAk={f:Fn→Fp|fest surjective, etf(1) =k}.
De´montrezqueCard(Ak) =Sn−1p+Sn−1p−1enquete´ddeiues-z

Snp=p[Sn−1p+Sn−1p−1]

3.De´duisez-enfinalementlaformule:
p
p=X(−k
Skn=0−1)ppkkn

Exercice 9 :Soit (n p)∈N⋆×N
1. Quel est le nombre de suites depentiers compris entre 1 etn?
2. Quel est le nombre de suites strictement croissantes depentiers compris entre
1 etn?
3. Quel est le nombre de suites croissantes depentiers compris entre 1 etn?

Exercice 10 :Soit (n p)∈N2nc.Osionoenrtdi`u’a´eeql

x1+x2+  +xn=p

De´terminezlenombredesolutionsdecettee´quation,
1. dans{0; 1}n
,
2. dans (N⋆)n
Indication :drelssloendza’obd´eterminioatedsnoituuqe´ni’lx1+x2+  +
xn≤protcsaisedntn-’eiusetsettcirnemeuesochaqonunlutianssetna`coai
tiers entre 1 etp.
3. dansNn.

icffieocseibudstneeomnˆPropri´et´esd
Exercice 11 :Soit (n p)∈N2E.atsez`blisa
de´nombrement,lesformulessuivantes:
1.pn=n−pn
2.np+1+1=np+pn+ 1
3.nkX=0nk= 2n.

l’aide

d’un

raisonnement

de

Exercice 12 : Formule de Van der Monde
Soientn n1 n2nemorbmene,tneonisrad´dentme’lA.slernu’dediasentdenatuiers
e´tablissezlaformulesuivante:
X
n1n+n2=nk=0kn1nn−2k

Exercice 13 :Soientp k ntrois entiers naturels tels que 0≤p≤k≤n´Dme.tronez
que
nkp=npnn−−pk
k
End´eduire
kX nn−pnnk
X

S1=0p−k; etS2=k=p(−1)n−kk p 
n
p=

Calcul de sommes
Exercice 14 :SoitEun ensemble fini de cardinaln∈N⋆. Notons
•S1=XCardX
X∈P(E)
•S2=XCard(X∩Y)
(XY)∈P(E)2
•S3=XCard(X∪Y)
(XY)∈P(E)2
1. Montrez queS1=n2n−1.
2. Montrez queS2=n22n−2.
3. Etablissez la relationS2+S3= 2n+1S1´D.z-seuiedequenS3= 3n22n−2.
Exercice 15 :enortzeuq´DmeX Xi= 2n−2n(n+ 1)
A⊂Fni∈A

2

Analyse combinatoire
Exercice 16 :Le Poker se joue avec un jeu de 32 cartes, on distribue a chaque
`
joueur unemainde cinq cartes.
1.D´enombrezlenombredemainspossibles.
2.De´nombrezlenombredemainsquicontiennent:
(a)uncarr´ed’as(4as).
(b)uncarre´(4cartesdemeˆmehauteur).
(c)unfull(3cartesdemˆemehauteuret2autrescartesdemeˆmehauteur).
(d)unbrelan(3cartesdemeˆmehauteursansfullnicarr´e)
(e)unequinteflush(5cartesdehauteurconse´cutivesetdemeˆmecouleur).
(f)unecouleur(5cartesdelameˆmecouleursansquinteflush).
(g) exactement deux rois et trois coeurs.

Exercice 17 :eLhecsejoujeud’´echcqiiureserunue´t8seloco8ldeneigsennseL.
tourspeuventprendretoutepi`ecesitu´eedansleurligneouleurcolonne.
1.Decombiendefa¸conspeut-onplacer8toursidentiques,desortequ’aucune
d’entreellesnesoitmenace´eparlesautres.
2.Decombiendefac¸onspeut-onplacerktours identiques,k∈ {1    8}de
sortequ’aucuned’entreellesnesoitmenac´eeparlesautres?

Correction des exercices

Exercice 1 .—onfavaeuirr´neercnceru.e..
•isattialionIineuorsqLn= 1, on a 1×3×8 = 4×6 est divisible par 6.
•´edit´eH´ersoitn≥0 tel queun=n(2n+ 1)(7n est divisible par 6. Il+ 1)
existe doncN∈Ntel queun= 6N. Montrons queun+1est divisible par 6 :

un+1= (n+ 1)(2n+ 3)(7n+ 8) = [n+ 1][(2n+ 1) + 2][(7n+ 1) + 7]
=n(2n+ 1)(7n+ 1) + 42n2+ 60n+ 24
= 6×[N+ 7n2+ 10n+ 4]


•clonCniousruer´rcenomacn,e´equontrrtouepountteriearpn∈N,
n(2n+ 1)(7n est divisible par 6.+ 1)N

Exercice 2 .—rpueevesaLceenrrcu´errpara:
•noitasilaitinIlorsquen= 2, on a 1 +41=45Or45>56⇐⇒
lapropri´et´tv´erifi´eepourn= 2.
e es
•´ited´re´Hitn≥2 tel que
eso
1+212+  +n123n
>2n+ 1

25>24. Donc

On a alors
1 12+  +n12 3 1+ (n1
+2n+ 1)2>2n+1(+n+ 1)2
3n3+ 6n2+ 5n+ 1
>(2n+ 1)2(n+ 1)2
Onve´rifiealorsque3(n23n1+6+n)22+(n5+n+1)21≥32nn,+3+.3nEffete

3n3+ 6n2+ 5n 3+ 1n+ 3

(2n+ 1)2(n+ 1)22n+ 3

6n4+ 21n3+ 28n2+ 17n+ 3
=
(2n+ 1)(2n+ 3)(n+ 1)2
6n4+ 21n3+ 27n2+ 15n+ 3

(2n+ 1)(2n+ 3)(n+ 1)2
n(n+ 2)
=
(2n+ 1)(2n+ 3)(n+ 1)2
≥0

Partransitivit´edelarelationd’ordre,ils’ensuitque

Conclusion
1

1 1 1 + (n+1)12>23nn3++3
+22+  +n2

parr´ntr´equetoutentiern
ecurrence, on a mo pour
1 3n

2,

3

Exercice 3 .—Pra´rceruercn.e

•Init.pourn= 1, on a 1!3! = 64 =≥22.

He´r.Soitn∈N⋆tel que 1! 3!  (2n+ 1)!≥(n+ 1)!n+1. Alors

1! 3!  (2n+ 1)! (2n+ 3)!≥(n+ 1)!n+1×(2n+ 3)!
≥(nn+2)!+2n+1(2n+ 3)!
×
2n+3
n+2Yk
n+k=n+3
≥(n+ 2)!1×k=Y1k×(n+ 2)n+1
2n+3
Y(n+ 2)
k=n+3
≥(n+ 2)!n+2×(n+ 2)n+1
≥(n+ 2)!n+2

•Ccl.Pruce´rranomae´rtcnerno,e∀n∈N⋆1! 3!  (2n+ 1)!≥(n+ 1)!n+1
N

Exercice 4 .—srqe´olOncfiire´vrapecnemmoeti´prroepttceern= 2. Il s’agit de
montrer que pour tout couple (a b)∈R2erieursou´egauxa`,1noaredlee´puss
´

2(ab+ 1)≥(a+ 1)(b+ 1)

.Raisonnonspar´equivalences,ona:

2(ab+ 1)≥(a+ 1)(b+ 1)⇐⇒ab−a−b+ 1≥0⇐⇒(a−1)(b−1)≥0

Commeaetbte.satisfaieetsibnee´agil´tsoinre`enieredttce1a`srueire´pustn

Apr´esentmontronslapropri´ete´parre´currence.

•Hr´´e.edSoitn≥un entier tel que pour tout1 nles´r´erbseenomletd-up
(a1     an)∈Rna`,1no:axuage´uosrueie´psuusto,

2n−1(a1×    ×an+ 1)≥(a1+ 1)×    ×(an+ 1)

Soit alors (b0 b1     bn)∈Rn+1unnr´eeetdeoussls,tu1lp+ueire´puuosr
e´gaux`a1.AlorsenposantB0=b0≥1 etB1=b1 ×  bn≥1, et en
appliquantlaremarquepre´liminaire,ilvient:

2n(b0×b1   ×bn+ 1) = 2n−1(1 +B0)(1 +B1)
= (1 +b0)×2n−1(b1   ×bn+ 1)

Onconclutalors`al’aidedel’hypothe`seder´ecurrenceque

2n(b0×b1   ×bn+ 1)≥(1 +b0)×(1 +b1)×    ×(1 +bn)

•Ccl.Pra´rceruernce,onamontr´equtrtouepoun-uplet (a1     anree´d)sel
sup´erieursoue´gauxa`1,2n−1(a1×    ×an+ 1)≥(a1+ 1)×    ×(an+ 1)N

Exercice 5 .—Soitf∈E.
1.Montronsparre´currencesurp∈N, quef(Dp)⊂ Dp.
(a)Init.roLeuqsp= 0, la demi-droiteD0estNion,.rOapdre´nfitif;N→N,
d’o`uf(D0)⊂ D0.
(b)H.re´soitp∈Ntel quef(Dp)⊂ Dp. On montre queDp+1est stable par
f.
Soitk≥p Alors+ 1.k−1≥p. Par HR, il s’ensuit quef(k−1)≥p, ce
quirevien`adirequef(k−1)∈ DpnemeeuqtetlulanfiHr,R.aP´rseline
f◦f(k−1)≥p. Finalement, commef∈E, il vientf(k)> f◦f(k−1)≥p.
Partransitivit´eam´eli´e,onende´duitquef(k)> p, ce qui revient
ore
´is´ementa`direquef(k)≥p+ 1.
prec
Ceci´etantvraipourtoutk≥pnetabielastablitie´balied+no,1Dp
´
parf.
(c)Ccl.ottuneitqeeuopruercu´errPao,ecnerr´rtnomanp∈N,f(Dp)⊂
Dp.
2. Soitn∈Ncatevdenee´´cppA.uqilltsupratslon´eerp=f(n). On a donc
f(n)∈ Dperitno’lu`o’df◦f(n)∈ Dp. Autrement ditf◦f(n)≥f(n). Or,
fte´snadtnaE, on af(n+ 1)> f◦f(ntrar.)aPvitisntineameli´e´eorile,
´
´
resulte que
f(n+ 1)> f(n)

Ceci´etantvraipourtoutentier,ilenre´sultequef:N→Nest strictement
croissante.
Finalement, par stricte croissance def´einligal’,´tef◦f(n)< f(n+ 1) , valide
pour tout entier natureln,ennıqertˆaeuf(n)< n+ 1.
1...urteeculsdinsoobsnaexusse´leiarencecurarr´uveperp

4

3. Pour conclure on utilise le fait suivant1:
Siϕ:N→Nest un fonction strictement croissante, alors, pour tout entier
naturel,n∈N,ϕ(n)≥n.

Applique´a`notrefonctionf:N→N, ce fait montre que pour tout entier
n≤f(n)< nssiaa’deuqecleniilib´eiterequutsspo+1,f(n) =n.
Finalement,laseulefonctionappartenanta`Enotcoiinseltfa!!´eitntdeN

Exercice 6 .—tiga’sli.1´ti.nucite’dneecixtstd’eultar´esd’un
e
Unicit´e:Soitn∈NOn.nsco`eider(p1 q1)(p2 q2)∈N2×N2tels que
n= 2p1(2q1+ 1) = 2p2(2q2+ 1)
Supposonssanspertedege´ne´ralit´equep1≥p2. On a alors
2p1−p2(2q1+ 1) = 2q2+ 1
Clairement le membre de droite est impair, ceci entraˆıne quep1−p2puis que
q1=q2.
Existence :
Lad´emonstrationseraparrecurrenceforte.
´
(a)Init.Pourn,1=epnoe´turirc=2e10×(2× Le couple (00 + 1).0)
convient.
(b)H´er.Soitn∈N⋆. On suppose que tout entierm∈[1 nerriec’´tseu,p]]
sous la formem= 2p(2qo`u(+1),p q)∈N2. Montrons qu’il en va de
mˆemepournrit´edevantlapatucsiuse.1+idnOn.
◮sinest pair, alorsnetxesi´enscoarilt,enqutse1+P.riapmiq∈N
telq quen+ 1 = 2q En ce cas, le couple (0+ 1. q) convient.
◮sinest impair, alorsn+ 1 est pair. Par suite il existem∈[1 n]] tel
quen+ 1 = 2m. Commem∈[1 n]], il s’ecrit par HR sous la forme
´
m= 2p(2q+1),ou`(p q)∈N2. Dans ce cas,n+ 1 = 2p+1(2q :+ 1)
le couple (p+ 1 q) convient.
⊲´dneie’le´rtnceenstxiupcound’dnaslesstouonabcas,el’dne-
emo
tiers (P Q) tel quen+ 1 = 2P(2Q+ 1).
(c)Ccl .P´rraurecceenna,ontmo´teunetureitn∈N⋆utpe´es’ircr
re q o e
sous la formen= 2p(2q+1),o`u(p q)∈N2
.
2. Soit Φ :N×N→Nepniefid´ar
∀(p q)∈N2Φ(p q) = 2p(2q+ 1)−1
D’apr`eslaquestionpre´c´edente,Φre´aliseunebijectiondeN2surN.
3. La projectionp:N2→Nest clairement surjective mais pas injective.
Siϕ:E→Flpcinupaetsnidrnfila,isemblesdemˆemecataoientneredxune
ilyae´quivalenceentreϕsurjective etϕ´irporpene´tve.Mectietteaiscijn
e
subsiste pas lorsqueϕsdaieteposmntlb´eqeiuueexsnmeieentredestd´efin
cardinal infini.N

Exercice 7 .—SoientEun ensemble de cardinaln,A B∈P(E) deux parties de
E.

1. Le cardinal deP(E)×P(E) est 2n×2n= 4n.
2. Pour que (A B)´vifiereA∩B=∅, il faut choisirBdans l’ensemble des parties
ducompl´ementairedeA. Pour compter le nombre de couples (A B) tels que
A∩B=∅, on discute suivant la valeurk∈[0 n]] du cardinal deA:
(a) je choisis une partieA∈Pk(E)nk.spossibilit´e
(b) puis je choisisB∈P(E\A)2n−kilibisso.se´tp
Au total, il y ank2n−kocsnf¸areneid´fftsurriueetdscenoncoupleA Bde
parties disjointes deEtelles queCardA=k.
Finalement, le nombre de couples (A B) de parties disjointes deEest
N=k=Xn0nk2n−k= 3n

3.D’apre`slesloisdeMorgan,si(A B) est un couple de parties deEtel que
A∪B=E, alors (A′ B′) = (E\A E\B) est un couple de parties disjointes
deEet vice versa. Par suite, il y a autant de couples (A B) est un couple de
parties deEtel queA∪B=Edeueupcoqasavoirointes,`itseidjseldspera
n
3 .
4.Onreconnaıˆticilacaracte´risationducompl´ementaire:
Pour construire un couple (A B) tels queA∩B=∅etA∪B=E
(a) je choisis une partieA∈P(E)2n´tseibilsoisp.
(b) puis je choisisB=∁E(A)bissop1s.´eitil
Au final, il y a donc 2ncouples (A B) de parties deEtels queA∩B=∅et
A∪B=E.N

Exercice 8 .—1. Sin < p, il n’existe pas de surjection deFnsurFp. Sin=p,
toute surjection deFnsurFpest automatiquement bijective : il y a doncn!
surjection deFni-mˆnsluEnfineme.qseul,roadn∈N⋆etp= 1, il n’y a
qu’une application deFndansF1 ! !. Elle est surjective trop de la chance !
2. Soitn p∈N⋆. Pourk∈Fp, on noteAk={f:Fn→
Fp|fest surjective, etf(1) =k}.
Soitf∈Ake´cdenedt.´entnatuess1orAlkparfD.,tnepr´esenteuxcasse
◮ese1tseltiosedc´tdenlaeu´entkparf. Dans ce cas,finduit par res-
triction une fonction surjective de[2 n]] surFp\ {k}.
◮tiose’n1aptsselseeulant´ec´edentdkparf. Dans ce cas,finduit par
restriction une fonction surjective de[2 n]] surFp.
Ainsi,Akuxdeussoinjodeteoinusidnsee´rtse:e-snmelb
◮Ak1est l’ensemble des fonctions deAkpour lesquelles 1 est le seul
ant´ec´edentdek.

5

Ak2est l’ensemble des fonctions deAkpour lesquelles 1 n’est pas le seul
ante´ce´dentdek.

Pourde´nombrerAk1`itnenpateuqsesaliontila`aear´e’dnucrisles´jed´e
me
telle fonction
•je choisis une fonction surjective
˜
f:[2 n]]→Fp\ {k}Sn−1p−1ilibse´t.psios
˜
•je prolonge cette fonction parf(1) =kp1sot´libisi.es

D’apre`sleprincipedesBergers,ils’ensuitqueCardAk1=Sn−1p−1.

Pourd´enombrerAk2realisanent`alaseuqmie`el´stepa´eediscrjenu’dnoit
´
telle fonction

•je choisis une fonction surjective
˜
f:[2 n]]→FpSn−1psibiposse.il´t
˜
•je prolonge cette fonction parf(1) =k.bilit´esissop1
D’o`uCardAk2=Sn−1peP.raedt´arucdiadvitiusneuqtianid’s,l

Card(Ak) =Sn−1p+Sn−1p−1

Finalement, l’ensembleAdes applications surjectives deFnsurFp´etantla
´ ion disjointe desAk, il vient
reun
Snp=Card(A) =Cardk=[p1Ak!
p p
=XCard(Ak) =X[Sn−1p+Sn−1p−1]
k=1k=1
=p[Sn−1p+Sn−1p−1]

3.Parre´cuurencesurn∈N⋆, montrons que

Snp=pkX=0(−1)p−kkpkn

(a)Init.uesqroLn= 1, on a
k=Xp0(−1)p−kkpk=k=pX0(−1)p−kpkp−−11=p(1−1)p−1

Sipon1,tiobt1eneq,c=`aiuocrrseopdnibneS11et sip >1, on
obtient0cequicorrespondeneffet`aS1p.

(b)d.H´´eersoitn∈N⋆tel que
pn
∀p∈N⋆ Snp=kX=p0(−1)p−kkk
Ve´rifionsquenos:ete´irporpetetecediterh´+1tip∈N⋆, on a :
´

Onv´erifieaise´mentquelasuiteaainsi construite est une suite croissante
d’entiers compris entre 1 etn.
Finalement, l’ensemble des suites croissantes depentiers compris entre 1 et
net suites strictement croissantes depentiers compris entre 1 etn+p−1
sonte´quipotents.Ilyadoncn+pp−1suites croissantes depentiers compris
entre 1 etn.N
.
Sn+1p==pp(Spnk=Xp0+(−1S)npp−−k1)pkkn+pk−=X10(−1)p−1p−k1kn!Exercice 10 .—1.S1=(x1 x2     xn)∈ {01}n|x1+x2+  +xn=p
−kdre´PuorernombS1u’ensitaoidniuqsepate´seltiral´earalt`enenm`d´ec,on
solution :
−n•je choisis une partie{i1     ip}`apeml´dtesen´e[1 n]]pn
=pkpX=−01(−1)p−kkp−pk1kn+p×ppolitissbie´.s
AppliquonslaformuledePascaletlapetiteformuledescoeffdubinˆome,•on posexi1=  =xip= 1bissop1.se´tili
il vient :•pourj ∈ {i1     ip},xj= 0itils.´e1opssbi
Sn+1p=pk=X−01(−1)p−kppk−−11kn+pn+1=pkX=−01(−1)p−kkpkkn+pn+1Au final,CardS1=np.
2.S2=(x1 x2     xn)∈(N⋆)n|x1+x2+  +xn=p.
p−1rlesmbre´enopardneecocmmnOitul”snouos“os-ssp=(x1 x2     xn)∈
=X(−1)p−kkpkn+1+pn+1=kXp=0(−1)p−kkpkn+1(N⋆)n|x1+x2+  +xn≤p. A une sous-solution (x1 x2     xn) on
k=0associe la suite (u1 u2     un)´dperafiein
Lapropri´et´eesth´er´editaire.
(c)Concl.tn´ranomqeeucu´errpa,oceenrr∀k∈[1 n]] uk=x1+  +xk
On observe que la suite (u1 u2     un) est strictement croissante caruk+1−
∀(n p)∈N⋆×N⋆ Snp=pX(−1)p−kkpknuk=xk+1∈N⋆. De plusun=x1+x2+  +xn∈[1 p]] car (x1 x2     xn)∈
k=0sp.
ombre de sa1(a`iuqed´eroc´Lepx1 x2     xn)∈spassocie la suite strictement croissante
Exe2r.ciEceta9nt.d—no´neeunepartie.dLeen1Fnset`aiup´le´e(me ntsap)lin∈’yFpn’qutesanup.ndesene(efulcoa¸u1 u2     unectiv)dfin´eunitppaeacilnoitejib2
rangerces´el´ementsparordrecroissant.Pa´equent,ilyaautantdede
r cons
arties Φ :sp→ {(a1     an)∈Fnp|(ak) strictement croissante
suites strictement croissantes depentiers compris entre 1 etnque de p (x1 x2     xn)7→(u1 u2     un)
`apdetsenme´le´Fnroiavas,`pn.
´
3. Etant donnee une suite croissantea= (a1     ap) deped´eeml´tsenFn, on lui En particulier,Card(sp) =np.
associe la suiteb= (b1     bpdealindracelrenimrete´rpaiefin´e)dnt,pourdFinalemeS2, on observe que
∀k∈[1 p]] bk=ak+k−1
s=S⊔s

Onv´erifieaise´mentquelasuitebainsi construite est une suite strictement
croissante d’entiers compris entre 1 etn+p−1.
Inversement,´etantdonn´eeunesuitestrictementcroissanteb= (b1     bp) de
pel´e´sdement[1 n+p−1]], on lui associe la suitea= (a1     ap)d´efineiapr

∀k∈[1 p]] ak=bk−k+ 1
2tacilppaice´rnoiueql’steellue??proq

6

}

p2p−1

Paradditivite´ducardinal,ils’ensuitque
CardS2=Card(sp)−Card(sp−1) =pn−p−n1=np−−11

Ex

a
3.OPonuirntcreottdedernie`reed´emˆemitlaonsuoi,neutsqhcrameuq+xenpr≤ce´pe´`´deitnrtveTuot.enmmedlemmbosCe.enle’merbromen(X Y)∈P(E)2|X∩YPk(E).
uitσp= (x1 x2     xn)∈Nn|x1+x2+nuetno’dlpecluoe´rctieliaero,dnPourcefilaeitasa`tn´ralimqune`eets´esap
lesxipeuvent s’annuler, la suite (u1 u2     untpiaersepar:e´dd)einfi
•je choisis une partieIa`keneml´´edetsEknopssbilitie´.s
∀k∈[1 n]] uk=x1+  +xk•je choisis un couple (X′ Y′) de parties disjointes dansP(E\I)×P(E\I)
est une suite croissante (pas strictement a priori) d’entiers compris entre 1 et3n−kcfexo7)tili(se´opbiss
n.xe’lo,9opa’Dse`rainsuetq•on poseX=I⊔X′ Y=I⊔Y′.est´libisip1so
Au final, il y akn3n−kruironstsdec¸con(euolpuecnafX Y) de parties de
Card(σp) =n+pn−1Etel que le cardinal deX∩Yioetaxtcmene´tgeal`asksnadtnat.Enr´einjec
le calcul deS2, il vient,
Finalementn
S2=Xk×Card(X Y)∈P(E)2|X∩YPk(E)
CardS3=Card(σp)−Card(σp−1) =n+np−1−n+np−2=nn+−p1−2k=0
n−1n−k
N=nkX=0knk3n−k=nkXn=1k−13
ercitLci’eid1e´4e.p—’agi.Ils1ldnadiarpaesreuscstultcevinasommettededieestcruouclacrelarspestideidanxuedottuseeltd’ajouterlescarE=.r-nkn=X−01nk−13n−1−k=n4n−1
es :
3.Etantdonn´ee(X Y)∈P(E)×P(E), on aCard(X∪Y) +Card(X∩Y) =
((ba))iillyyaanitrap1ts)(sl1glinraceanidtrapdseitievide)an0lp(radeceraidCardX+CardY terme, il vient `. En sommant ceci term
e a ,
e on
(c) il y a2nparties de cardinal 2 (paires)S2+S3=XCard(X∩Y) +XCard(X∪Y)
(XY)∈P(E)2(XY)∈P(E)2
((de))ialnydaso3nol3nadni!=arecsdie,rtapXCard(X) +XCard(Y)
(XY)∈P(E)2(XY)∈P(E)2
Du coup,n n= 2nXCardX+ 2nXCardY
S1=XC dX=X XCard(X) =X Xk= 2n+X1∈SP(E)Y∈P(E)
ar
X∈P(E)k=0X∈Pk(E)k=0X∈Pk(E) 1
X
=k=n0k×nk=nk=X1k×nk=nkX=1n×kn−−11ExerciFciena1l5e.me—roL’uqsaanoriaffqteudeiue`anend´t,onS3unes3=nom22mn−e2.retni’duebnnoerefxleetsdoublN-
n−1
n−1
=nnk−X1=0k=neptiar’ularaittr2evtnAdeofeidreordFsdntoe´emtnssues´sleontimaomesadly’iquestiarepuqT.leiede∈c’FenAenclaira’d,chaquee.Ainsirntieagitils’t´e,psenorpceel´ts:tnanetnijo∈utFeneacqoumseruoprtaphec´r
n
2. Pour calculerS2edisndommcotecucee´pe´rnestedmmntleuivainalcardX∩Y.X Xi=X Xi
On aA⊂Fni∈A i=1A⊂Fn
i∈A
n
S2=X XCard(X∩Y=)Xni×Card{A∈P(Fn)|A∋i}
k=0 (XY)∈P(E)2X∩YPk(E)i=1
n
=Xk×Card(X Y)∈P(E)2|X∩YPk(E)erronbmuoPe´dr{A∈P(Fn)|A∋i}itle´ecr,ondene`miuqsepate´sla`ant
k=0leelaptrno’dnuteie:tisaliear´

7

•l’isishoecjtneme´le´i
•je choisis une partie dansP(E\ {i})
Ainsi,Card{A∈P(Fn)|A∋i}= 2n−1et par suite

X Xi=
A⊂Fni∈A

=

kn.t´esbiliossip
2n−1possibilit´es

n
Xi×Card{A∈P(Fn)|A∋i}
i=1
n
2n−1×Xi= 2n−2n(n+ 1)
i=1

Exercice 16 .—en œuvre le prinicipe des bergers :on met

N

1. nombres de mains
•je choisis 5 cartes parmi 32523soisp.est´libi
Il y a325mains possibles
2. nombre de carres d’as
´
•je choisis 4 as parmi 444psoes.lit´sibi
•jechtrachedeisioenuserff´teenteaudiur821ssbilitiop´es
Ilya28carr´esd’aspossibles
3.
4.nombredecarre´sd’as
•je choisis un couple (h1 h2) de hauteurs distinctes8×es.sop7ibis´til
•jechoisis4catrsea`alahtuuerh144litissbiop´
es.
•je choisis une carte de hauteurh214itilibsspoe´s

Ilya224carre´spossibles.
Remarque :on peut aussi dire 8×r´arpoes8c2ir.elespssibm´etarsy

5. nombre de fulls
•je choisis un couple (h1 h2) de hauteurs distinctes8×7opssbilitie´s.
•`sethalaetuarujhoecisisar3ch134ibis´tilsop.es
•je choisis 2 carte de hauteurh242bilit´espossi
Au total , il y a 8×7×3424fulls possibles.
6. nombre de brelans
•je choisis une hauter pour le tripletilit´es.op8biss
•je choisis une paire de hauteur{h2 h3}
distinctes entre elles et distinctes deh127soisp´.tseibil
•je choisis 3 cartes de hauteurh143tilise´opbiss

8

•je choisis 1 carte de hauteurh2
•je choisis 1 cartes de hauteurh3
Au total , il y a 8×72×43brelans possibles.
7. nombre de quinte flush

14t´esbiliossip
41ospsibilit´es

•je choisis une couleur14psot´libisi.es
•halsisioedruetua`imerpalecthrjaecere41ospt´libisise.
Au total , il y a 16 quinte flushs possibles.
8. nombre de mains monocrhomes !
•je choisis une couleur41possibs.´eitil
•je choisis 5 crtes de cette couleur85.tseibilossip
´
Au total , il y a 224 mains monochromes possibles. On peut alors retrancher
les 16 quintes flush.
9. 3 coeurs et 2 rois ! On distingue 2 cas, suivant que la main continet le roi de
coeur ! !
Avec roi de coeur
•je choisis le roi de coeur11s.it´esspoilib
•je choisis un autre roi13.est´libisiosp
•je choisis 2 autres coeur72possibiltie´.s
•je choisis 1 autre carte112´til.sesopibis
Au total , il y a 3×212mains avec 3 coeurs et 2 rois dont le roi de coeur.

Sans roi de coeur
•je choisis 2 rois (pas de coeur)23´es.oplitissbi
•je choisis 3 coeur (pas le roi)37ilibse´tpisso.
Au total , il y a 3×37mains avec 3 coeurs et 2 rois sans le roi de coeur.

Finalement, il y a 1424 mains contenant exactement deux rois et trois coeurs.
N
Exercice 17 .—1. Il s’agit du graphe d’une application injective deF8dans
lui-meˆme.Ilya8!faconsdeplacerleshuittours.
¸
2.kansourdunetcolonotccpue´enssrenourtotisepaesesrletcatnemuaylxear
chacune de ces colonnes
•je choisisknnlocosek8ilibissop.se´t
•je remplis leskcolonnes comme le graphe d’une injection deFkdansF8
(88−!kt´li.essop!ibis)
Au total, il y ak!×k82erlestounsdeplacf.¸aroscN