Fiche de révision dénombrement MPSI

CHAPITRE 33 : ENSEMBLES ET DENOMBREMENT

I – Généralité sur les ensembles

1) Intersections, réunion, différence

 et  [pic 1][pic 2]

2) Parties d’un ensemble  et son complémentaire [pic 3][pic 4]

 et  [pic 5][pic 6]

3) Fonction indicatrice d’une partie d’un ensemble non vide [pic 7]

Fonction indicatrice :          [pic 8]

ppté :          [pic 9]

 [pic 10]

 [pic 11]

 [pic 12]

Différence symétrique : [pic 13]

ppté :          [pic 14]

        ( : groupe abélien (de neutre )[pic 15][pic 16]

         : anneau commutatif (de neutres  et )[pic 17][pic 18][pic 19]

II – Ensembles finis

ppté :          et  deux ensembles tels que  bijection[pic 20][pic 21][pic 22]

si  ou  fini  [pic 23][pic 24][pic 25]

ppté :         [pic 26]

ppté :         [pic 27][pic 28]

1) Opérations sur les ensembles finis

        a. réunion de 2 ensembles finis

Union disjointe :  quand [pic 29][pic 30]

théorème des 4 cardinaux :  et  ensembles finis [pic 31][pic 32]

        [pic 33]

        [pic 34]

        b. réunion d’un nombre d’ensembles finis 2 à 2 disjoints  

 des ensembles finis 2 à 2 disjoints [pic 35]

 [pic 36]

 est fini et [pic 37][pic 38]

 [pic 39]

        c. produit cartésien d’ensembles finis

 et  ensembles finis : [pic 40][pic 41][pic 42]

 ensembles finis :   [pic 43][pic 44]

2) Applications entre 2 ensembles finis

 et  ensembles finis tels que  et [pic 45][pic 46][pic 47][pic 48]

         injective   surjective[pic 49][pic 50][pic 51]

 et  ensembles finis non vides tels que  et  [pic 52][pic 53][pic 54][pic 55]

Ensemble des applications de  dans  : [pic 56][pic 57][pic 58]

ppté :         nombre d’applications de  dans  : [pic 59][pic 60]

 et  ensembles non vides:  [pic 61][pic 62][pic 63][pic 64]

ppté :         nombre d’injections de  dans  :[pic 65][pic 66]

        ou bien  : il n’y a pas d’injections de  dans [pic 67][pic 68][pic 69]

        ou bien  : il y a  injections de  dans [pic 70][pic 71][pic 72][pic 73]

ppté :         nombre de bijections de  dans  :[pic 74][pic 75]

        ou bien  : il n’y a pas de bijections de  dans [pic 76][pic 77][pic 78]

        ou bien  : il y  bijections de  dans [pic 79][pic 80][pic 81][pic 82]

3) Parties d’un ensemble fini

...