INFO COMBINAISONS AVEC RÉPÉTITIONS

                          INFO    EXERCICES SUR LES COMBINAISONS AVEC RÉPÉTITIONS   

         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 

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

        REPONSE:

          Cet exercice est une aide pour l'exercice  suivant ..

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

             avec répétition.

    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  ?

              OUI.

     3. a ) Que représente :

                           ?

         C'est le nombre de termes qui figurent dans la totalité des combinaisons d'ordre

          p avec répétition.

            En effet 

             Si l'on fait l'inventaire de tous les termes des  combinaisons d'ordre p avec répétition

            d'éléments de E, comme chacune  contient p termes,

            cela fait :

                     termes

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

              OUI.

           En effet,  tous les termes x₁ , x₂ ,   ....... ,x_n  jouent le même rôle.

           c) Que représente :  

                          ?

          C'est le nombre de termes x1  , c'est aussi le nombre de terme x2 ,  ....etc.

           dans l'inventaires des    combinaisons  d'ordre p avec répétition d'éléments de E.

           En effet:

          On dispose de n termes possibles,  x₁ , x₂ ,   ....... ,xn  , et chacun apparait un  même nombre de fois.

         Donc on doit diviser     par n   pour avoir le nombre d'apparitions  de chacun .   

         d ) Montrer que : 

                 En déduire :                en fonction de      .

         On peut dire que l' on peut, pour de raisons de symétrie,  raisonner avec seulement le terme  x₁ 

         Par un raisonnement analogue on obtiendra le même résultat pour les autres termes

              x ₂ , ..... , x_n   .

             Imaginons que l'on ajoute à chacune des

                       combinaisons d'ordre p avec répétition,  un terme  x₁  .

           On obtient alors  toutes les combinaisons d'ordre p + 1 avec répétition 

              d'éléments de E , où il y figure au moins un   x₁  .

             Chacune de celles- ci est obtenue en juxtaposant un x₁ à  une combinaison

              d'ordre p avec répétition  d'éléments de E.  

         •   Donc,  il y a autant de ces combinaisons  d'ordre p + 1 avec répétition 

              d'éléments de E , où il y a au moins un  x₁  qu'il  y a de  combinaisons 

              d'ordre p avec répétition  d'éléments de E ,   soit    .

         •    Ainsi     il y a  au total       termes x₁   qui ont été rajoutés à ceux 

               de  l'inventaire des termes  x₁  des    combinaisons d'ordre p  avec répétition 

              d'éléments de E .

           •  Mais on sait aussi , qu'il y a  déjà  _​   termes x1  dans cet  l'inventaire des termes  x₁  des   

              combinaisons d'ordre p  avec répétition  d'éléments de E.

           •   Ainsi en sommant ces deux nombres       et       on obtient

             le nombre de x₁ dans l'inventaire des   combinaisons d'ordre p + 1 avec  répétition 

            d'éléménts de E.

         •   Or  le nombre de termes x₁ dans les   combinaisons d'ordre p + 1 avec  répétition 

             d'éléments de E      est   

         •    D'où l'égalité: 

       On en déduit :

              e) :

    e ) Qu'obtiendrait-on pour la  valeur de 

            si l'on avait   

            On peut dire :

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

     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 )                                          

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

     REPONSE:

       Ce sont plus les notations que les idées qui ici sont délicates.

         Soit n un entier naturel non nul fixé.

            Effectuons une récurrence sur IN*− {1}   avec comme variable p pour établir 

             la formule :

       • p = 2

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

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

          On a, comme combinaisons d'ordre p avec répétition d'éléments de E:

           x₁ x₁     x₁ x₂       ..............................    x₁, x_n               ( il y en a  n sur cette ligne )

                         x₂  x₂     .................................. x₂  x_n                ( il y en a   n − 1  sur cette ligne )

                                                   ......................

                                                                           x_n x_n                ( il y en a   1  sur cette ligne )

         Donc, il y en a: 

            car c'est la somme des n premiers termes de la suite arithmétique de raison 1

            et de premier terme 1.

            D'autre part ici :

               Ainsi on a bien : 

         La formule est vraie pour p = 2

        • Soit p dans IN − { 0 , 1 } quelconque.

                Montrons que si 

                 alors :

           L'établissement nécessaire d'abord de la relation

            est identique à celle de l'exercice préparatoire précédent.

             On peut donc reprendre la démarche de  l'exercice précédent.:

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

         •  On dispose toujours de n éléments    x₁, x₂, ..., x_n   de E.         

             Si l'on fait l'inventaire de tous les termes des

             combinaisons d'ordre p avec répétition , comme chacune en contient p ,

            cela fait :

                     termes en tout

             Mais aucun terme n'étant privilégié il y a autant de 

              x₁ que de x₂   ou que de  x₃ ....     ou que de  x_n    .

              Il suffit donc de diviser par n  pour savoir combien il y en a de chacun.

            Ainsi il y  a ;

                 termes  x1   

                 termes  x2   

                .......................................

                termes  x_n 

            On peut pour de raisons de symétrie raisonner avec seulement le terme   x₁ 

             Par un raisonnement analogue on obtiendra le même résultat pour les autres termes

              x ₂ , ..... , x_n   .

             Imaginons que l'on ajoute à chacune des

                       combinaisons d'ordre p avec répétition,  un terme  x₁  .

             On obtient ainsi toutes les combinaisons d'ordre p + 1 avec répétition 

              d'éléments de E , où il y a au moins un   x₁  .

             Chacune de celles ci est obtenue en juxtaposant un x₁ à  une combinaison

              d'ordre p avec répétition  d'éléments de E.  

         •   Donc,  il y a autant de ces combinaisons  d'ordre p + 1 avec répétition 

              d'éléments de E , où il y a au moins un   x₁  qu'il  y a de  combinaisons 

              d'ordre p avec répétition  d'éléments de E ,   soit    .

         •    Ainsi     il y a  au total       termes x₁   qui ont été rajoutés à ceux 

               de  l'inventaire des termes  x₁  des    combinaisons d'ordre p  avec répétition 

              d'éléments de E .

           •  Mais on sait aussi , qu'il y a  déjà  _​   termes x₁  dans cet  l'inventaire des termes  x1  des   

              combinaisons d'ordre p  avec répétition  d'éléments de E.

           •   Ainsi en sommant ces deux nombres       et      on obtient

             le nombre de x₁ dans l'inventaire des   combinaisons d'ordre p + 1 avec  répétition 

            d'éléménts de E.

         •   Or  le nombre de termes x₁ dans les   combinaisons d'ordre p + 1 avec  répétition 

                   est   

         •    D'où l'égalité: 

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

        On peut alors continuer  notre récurrence :.

         On déduit :

        Mais on sait que :

           Donc :

      Conclusion: La formule est établie sur IN* −{ 1 }.

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