Cours de Combinatoire

Cours de Combinatoire 5 novembre 20101 Rappels sur les ensembles Definitions Soit A et B deux ensembles. On note par :– |A| son cardinal, c.a.d. le nombre d'elements de A;– A∪B l’union de A et B, A∪B ={x :x∈A ou x∈B};– A∩B l’intersection de A et B, A∩B ={x :x∈A et x∈B};– A⊂B si pour tout x, si x∈A alors x∈B;– A\B la diff´erence de A et B, A\B ={x :x∈A et x∈/ B}– A×B l’ensemble des couples ordonn´es (x,y) tel que x∈A et y∈BA×B ={(x,y) :x∈A et y∈B}Propriet´es– |A|+|B| =|A∪B|+|A∩B|– |A×B| =|A||B|n n– |A |=|A| pour n∈N.2 Applications, fonction caract´eristique, arrangementsD´efinitions– Soit A et B deux ensembles. Une application φ de A dans B, not´ee par φ : A→ B, associea` chaque ´el´ement a∈A un unique ´el´ement de B, not´e φ(a). Formellement on peut voir uneapplication comme un sous-ensemble Φ de A×B tel que pour tout x∈A il existe un uniquey∈B tel que (x,y)∈ Φ.– Soit A⊂B, on d´efinit sa fonction caract´eristique f :B→{0,1} parA0 si a∈/ Af (a) =A 1 si a∈APropri´et´es|A|– L’ensemble des applications de A dans B a cardinalit´e |B| .Pour chaque ´el´ement de A on a|B| possibilit´es de choisir son image.n– L’ensemble des fonctions caract´eristiques sur l’ensemble B a cardinalit´e 2 ou` n =|B|.Pour chaque ´el´ement de B on a deux possibilit´es de choisir son image.Il y a une bijection directe entre l’ensemble P(B) des parties de B et l’ensemble des fonctionsncaract´eristiques sur B, donc|P(B)| = 2 , ou` n =|B|.D´efinitions– Une injection φ : A→ B ...