Dénombrement

 

II.-DENOMBREMENT

1.  Factorielle

Soit , on appelle « factorielle (de) n » le réel noté  défini par

·                    Si

·                    Si

 

            Exemples : 

 

          Propriétés :

                      

 

            Exemple :

 

2.  Cardinal d’un ensemble :

Le cardinal d’un ensemble E est le nombre d’éléments de E. On le note .

 

            Propriétés :

·       

·         Si  

·         Dans le cas général

              

·  

 

3.  Arrangement

a.   Définition :

Soit E un ensemble ayant n éléments et .

Un arrangement de p éléments de E est une suite ordonnée de p éléments de E, deux à deux distincts.

 

Exemples :

-                    

 sont des arrangements de 3 éléments de E

 n’est pas un arrangement d’éléments de E

 

-                    

Un nombre de 3 chiffres différents écrits avec les éléments de E est un arrangement de 3 éléments de E

 

-                     Une urne contient 10 jetons numérotés de 1 à 10

On tire successivement et sans remise 3 jetons de l’urne.

Le résultat peut se représenter par un triplet ou x1 désigne le numéro du 1er jeton, x2 désigne le numéro de 2e jeton, x3 désigne le numéro du 3e jeton

Comme le tirage est sans remise ; x1, x2, x3 sont tous différents

On peut donc assimiler le résultat des tirages à un arrangement de 3 éléments pris parmi les 10.

 

         Remarque :

Deux arrangements distincts diffèrent soit par la nature soit par l’ordre des éléments :

           

 

b.        Nombre d’arrangements :

 

Considérons un ensemble E ayant n éléments et soit . On veut dénombrer tous les arrangements de p éléments de E.

 

Pour le premier élément de l’arrangement, on a n possibilités.

Avec chacune de ces n possibilités, on peut former (n-1) arrangements en prenant un élément parmi les (n-1) éléments restants. On peut donc au total former n(n-1) arrangements de deux éléments de E.

Avec chacun des ces n(n-1) possibilités on peut former (n-2) arrangements de 3 éléments en lui associant un élément pris parmi les (n-2) autres ; donc au total, on peut  avoir

n(n-1)(n-2) arrangements de 3elements de E.

……………….

 

Lorsque le (p-1) élément est choisi, on n’a plus que (n-p+1) choix pour le pe élément pour former les arrangements de p éléments

 

On a alors  arrangements de p éléments  de E possibles.

       Théorème :

Le nombre d’arrangements de p éléments d’un ensemble ayant n éléments est :

 

 

4.      Permutation :

E étant un ensemble ayant n éléments. Une permutation des éléments de E est un arrangement de n éléments de E.

       

        Le nombre de permutation des éléments de E est donc :    

        

 

Théorème :

Le nombre de permutation de n éléments est :

 

5.      Combinaison :

a.        Définition

Soit un ensemble ayant n éléments et  ;  une combinaison de p éléments de E est une partie de E ayant p éléments

 

Exemple :

-

 sont des combinaisons de 3 éléments de E

- Un sac contient 10 boules.

On extrait simultanément de ce sac 3 boules. On peut assimiler un résultat de cette extraction à une combinaison de 3 éléments.

 

b.        Nombre de combinaison :

Soit E un ensemble tel que

Posons  et considérons

On peut former  permutations des éléments de A. Mais comme une permutation des éléments de A est un arrangement de p éléments de E. on a  arrangements des p éléments de E ( formés avec les  éléments de A)

On a donc   arrangements avec une combinaison  de p éléments de E.

Si  est le nombre de combinaisons de E, on peut obtenir au total arrangements. Et on obtient tous les arrangements de cette façon.

Or le nombre d’arrangements de p éléments est , on a l’égalité :

 

Théorème :

Le nombre de combinaison de p éléments d’un ensemble  à n éléments est :

 

 

Propriétés :

¨                                                 

 

¨              Triangle de Pascal :

 

p

n

0

1

2

3

 

p

p+1

0

 

 

 

 

 

 

1

 

 

 

 

 

2

 

 

 

 

3

 

 

 

 

 

 

 

 

 

 

n

 

 

 

    

               װ 

n+1

 

 

 

 

 

            Ce qui donne :

 1

 

 1        1

 

 1        2          1

 

 1        3          3          1

 

 1        4          6          4          1         

 

 1        5   +    10       10       5          1

                      װ

                         1        6          15       20      15         6          1

                        …………

 

¨        Développement de Newton

On montre que quels que soient a, b réels, et

ou

 

Exemples :

 

Application : Nombre des parties d’un ensemble

Soit E un ensemble à n éléments

Le nombre de parties à 0 élément est

                                         1 élément est 

                                         2 éléments est

                                                …..

                                          p éléments est

                                               ……

                                          n éléments est

 

Le nombre des parties de E est égal à

 

 

III - DENOMBREMENT D’APPLICATIONS :

Soit f une application d’un ensemble  vers un ensemble F.

f est parfaitement définie par la donnée de

A chaque application f de E vers F correspond donc un et un seul p-uplets  d’éléments de E. Et réciproquement à chaque p-uplets  d'éléments de F correspond une et une seule application f (qui est définie par ).

Le nombre d'applications de E vers F est donc égal au nombre de p-uplets d'éléments de F

Si , le nombre de p-uplets éléments de F est . D'où :

 

             Théorème :

Le nombre d’application d’un ensemble à p éléments vers un ensemble à n éléments est np

 

Le p-uplets correspondant à une injection est formé de p éléments  2 à 2 distincts donc c’est un arrangement de p éléments de F

            Théorème :

Le nombre d’injection d’un ensemble à p éléments dans un ensemble à n éléments (avec ) est égal au nombre d’arrangements de p éléments pris parmi n.

 

Puisque si , et où  est injective, alors f est bijective, on a, le nombre de bijection de E vers F avec

            Théorème :

Le nombre du bijections d’un ensemble à n éléments vers un ensemble à n éléments est égal au nombre d’arrangements de n éléments pris parmi n, donc au nombre de permutation de n éléments .