La lecture à portée de main
Description
Sujets
Informations
Publié par | colle-mpsi |
Nombre de lectures | 29 |
Licence : |
En savoir + Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
|
Langue | Français |
Extrait
MPSIdulyc´eeRabelaishtt:p//pmisai.sbrntuciere.frf.e
PROGRAMME DE COLLE S12
semaine du 3+7 janvier 2012
NB :seulesrpposotiroe`em,sil´eesneions´eto´gix.seetnosesaplonemd´esnoitartse´htseds
´
ENTIERS NATURELS, ENSEMBLES FINIS, DENOMBREMENT
Entiers naturels
Th´re`me.—
eo
The´ore`meder´ecurrence—.SoitPenuporpe´iredt´edes´el´ementsN, etn0∈N.
∀n≥n0P(n)••⇐:noitasliiaitIn:H´eit´er´ed
⇒
P(n0) est vraie
(∀n≥n0)P(n)⇒ P(n+ 1)
The´ore`me*.—The´o`de´currencedouble—.SoitPdetsneme´le´sede´te´nepropriuN, etn0∈N.
reme e r
∀n≥n0P(n)⇐⇒
•Initialisation :P(n0) etP(n0+ 1) sont vraies
•ree´´H:eid´t(∀n≥n0)P(n) etP(n+ 1)⇒ P(n+ 2)
Corollaire*.—Th´eor`emeder´ecurrenceforte—.SoitPuprneirpo´te´sede´le´stedmeneN, etn0∈N.
∀n≥n0P(n)⇒•⇐:noitadesitliea´it:iIn(∀P(nn0≥) ens0)tvraPie(n0)et etP(n)⇒ P(n+ 1)
•Her
´ ´
En pratique :se:tepaedezroc´ois´entruce´rrapp,ecnerronemd´neontirastdi´erugeprrou
•Initialisationzefi:vsvouri´eP(n0)
•it´ee´Hde´r: soitn≥n0tel queP(n0) est vraie1, on montre queP(n vraie.+ 1) est
•Conclusion pour conclure. urrence ´ de: invoquez le princi
pe rec
Ensembles finis
De´finition:SoitEun ensemble. On dit queEestfinien bijection avec un intervalle d’entierss’il est Fn. L’entier
n, s’il existe est unique. On l’appelle lecardinaldeE. On noteCardE=n.
The´ore`me*.—Cardinaldesparties—.SoitEun ensemble fini etA∈P(E) une partie deE. Alors
Aest un ensemble fini etCardA≤CardE,
A=Esi et seulement siCardA=CardE.
Corollaire*.—Soitfune application d’un ensembleEvers un ensemblefiniF.
L’ensembleimagef(E) est fini etCardf(E)≤CardF
Cardf(E) =CardFsi et seulement sifest surjective.
Corollaire*.—Soitfune application d’un ensemblefiniEvers un ensembleF.
L’ensembleimagef(E) est fini etCardf(E)≤CardE
Cardf(E) =CardEsi et seulement sifest injective.
The´or`eme*.—SoientEetFdes ensembles finis.
Il existe une injection deEdansFssiCardE≤CardF
Il existe une surjection deEsurFssiCardE≥CardF
Il existe une bijection deEdansFssiCardE=CardF
1ctse’yh’lhtopse`er´deurecncree
1
The´ore`me.—SoientEetFdeux ensemblesfinisetf:E→Fune application.
On suppose queCardE =CardF. Les assertions suivantes sonttnelseqe´aviu
~•fest injective
•fest surjective
w•fest bijective
De´nombrements
E+CardF
Th´eor`eme.—SoientEetFdes ensembles finis,A B∈P(E) des parties deE. Alors
SiEetFsont disjoints, lar´ondieunietniojsE∪Fest finie etCard(E∪F) =Card
laeur´noinE∪Fest finie etCard(E∪F) =CardE+CardF−Card(E∩F)
leaintme´eplomcer∁EAest fini etCard(E\A) =CardE−CardA
lacnee´erdffiA\Best finie etCard(A\B) =CardA−Card(A∩B)
leporudtiacrt´esienE×Fest fini etCard(E×F) =CardE×CardF
L’ensembleFEdetoutes les applicationsdeEversFest fini etCard(FE) = (CardF)CardE
L’ensembleI(Ep Fn) desapplications injectivesdeEpversFnest fini etCardI(Ep Fn) =Apn=(nn−!p)!si
0≤p≤n, et 0 sinon.
L’ensembleB(Ep Fn) desapplications bijectivesdeEpversFnest fini etCardB(Ep Fn) =n! sip6=n, et 0
sinon.
L’ensembleP(En) detoutes les partiesdeEnest fini etCardP(En)= 2n
L’ensemblePp(En) desitsepra`apntmes´´eeldeEnest fini etCardP(En)=np=p!(nn!−p)!si 0≤p≤n
et 0 sinon.
tf:E→F rune application
dTee´hEorse`urmeF..—OnTsuhpo´epro`esemequdee(s∃bpe∈egNrr⋆s) (—∀y.S∈oiFt),ECeatrdFdfe1ux({ye}sn)emb=p.Alorjssutniiescelevsefi
¯
CardE=pCardF
Savoir-faire :ulitirlseh´etr`eoseeBmedepsuogrrenombrd´ererEmone´drurerbetpoF.
Analyse combinatoire
SoitEnnensembl`eaunrlgemoeseunpantrinonseuqle`dacsemenestO.e´´lusuiblealetadans:avtn
cardinal ensemble des
•tirages successifs avec remise deped´eeml´tsenEn
npest le nombre de•petitiondelsiet`srae´pedstneme´el´En(oup’´sdteisntme´eeldsel-En)
´
•applications deFpdansEn
•tirages successifs sans remise dep´el´menestedEn
Apnest le nombre de•listes depedstcnitsditseneml´´eEn(oupednest´lmed’´eentsngemarra-En)
•applications injectives deFpdansEn
•seassnerimesedssgeratin´taulimpel´ementsde´En
pnest le nombre de•listes strictement croissantes depentsd´eelme´En
•partaei`spnest´lmee´deEn
Propri´ete´sdescoefficientsdubinˆome
Theoreme*.—Pour tous (n p)∈N2,
´ `
0n= 1n1=n
pn=n−pn pn11++=pn+p+n1
Savoir-faire :erpreinttion´etarenuodnnlareontisesneilbmdetssece
2
Pnk=0kn= 2n