COMBINAISONS AVEC RÉPÉTITIONS

                                                           TS  FUTUR  PROGRAMME SEPT; 2020

                            Thème:   COMBINAISONS AVEC RÉPÉTITIONS

                             • Soit p et n deux entiers naturels non nuls.

                                  Une combinaison avec répétition d'ordre p  d'éléments d'un ensemble E ,

                                 de n  éléments,  est une disposition  non ordonnée de p éléments

                                 pas forcément distincts de  E.

                             • EXEMPLE.

                                    Soit l'ensemble E = { a , b , c } .

                                  Les combinaisons avec répétion, d'ordre 2 ,  d'éléments de E sont :

                                   les dispositions non ordonnées de deux éléments pas forcément disticts de E.

                                   Ici on obtient :

                                                 aa   ab   ac

                                                        bb   bc 

                                                                cc

                                     La notation ab est la même que ba.

                                     Ce ne sont pas des ensembles ni des couples.

                                     Parfois on prononce le mot de collection .

                                      Le nombre de ces combinaisons avec répétition est noté :

                                                          avec  n = 3 et  p = 2

                                            Il y a en a.

                                       On remarque que : 

                                  Cette formules  va être généralisée .                              

                      • Nombre de combinaisons avec répétition d'ordre p d'éléments

                        d'un ensemble E de n éléments  avec p et n deux entiers naturels non nuls.

                         Le cas où p = 1 n'a pas d'intérêt car alors on a les n singletons formés chacun d'un

                          élément de E.     

                   • Justification ludique possible de la formule.                    

           On va coder la situation, en utilisant un parallélisme de situation ( en fait une bijection

           entre deux ensembles finis de même cardinal ), de façon à se ramener à un problème

          de comptage plus simple des éléments d'un ensemble plus accessible .

          Nous disposons d'un ensemble E de n éléments distincts. ( n dans IN* )

          E = { x₁, x₂, ..., x_n }   décrit ici en extension.

          Une combinaison d'ordre p avec répétition d'éléments de E , comprend  p éléments

         de E, sans ordre, pas forcément différents.

         On va lui associer  une unique permutation avec répétition des n + p – 1  boules 

         d'une urne qui contient  n – 1 boules noires et  p boules blanche.

            Une telle permutation avec répétition des n − 1 + p boules de l'urne ici pour n= 4 

               et p = 7   est par exemple 

           Une combinaison d'ordre 7 avec répétition d'éléments de E est,  pour p = 7 ,par exemple

               x₁    x₁   x₃    x₄   x₄   x₄   x₄

        De la sorte, le nombre de ces combinaisons d'ordre p avec répétition va être égal à celui

        des permutations avec répétitions des n + p – 1 boules de l'urne,

        c'est-àdire comb( n + p – 1 , p ).

        D'où la justification de 

      Détaillons ce codage qui permet cette démarche.

      • • • Soit  une combinaison d'ordre p d'éléménts de E.

              On dispose ses termes du plus petit indice au plus grand

              pour la lecture bien qu'il n'y ait pas d'ordre.

             ♦  Soit x_i   son premier terme       1 ≤ i   ≤​ x_n

               Son indice dans E est i.

                On considère    i − 1 

                On met i − 1  boules noires à gauche de la première boule blanche dans 

                le la grille de n + p  − 1 cases.

                Si  i − 1  = 0 alors on met seulement en premier une boule blanche

              ♦  Soit x_j    son  second  terme   avec     1 ≤ j   ≤​ x_n  

                   Son indice dans E est j

                   On considère j − 1 

                   On met autant de boules noires que nécessaire pour avoir 

                  j − 1  boules noires à gauche de la nouvelle boule blanche.

                 ( Attention en comptant celles déjà mises.

                      Donc s'il y a déjà k boules noires placées,

                      il faut n'ajouter que  j − 1  − k boules noires avant de mettre la seconde 

                      boule blanche. )

              ♦  Ainsi de suite,  pour les autres termes de la combinaison.

                  On remplit ainsi les   n + p – 1 cases de p boules blanches et  n – 1 boules noires .

         • • •     EXEMPLE CONCRET :

                  Soit   E = { x₁, x₂,x ₃ ,  x₄ }                 n = 4   

                  Soit p = 7                      n – 1 = 3          n + p – 1 = 10

             #  Premier aspect 

                  Considérons la combinaison d'ordre 7  avec répétition :

                   x₁    x₁   x₃    x₄   x₄   x₄   x₄   

                Soit la grille vide de 10 cases à remplir 

                 pour avoir une permutation avec répétition des 10 boules de l'urne

                 dont 7 blanches et 3 noires

                   ♦  x₁   est d'indice 1  dans E.

                      1 − 1 = 0

                      Aucune boule noire à mettre à gauche de la première boule blanche.

                     Donc

                    ♦ Le terme suivant est encore x₁   d'indice 1  dans E.

                      1 − 1 =   0  

                      Aucune  boule noire à mettre à gauche de la  seconde boule blanche.

                       Donc

                    ♦ Le terme suivant est  x₃   d'indice 3  dans E.

                             3  − 1 = 2 

                       Avant de placer la troisième boule blanche on doit veiller à avoir 2 boules noires 

                      au total à sa gauche.

                      On ajoute donc ici deux boules noires puis une boule blanche

                       car il n'y a encore auncune boule noire.

                       ♦ Le terme suivant est  x₄   d'indice 4  dans E.

                           4  − 1 =  3  

                            Nous devons avoir 3  boules noires à gauche de la quatrième boule blanche.

                            Il y a déjà deux boules noires .

                          Donc on ne rajoute qu' une boule noire avant de mettre la quatrième boule blanche.

                           ♦ Les trois  termes suivants sont des  x₄   d'indice 4  dans E.

                                   4  − 1 =  3

                             Comme il y a déjà trois boules noires à gauche des boules blanches à placer

                             il n'y a qu'à mettre directement  les trois boules blanches .

                              On obtient l'unique permutation avec répétition des 

                              10 boules de l'urne:

             #   Réciproquement :   

                     Soit 

                                 la permutation avec répétition des boules de l'urne.

                  ♦ Il y a 0 boule noire à gauche de la première boule blanche.

                       0 + 1 = 1

                      On a le premier terme de la combinaison d'ordre 7

                      qui est d'indice 1 dans E

                        Donc :  x₁ 

                  ♦ Il y a 0 boule noire à gauche de la seconde  boule blanche.

                        0 + 1 = 1

                        On a le second  terme, de la combinaison d'ordre 7 avec répétition ,

                         qui est d'indice 1 dans E.

                         C'est   x₁

                        Donc :      x₁   x₁ 

                    ♦  Il y a 2 boules noires à gauche de la troisième  boule blanche.

                                     2 + 1 = 3

                                  On a le troisième  terme, de la combinaison d'ordre 7 avec répétition ,

                                 qui est d'indice 3 dans E.

                                        C'est   x₃ 

                                   Donc :      x₁   x₁    x₃  

                          ♦  Il y a 3 boules noires à gauche de la quatrième boule blanche

                              3 + 1 = 4

                           On a le quatrième terme, de la combinaison d'ordre 7 avec répétition ,

                            qui est d'indice 4 dans E.

                                   C'est   x₄   

                                        Donc :      x₁   x₁    x₃     x₄

                          ♦   Les trois boules blanches suivantes  ont chacune  trois boules noires à gauche.

                                        3 + 1 = 4

                              Donc les trois derniers termes de la combinaison d'ordre 7 avec répétition

                                  sont des   x₄   

                            Finalement la combinaison d'ordre 7 avec répétition  est:

                                                x₁   x₁    x₃     x₄     x₄     x₄     x₄   

-------------------------------------------------------------------------------------------------------------------------

   EXERCICE 0:

           Soit  E = [ a , b, c }     n = 3

          On note 

            le nombre de combinaison d'ordre p avec répétition d'éléments de E.    ( p entier non nul )

        1.  Faire deux tableaux à double entrée pour avoir celui des combinaisons d'ordre p

         avec répétition d'éléments de E , quand p = 3 et quand p = 4.

       2. Quand on ajoute un terme a pour toutes les combinaison d'ordre 3 d'éléments de E,

           obtient-on les combinaisons  d'ordre 4 avec répétion d'éléments de E, qui ont

           au moins  un terme a  ?

       3. On revient au cas général.

            E = { x₁ , x₂ , ...... , x_n }    n dans IN*      p dans IN − { 0 , 1 }

           On décide de faire  l'inventaire de tous les termes de toutes les combinaisons d'ordre p  avec répétition

           d'éléments de E .

         a ) Que représente :

                           ?

         b ) A-t-on autant de termes x₁ , que x₂ ,   ....... ou que x_n  dans  cet inventaire ?

         c) Que représente :  

                          ?

          d ) Montrer que : 

                 En déduire : 

             en fonction  de 

                   .

          e ) Qu'obtiendrait-on pour la  valeur de 

            si l'on avait 

 -----------------------------------------------------------------------------------------------------------------

     EXERCICE 1

                 Soit n un entier naturel non nul fixé.

                 Montrer par récurrence sur IN* − { 1} , la formule précédente  avec la variable p.

                   ( Commencer la récurrence à p = 2 )                                          

------------------------------------------------------------------------------------------------------