Rappels sur les ensembles d'enombrement

Description

Chapter 1Rappels sur les ensembles,d´enombrementSommaire1.1 Motivation : l’´equiprobabilit´e sur un ensemble fini . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Notions de base sur les ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2.1 D´efinition d’un ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2.2 Parties d’un ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.1 Image et image r´eciproque de parties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.2 Injectivit´e, surjectivit´e, bijectivit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.4 Rudiments de cardinalit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.5 D´enombrements classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.5.1 Produit cart´esien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.5.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.5.3 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.5.4 Arrangements, injections, p-listes sans r´ep´etitions et tirages ordonn´es sans remise . . . . . 111.5.5 ...

Informations

• Publié par: Zuib
• Nombre de lectures: 24
• Langue: Français

Extrait

Chapter

1

Rappels sur les de´nombrement

ensembles,

Sommaire 1.1Motivation:l’´equiprobabilite´surunensemblefini.......................... 1.2 Notions de base sur les ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1De´finitiond’unensemble..................................... 1.2.2 Parties d’un ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1Imageetimagere´ciproquedeparties.............................. 1.3.2Injectivit´e,surjectivite´,bijectivite´............................... 1.4Rudimentsdecardinalite´........................................ 1.5De´nombrementsclassiques........................................ 1.5.1Produitcarte´sien......................................... 1.5.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.3 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.4 Arrangements, injections,plsietssna...es..erimassnesn´onrdsogeratitesnoitite´pe´rs 1.5.5Coefficientsbinomiaux,partiesd’unensemblesettiragesnonordonn´essansremise.... 1.6Principesdebasedude´nombrement.................................. 1.7Quelquesconseilspratiquespourlesexercicesd’e´quiprobabilit´e...................

Objectifs : classiques.

5 5 5 5 7 7 7 8 8 8 10 10 11 11 13 14

Rappelerlesnotationssurlesensembles,lesrudimentsdecardinalite´etlesde´nombrements

Motscle´s: •cesrnoit,noietniun.mentaire,compl´e •application, injection, surjection, bijection. •ensemble fini, cardinal. •ra´tiuctrpdoeise,nnuplet,nstlipee,utrmioatˆome.,nocffieicnedtbuni

Outils : •d´ind’n,ncdaenepedsepicnoitcejibpriaptr,eed.ntioi •n.mlueldeu,ofromrunsgclaletdreiPaaweotdeNeˆnmfoudib

Techniquesded´emonstration: parr´ecurrence.

e´galit´ededeuxensemblespardoubleinclusion,contraposition,de´monstration

1.1

Motivation :

l’e´quiprobabilit´esurunensemblefini

Onrappellequel’e´quiprobabilite´Psur un ensemble fini Ω est l’application de l’ensembleP(Ω) des parties de Ω dans [0,nfieiapr1d]e´ CardA ∀A∈ P(Ω),P(A) =. Card Ω Cepremierexempledeprobabilit´evaeˆtrel’occasionderappelerquelques´ele´mentsdelathe´oriedesensembles,et lesprincipesdebasedude´nombrement.

1.2

1.2.1

Notions de base sur les ensembles

D´efinitiond’unensemble

Pourde´crireunensemble,esesedsteneml´´eodtuepnoilalrennolccesadentseatro’uqppane’c:ectsellela de´finitionenextensionorastpesn’lembseisnia,e´nnod.nUne{1,3,2}et{1,2,3}ldb´meec.eeesnˆmmetnelirev Dans cet exemple, 2 est unemtn´´eelde{1,2,3}, ce qui se note

2∈ {1,2,3};

lemeˆmee´le´mentpeutapparaıˆtreplusieursfoisdanslalistedes´el´ements,ainsi{1,3,2}et{2,1,2,3}detlenivcr´e mˆemeensemble. {1,3}estune partieouun sousensemblede{1,2,3}; on dit que{1,3}estinclusdans{1,2,3}, ce qui se note

{1,3} ⊂ {1,2,3}.

♠Attention !2∈ {1,2,3}et{2} ⊂ {1,2,3}. Onpeutausside´finirunensembleenpmoche´risnenost’ea`redidoenc,iset´eroppresulaotlannncaraciuqse´te´ir ses´el´ements: {2,4,6}={x∈ {1, . . . ,7}: 2 divisex}.

Quelques ensembles usuels :

•l’ensemble des entiers naturelsN={0,1,2, ...}, ∗ l’ensemble des entiers naturels strictement positifsN={1,2, ...},

•l’ensemble des entiers relatifsZ={...,−2,−1,0,1,2, ...},   p ∗ •l’ensemble des nombres rationnels :Q=, p∈Z, q∈N, q •seonlbderse´bmerels’elemnsRsopslee´nuosfiti,dessulresrnombR + ...

1.2.2

Partiesd’unensemble

On noteP(Ω) l’ensemble des parties de Ω. ´ ♣Exercice :Soit Ω ={1,2,3}l’ensemble. Ecrire PdeiltanΩiembCoetcnitsidseitrapeΩd(?.s)trap`seia deuxe´lementsdistinctes?

Soient Ω un ensemble, etAetBdeux parties de Ω.

•lanioun´erdeAetB´teeno,A∪BeΩcotied´eedmpos,paraselttsende´eeseml´Anemeedstsedt´le´eB:

{1,2,5,6} ∪ {2,3,5,7}={1,2,3,5,6,7}

5

Lare´uniondedeuxensemblescorrespondaulienlogique“ou” :

x∈A∪B⇔x∈Aoux∈B

(noter que sixest dansA∪B, alorsxtuepla`erteˆansdoiafsAetdansB) Lar´euniond’unefamilled’ensemblescorrespondauquantificateur∃soit ((“il existe”) : A i ) i∈I une famille de parties d’un ensemble Ω. Alors [ x∈A i ⇔ ∃i∈I, x∈A i . i∈I

•l’intersectiondeAetBon´t,eeA∩BartitlapcompedeΩdsnas,seonisqutsoiafalt`sedee´soneme´le´Aet dansB: {1,2,5,6} ∩ {2,3,5,7}={2,5}

L’intersection de deux ensembles correspond au lien logique “et” :

x∈A∩B⇔x∈Aetx∈B.

L’intersection d’une famille d’ensembles correspond au quantificateur∀(“pour tout”) : famille de parties d’un ensemble Ω. Alors \ x∈A i ⇔ ∀i∈I, x∈A i . i∈I

soit (A i ) i∈I une

•laidre´ffecne´mysrietequdeAetB´teeno,AΔBisqutseneml´´eessnadtiostno,seltparatiedeΩcompos´eed Asoit dansBmais pas dans leur intersection :

{1,2,5,6}Δ{2,3,5,7}={1,3,6,7}

Ladiff´erencesym´etriquededeuxensemblescorrespondaulienlogique“ou exclusif” :

c c x∈AΔB⇔x∈A∩Boux∈B∩A .

c •lerieneat´lmeocpmdeAeenot´nsΩ,daA´eels´deees´poomcΩedeitrapaltse,ptsamentsdeΩquineson dansA: c Ω ={1,2, ...,10}, A={1,3,5,7,8,9,10}, A={2,4,6}.

c Lepassageaucompl´ementairecorresponda`lane´gationlogique:x∈A⇔x∈/ A. Remarquonsquelecompl´ementaired´ependdel’ensembleΩconside´re´,etque

c c A∪A= Ω etA∩A=∅.

Proprie´t´es1.1SoientA,BetCtrois parties d’un ensembleE.

c c c •(A∪B) =A∩B

c c c •(A∩B) =A∪B

•(A∪B)∩C= (A∩C)∪(B∩C)

•(A∩B)∪C= (A∪C)∩(B∪C)

De´monstration:urmoporl’´ntretie´gelaxuneededarderpoc`eturpnoepel,sesbmdouble inclusion: AetBulseetsiuxga´entosmenestiAest inclus dansB, etBest inclus dansA. Montronsainsilapremie`repropri´et´e.SoientAetBdeux parties d’un ensembleE.

6