Philippe.Dumas@inria.fr


http://algo.inria.fr/dumas/Maple/

Retour en page principale Table des matières Index

Maple V.4 worksheet Maple V.5 worksheet

Nous allons procéder en plusieurs étapes. Parcourir les parties à k éléments constituées d'entiers pris entre m et n est un exercice de programmation intéressant en lui-même. Pour fixer les idées nous choisissons les valeurs suivantes des paramètres.

> m:=1:

  n:=8:

  k:=6:

Ensuite nous écrivons une séquence d'instructions qui va nous fournir un parcours possible. Les lignes marquées d'un dièse vont provoquer la sortie qui suit ; elles sont utiles pour l'explication mais disparaitront ensuite. La séquence d'instructions en question est répétée ce qui n'est pas satisfaisant du point de vue de la programmation (c'est une source d'erreurs) mais cela n'est pas trop grave car nous allons bientôt nous en débarrasser.

> for l to k do z[l]:=m+l-1 od:

  s:={seq(z[l],l=1..k)}:

  for x from m to n do                            #

    if member(x,s) then Symbol[x]:=`-o-`          #

    else Symbol[x]:=`---`                         #

    fi;                                           #

    printf("%3s",Symbol[x])                       #

  od:                                             #

  #printf("\n");                                  #

  while z[1]<n-k+1 do

    if z[k]<n then z[k]:=z[k]+1

    else 

      for j from 1 to k-1 while z[k-j]=z[k-j+1]-1 do od:

      if j<k then z[k-j]:=z[k-j]+1;

        for l from 0 to j-1 do z[k-l]:=z[k-j]+j-l od

      fi

    fi;

    s:={seq(z[l],l=1..k)};

    for x from m to n do                          #

      if member(x,s) then Symbol[x]:=`-o-`        #

      else Symbol[x]:=`---`                       #

      fi;                                         #

      printf("%3s",Symbol[x])                     #

    od:                                           #

    printf("\n");                                 #

  od:

-o--o--o--o--o--o-------

-o--o--o--o--o-----o----

-o--o--o--o--o--------o-

-o--o--o--o-----o--o----

-o--o--o--o-----o-----o-

-o--o--o--o--------o--o-

-o--o--o-----o--o--o----

-o--o--o-----o--o-----o-

-o--o--o-----o-----o--o-

-o--o--o--------o--o--o-

-o--o-----o--o--o--o----

-o--o-----o--o--o-----o-

-o--o-----o--o-----o--o-

-o--o-----o-----o--o--o-

-o--o--------o--o--o--o-

-o-----o--o--o--o--o----

-o-----o--o--o--o-----o-

-o-----o--o--o-----o--o-

-o-----o--o-----o--o--o-

-o-----o-----o--o--o--o-

-o--------o--o--o--o--o-

----o--o--o--o--o--o----

----o--o--o--o--o-----o-

----o--o--o--o-----o--o-

----o--o--o-----o--o--o-

----o--o-----o--o--o--o-

----o-----o--o--o--o--o-

-------o--o--o--o--o--o-

Nous voyons une partie à k éléments comme un ensemble de k perles enfilées sur un fil et les positions possibles des perles sont les entiers entre m et n. Au départ toutes les perles sont calées à gauche et nous les poussons petit à petit vers la droite. Dans la dernière position elles sont calées à droite. Notre but est de faire apparaître les parties dans l'ordre lexicographique. L'algorithme est le suivant : la perle la plus à droite est poussée d'un cran vers la droite à chaque pas de l'algorithme ; quand elle bute sur l'extrémité droite, nous décalons d'un cran vers la droite la perle qui la précède et nous ramenons celle qui a buté sur l'extrémité droite juste à droite de cette perle qui la précède; si jamais il n'est pas possible de bouger la perle qui précède celle qui est la plus à droite, alors nous reculons vers la gauche pour chercher la première perle (c'est-à-dire la plus à droite possible) que nous pouvons décaler vers la droite. Nous procédons ainsi jusqu'à ce qu'aucun perle ne puisse plus être décalée vers la droite. C'est ce que nous avons programmé dans la séquence d'instructions précédente. Il existe d'autres approches de la question ; on pourra là dessus consulter [NiWi78]

Nous arrivons ainsi à la procédure qui suit. Dans l'exercice on demande de calculer une somme d'inverses de produits ; au lieu de fournir les parties à k éléments, nous calculons donc ces produits de k termes. Cependant nous voulons vérifier la correction de la procédure; nous utilisons donc des indéterminées plutôt que des valeurs numériques. Il suffira de remplacer ensuite tous les i[z[index]] par les z[index] pour approcher de la solution demandée.

> setwalk:=proc(k::posint,n::integer)

    local p,l,i,z,S,j;

    p:=1;

    for l to k do z[l]:=l od:

    p:=mul(i[z[l]],l=1..k);

    S:=1/p;

    while z[1]<n-k+1 do

      if z[k]<n then 

         z[k]:=z[k]+1

      else 

        for j from 1 to k-1 while z[k-j]=z[k-j+1]-1 do od:

        if j<k then z[k-j]:=z[k-j]+1;

           for l from 0 to j-1 do 

             z[k-l]:=z[k-j]+j-l

           od

        fi

      fi;   

      p:=mul(i[z[l]],l=1..k);

      S:=S+1/p

    od:

    S

  end:

Testons la procédure sur un petit exemple.

> setwalk(2,5);

Notons que le résultat obtenu n'est rien d'autre qu'une fonction symétrique élémentaire des 1/i[l]. On pouvait donc faire apparaître la même quantité comme suit.

> N:=5:

> collect(mul(X-1/i[l],l=1..N),X,expand);

Tout cela est fort bien, mais nous n'avons pas respecté l'énoncé. En effet le calcul précédent répondrait à la question si les inégalités qui figurent dans l'indexation de la somme étaient larges, mais elles sont strictes. Le problème n'est pas de parcourir les ensembles à k éléments mais les multi-ensembles à k éléments ou encore, en bon français, les combinaisons avec répétitions de k éléments. Il faut donc reprendre la procédure et la modifier en conséquence. On obtient la nouvelle procédure que voici.

> multisetwalk:=proc(k::posint,n::integer)

    local p,l,i,z,S,j;

    p:=1;

    for l to k do z[l]:=1 od:

    p:=mul(i[z[l]],l=1..k);

    S:=1/p;

    while z[1]<n do

      if z[k]<n then 

         z[k]:=z[k]+1

      else 

        for j from 1 to k while z[k-j]=n do od:

          if j<k then z[k-j]:=z[k-j]+1;

            for l from 0 to j-1 do 

              z[k-l]:=z[k-j]

            od

          fi

      fi;   

      p:=mul(i[z[l]],l=1..k);

      S:=S+1/p

    od:

    S

  end:

> multisetwalk(3,3);

Ceci dit, il existe une autre façon de procéder. En effet un argument classique pour dénombrer les combinaisons avec répétitions de k éléments pris dans n consiste à remarquer qu'il existe une bijection entre l'ensemble de ces combinaisons avec répétitions et l'ensemble des combinaisons de k éléments pris dans n+k-1. Si la combinaison s'ordonne en x_1 < x_2 < ... < x_k et la combinaison avec répétitions s'ordonne en y_1 <= y_2 <= ... <= y_k, alors les deux sont liées par les formules y_1=x_1, y_2=x_2-1, ..., y_k=x_k-k+1. Il suffit donc d'une légère modification pour obtenir une procédure qui réponde à la question.

> smartmultisetwalk:=proc(k::posint,nn::integer)

    local n,p,l,i,z,S,j;

    n:=nn+k-1;

    p:=1;

    for l to k do z[l]:=l od:

    p:=mul(i[z[l]-l+1],l=1..k);

    S:=1/p;

    while z[1]<n-k+1 do

      if z[k]<n then 

         z[k]:=z[k]+1

      else 

        for j from 1 to k-1 while z[k-j]=z[k-j+1]-1 do od:

        if j<k then z[k-j]:=z[k-j]+1;

           for l from 0 to j-1 do 

             z[k-l]:=z[k-j]+j-l

           od

        fi

      fi;   

      p:=mul(i[z[l]-l+1],l=1..k);

      S:=S+1/p

    od:

    S

  end:

> smartmultisetwalk(3,3);

Retour en page principale