Colle N°13: Entiers naturels, dénombrement

Description

MPSI du lyc´ee Rabelais http://mpsi.saintbrieuc.free.fr semaine du 3+7 janvier 2012 PROGRAMME DE COLLE S12 NB : seules les d´emonstrations des th´eor`emes, propositions ´etoil´ees ne sont pas exig´ees. ´ENTIERS NATURELS, ENSEMBLES FINIS, DENOMBREMENT Entiers naturels Th´eor`eme.— Th´eor`eme de r´ecurrence —. SoitP une propri´et´e des ´el´ements de N, et n ∈N.0 • Initialisation : P(n ) est vraie0 ∀n≥ n ,P(n) ⇐⇒0 • H´er´edit´e : (∀n≥n ), P(n)⇒P(n+1)0 Th´eor`eme*.— Th´eor`eme de r´ecurrence double —. SoitP une propri´et´e des ´el´ements de N, et n ∈N.0 • Initialisation : P(n ) etP(n +1) sont vraies0 0 ∀n≥n ,P(n) ⇐⇒0 • H´er´edit´e : (∀n≥ n ), P(n) etP(n+1)⇒P(n+2)0 Corollaire*.— Th´eor`eme de r´ecurrence forte —. SoitP une propri´et´e des ´el´ements de N, et n ∈N.0 • Initialisation : P(n ) est vraie0 ∀n≥ n ,P(n) ⇐⇒0 • H´er´edit´e : (∀n≥n ), P(n ) et ··· et P(n) ⇒P(n+1)0 0 En pratique : pour r´ediger une d´emonstration par r´ecurrence, proc´edez en trois ´etapes : • Initialisation : vous v´erifiezP(n )0 1• H´er´edit´e : soit n≥ n tel que P(n ) est vraie , on montre que P(n+1) est vraie.0 0 • Conclusion : invoquez le principe de r´ecurrence pour conclure. Ensembles finis D´efinition : Soit E un ensemble. On dit que E est fini s’il est en bijection avec un intervalle d’entiers F . L’entiern n, s’il existe est unique. On l’appelle le cardinal de E. On note Card E = n. Th´eor`eme*.— Cardinal des parties —. Soit E un ensemble fini et A∈P(E) une partie de E.

Sujets

• Classe préparatoire aux grandes écoles
• Mathématiques, physique et sciences de l'ingénieur
• Public Readiness and Emergency Preparedness Act
• exercices
• Mathématiques

Informations

• Publié par: colle-mpsi
• Nombre de lectures: 21
• 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≥n0P(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≥n0P(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≥n0P(n)⇒•⇐:noitadesitliea´it:iIn(∀P(nn0≥) ens0)tvraPie(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 etCardP(En)= 2n
L’ensemblePp(En) desitsepra`apntmes´´eeldeEnest fini etCardP(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),ECeatrdFdfe1ux({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
pnest le nombre de•listes strictement croissantes depentsd´eelme´En
•partaei`spnest´lmee´deEn

Propri´ete´sdescoefficientsdubinˆome

Theoreme*.—Pour tous (n p)∈N2,
´ `

0n= 1n1=n

pn=n−pn pn11++=pn+p+n1

Savoir-faire :erpreinttion´etarenuodnnlareontisesneilbmdetssece

2

Pnk=0kn= 2n