Permutations d’un ensemble fini

Section I - Opérations sur les permutations

Question 1 - Création de la permutation identité

Pour créer la permutation identité dans Sn, nous formons un tableau P de taille n et affectons à chaque composante k la valeur k.

identp:=proc(n::integer)
  local P,k;
  P:=array(1..n);
  for k to n do P[k]:=k od;
  RETURN(eval(P))
end:

Question 2 - Création d'une permutation pseudo-aléatoire

On part de la permutation identité représentée par P = [1, 2, ..., n]. Ensuite, pour k allant de n à 2 (en ordre décroissant), on échange P[k] avec un élément P[j] où j est choisi aléatoirement dans l'intervalle [1, k]. Une version plus large de la syntaxe rand permet d'obtenir un entier aléatoire directement dans un intervalle.

randp:=proc(n::integer)
  local P,j,k,t: 
  P:=identp(n);
  for k from n to 2 by -1 do
    j:=1+(rand()mod k);
    t:=P[k]; P[k]:=P[j]; P[j]:=t;
  od;
  RETURN(eval(P));
end:

Question 3 - Composition de deux permutations

Le résultat t = q ◦ p est représenté par un tableau T de taille n. Pour chaque entier k de {1, ..., n}, on a t(k) = q(p(k)), ce qui se traduit par T[k] = Q[P[k]].

comp:=proc(Q::array(integer),P::array(integer),n::integer)
  local T,k;
  T:=array(1..n);
  for k to n do T[k]:=Q[P[k]] od;
  RETURN(eval(T));
end:

Question 4 - Puissance m-ième d'une permutation

L'algorithme d'exponentiation rapide repose sur l'écriture binaire de l'exposant m = Σ (b_j × 2^j). On calcule les carrés successifs et on compose le résultat pour les termes où b_j = 1.

Solution itérative :

powp:=proc(P::array(integer),n::integer,m::integer)
  local Q,T,k;
  Q:=identp(n);
  k:=m; T:=copy(P);
  while k>0 do
    if k mod 2 = 1 then
      Q:=comp(Q,T,n)
    fi;
    T:=comp(T,T,n);
    k:=floor(k/2);
  od;
  RETURN(eval(Q));
end:

Solution récursive : Pour calculer q = p^m, on calcule t = p^k où k = quotient(m, 2). Puis on élève t au carré. Si l'exposant m est impair, on multiplie le résultat par p.

powpr:=proc(P::array(integer),n::integer,m::integer)
  local Q;
  if m=0 then RETURN(identp(n))
  else
    Q:=powpr(P,n,iquo(m,2));
    Q:=comp(Q,Q,n);
    if type(m,odd) then
      Q:=comp(P,Q,n)
    fi;
    RETURN(eval(Q));
  fi
end:

Question 5 - Inverse d'une permutation

Soit Q = [q(1), q(2), ..., q(n)] le tableau associé à q = p^(-1). Pour tout k, q(p(k)) = k, donc on affecte Q[P[k]] := k.

invp:=proc(P::array(integer),n::integer)
  local Q,k;
  Q:=array(1..n);
  for k to n do Q[P[k]]:=k od;
  RETURN(eval(Q));
end:

Section II - Décomposition en cycles disjoints

Question 1 - Inversion sur place

Cette procédure parcourt les cycles de la permutation et les inverse un par un sans utiliser de tableau auxiliaire de taille n. Les éléments déjà traités ("taggués") reçoivent un signe négatif, qui est rétabli à la fin.

Invp:=proc(P::array(integer),n::integer)
  local i,j,k,t:
  for i to n do
    j:=i; k:=P[j];
    while P[i]>0 do
      t:=P[k];
      P[k]:=-j;
      j:=k;
      k:=t
    od;
    P[i]:=-P[i];
  od;
  RETURN();
end:

Question 2 - Décomposition en forme C

La procédure transforme la forme T d'une permutation en sa forme C, marquant la fin de chaque cycle par un nombre négatif.

Decomp:=proc(P::array(integer),n::integer)
  local Q,i,j,k;
  Q:=copy(P);
  i:=0;
  for j to n do
    if Q[j]>0 then
      while Q[j]>0 do
        i:=i+1: P[i]:=j;
        k:=Q[j];
        Q[P[i]]:=0;
        j:=k;
      od;
      P[i]:=-P[i]
    fi;
  od;
  RETURN()
end:

Note sur le code : la version de l'énoncé contient une légère anomalie dans la boucle while (indice j modifiant l'indice de la boucle for). Le fonctionnement est garanti par le fait que l'indice de boucle explore un cycle pour revenir à sa valeur.

Question 3 - Recomposition de la forme C en forme T

La procédure utilise un tableau copié Q. On parcourt Q et on construit le tableau P avec les valeurs absolues de Q, gérant la fermeture du cycle grâce à une mémorisation du début de cycle dans d.

Recomp:=proc(P::array(integer),n::integer)
  local Q,j,d;
  Q:=copy(P);
  for j to n do
    d:=Q[j];
    while Q[j]>0 do
      P[Q[j]]:=abs(Q[j+1]);
      j:=j+1;
    od;
    P[abs(Q[j])]:=abs(d);
  od;
  RETURN()
end:

Question 4 - Calcul de la signature

Méthode naïve (forme usuelle T) : On compte les inversions et on change le signe à chaque inversion trouvée.

signat:=proc(P::array(integer), n::integer)
  local s,i,j;
  s:=1;
  for i to n-1 do
    for j from i+1 to n do 
      if P[j]<P[i] then s:=-s; fi;
    od
  od;
  RETURN(s);
end:

Méthode avec forme C : Le nombre de cycles (incluant les points fixes) est égal au nombre de coefficients négatifs.

signatc:=proc(P::array(integer), n::integer)
  local s,i;
  s:=(-1)^n;
  for i to n do
    if P[i]<0 then s:=-s; fi;
  od;
  RETURN(s);
end:

Question 5 - Ordre d'une permutation

L'ordre est le PPCM des longueurs des cycles.

pgcd:=proc(a::integer, b::integer)
  if b=0 then RETURN(a)
  else RETURN(pgcd(b, a mod b))
  fi
end:

ordre:=proc(P::array(integer),n::integer)
  local i,j,m;
  m:=1;
  i:=1;
  while i<=n do
    j:=i;
    while P[i]>0 do i:=i+1 od;
    m:=m/pgcd(m,i-j+1) * (i-j+1);
    i:=i+1;
  od;
  RETURN(m);
end:

Note : Le PPCM de A et B se calcule par (A × B) / PGCD(A, B).

Question 6 - Puissance quelconque via cycles

En décomposant p, il suffit de décaler chaque élément à l'intérieur de son cycle de m positions (modulo la longueur du cycle).

Powp:=proc(P::array(integer),n::integer,m::integer)
  local Q,i,j,k,t;
  Q:=copy(P);
  Decomp(Q,n);
  i:=1;
  while i<=n do
    j:=i;
    while Q[i]>0 do i:=i+1 od;
    Q[i]:=-Q[i];
    t:=i-j+1;
    for k from 0 to t-1 do
      P[Q[j+k]]:=Q[j+((k+m)mod t)]
    od;
    i:=i+1;
  od;
  RETURN();
end:

Section III - Génération lexicographique de permutations

Question 1 - Passage à la permutation suivante

Cette procédure trouve le plus grand indice i tel que p(i) < p(i+1), puis le plus grand indice j tel que p(j) > p(i), échange p(i) et p(j), et inverse l'ordre des éléments restants pour obtenir la permutation suivante dans l'ordre lexicographique.

Nextp:=proc(P::array(integer),n::integer)
  local i,j,t;
  i:=n-1;
  while (i>0) and (P[i]>P[i+1]) do i:=i-1 od;
  if i>0 then
    j:=n;
    while P[j]<P[i] do j:=j-1 od;
    t:=P[i]; P[i]:=P[j]; P[j]:=t;
    i:=i+1; j:=n;
    while i<j do
      t:=P[i]; P[i]:=P[j]; P[j]:=t; 
      i:=i+1; j:=j-1;
    od;
  fi;
  RETURN();
end:

Question 2 - Liste des permutations

listp:=proc(P::array(integer),n::integer,k::integer)
  local T,Q,i,j;
  T:=array(1..k,1..n);
  Q:=copy(P);
  for i to k do
    for j to n do T[i,j]:=Q[j]; od;
    Nextp(Q,n);
  od;
  RETURN(eval(T));
end:

listallp:=proc(n::integer)
  RETURN(listp(identp(n),n,n!))
end:

Question 3 - Calcul du code de Lehmer

Le code c_i est le nombre de j > i tels que p(j) < p(i).

code:=proc(P::array(integer),n::integer)
  local C,i,j;
  C:=array(1..n);
  for i to n do
    C[i]:=0;
    for j from i+1 to n do 
      if P[j]<P[i] then
        C[i]:=C[i]+1
      end;
    od;
  od;
  RETURN(eval(C));
end:

Question 4 - Code de Lehmer sur place

Pour chaque i, on soustrait 1 à tout coefficient à droite qui est supérieur ou égal au coefficient en cours.

Code:=proc(P::array(integer),n::integer)
  local i,j,d;
  for i to n do
    d:=P[i];
    for j from i to n do
      if P[j]>=d then
        P[j]:=P[j]-1
      fi
    od
  od;
  RETURN()
end:

Question 5 - Décodage de Lehmer vers permutation

On inverse le processus par des remontées successives de droite à gauche.

Decode:=proc(P::array(integer),n::integer)
  local i,j;
  for i from n to 1 by -1 do 
    P[i]:=P[i]+1;
    for j from i+1 to n do
      if P[j]>=P[i] then
        P[j]:=P[j]+1
      fi
    od
  od;
  RETURN()
end:

Question 6 - Rang d'une permutation

Le rang est évalué par la somme rg(p) = Σ (c_k × (n-k)!) via le schéma de Horner.

rang:=proc(P::array(integer),n::integer)
  local r,k,C;
  C:=copy(P);
  Code(C,n);
  r:=0;
  for k to n do r:=(n+1-k)*r+C[k]; od;
  RETURN(r)
end:

Question 7 - Inversion et génération

L'application L associe une permutation à son code de Lehmer de manière strictement croissante vers l'ensemble Fn. De même, l'association du code de Lehmer au rang est strictement croissante vers {0, ..., n!-1}. L'application composée p ↦ rg(p) numérote donc bijectivement et en respectant l'ordre lexicographique les permutations de Sn.

gnar:=proc(n::integer,r::integer)
  local P,i,t;
  P:=array(1..n);
  t:=r;
  for i to n do
    P[n+1-i]:=irem(t,i);
    t:=iquo(t,i);
  od;
  Decode(P,n);
  RETURN(eval(P));
end:

randp:=proc(n::integer)
  RETURN(gnar(n,rand(n!)()));
end:

Section IV - Génération récursive de permutations

Question 1 - Affichage des éléments selon l'ordre lexicographique de l'inverse

La procédure place successivement les valeurs de 1 à n dans les positions disponibles, générant les permutations dans l'ordre croissant de p^(-1).

Printp:=proc(n::integer)
  local P,j,Pose;
  P:=array(1..n);
  for j to n do P[j]:=0 od; 
  
  Pose:=proc(m::integer)
    local k;
    for k to n do
      if P[k]=0 then
        P[k]:=m;
        if m=n then print(eval(P))
        else Pose(m+1)
        fi;
        P[k]:=0;
      fi;
    od;
  end;
  
  Pose(1);
  RETURN();
end:

Question 2 - Génération par échanges

a) Preuve de la bijection : Soit p un élément de Sn, et (σ, k) un élément de S_(n-1) × E_n. Si p = ϕ(σ, k) = σ ◦ τ_k, alors p(k) = σ(n) = n. Donc k = p^(-1)(n). Avec ce k, on a σ = p ◦ τ_k, et on vérifie que σ(n) = p(k) = n. L'application est donc bien injective, et, par égalité des cardinaux (n! pour Sn, (n-1)! × n pour S_(n-1) × E_n), c'est une bijection.

b) Procédure par échanges (Printp2) :

Swap:=proc(P::array,j::integer,k::integer)
  local t; t:=P[j]; P[j]:=P[k]; P[k]:=t; RETURN()
end:

Printp2:=proc(n::integer)
  local P,j,Go;
  P:=identp(n);
  
  Go:=proc(m::integer)
    local k,t;
    for k from m to 1 by -1 do 
      Swap(P,m,k);
      if m=2 then print(eval(P))
      else Go(m-1)
      fi;
      Swap(P,m,k);
    od;
  end;
  
  Go(n);
  RETURN();
end:

Section V - Permutations ayant un nombre donné de cycles

Question 1 - Nombres de Stirling de première espèce

a) Valeurs remarquables :

• [n, n] = 1 (seule l'identité a n cycles).
• [n, n-1] = n(n-1)/2 (correspond au nombre de transpositions, C(n, 2)).
• [n, 1] = (n-1)! (correspond au nombre de permutations circulaires).

b) Relation de récurrence : Considérons 1 < k < n. Les [n, k] permutations ayant k cycles se divisent en deux groupes :

• Celles dont n est un point fixe : le reste forme une permutation de S_(n-1) à k-1 cycles. Il y a [n-1, k-1] telles permutations.
• Celles où n n'est pas un point fixe : n s'insère dans un cycle d'une permutation de S_(n-1) ayant k cycles. Pour une telle permutation, n peut se placer à n-1 positions différentes (la somme des longueurs des cycles valant n-1). Cela donne (n-1) × [n-1, k] possibilités. On obtient la formule : [n, k] = [n-1, k-1] + (n-1)[n-1, k].

Question 2 - Calcul des coefficients de Stirling

stir:=proc(n::integer)
  local P,m,k:
  P:=array(1..n);
  P[1]:=1;
  for m from 2 to n do
    P[m]:=1;
    for k from m-1 to 2 by -1 do
      P[k]:=P[k-1]+(m-1)*P[k]
    od;
    P[1]:=(m-1)*P[1];
  od;
  RETURN(eval(P));
end:

Question 3 - Génération d'une permutation aléatoire à k cycles

La probabilité que n soit un point fixe est P = [n-1, k-1] / [n, k]. On s'appuie sur cette probabilité de manière récursive.

randc:=proc(n::integer,k::integer)
  local go,P;
  
  go:=proc(n::integer,k::integer) 
    local r,j,x;
    if k>1 then r:=stir(n-1)[k-1]/stir(n)[k]
    else r:=0
    fi;
    
    if 10^(-12)*rand()<r then 
      P:=go(n-1,k-1);
      P[n]:=n;
      if n=1 then RETURN(eval(P)) fi;
    else
      P:=go(n-1,k);
      j:=1+(rand()mod(n-1));
      Swap(P,n,j);
    fi;
    RETURN(eval(P))
  end;
  
  P:=array(1..n);
  go(n,k);
  RETURN(eval(P));
end:

Question 4 - Espérance du nombre de cycles

a) Polynôme de dénombrement : Pour n=1, f_1(x) = [1, 1]x = x. Supposons que f_(n-1)(x) = x(x+1)...(x+n-2). f_n(x) = Σ [n, k]x^k = x [n-1, n-1]x^(n-1) + Σ ([n-1, k-1] + (n-1)[n-1, k])x^k f_n(x) = x Σ [n-1, k]x^k + (n-1) Σ [n-1, k]x^k f_n(x) = (x + n - 1) f_(n-1)(x). Par récurrence, f_n(x) = x(x+1)...(x+n-1).

b) Espérance X_n : E(X_n) = (1/n!) Σ k [n, k] = (1/n!) f'_n(1). En dérivant f_n(x), on obtient que f'_n(1) / f_n(1) = Σ (1/k) pour k allant de 1 à n. Puisque f_n(1) = n!, on a E(X_n) = Σ (1/k). Un équivalent classique de la série harmonique donne E(X_n) ≈ ln(n) quand n → ∞.

Question 5 - Records dans un tableau

a) Valeur maximum :

maxi:=proc(P::array(integer),n::integer)
  local m,k:
  m:=P[1];
  for k from 2 to n do
    if P[k]>m then m:=P[k] fi;
  od;
  RETURN(m);
end:

b) Espérance mathématique du nombre de records : La source fournie est endommagée et s'interrompt brutalement au début de la réponse (« On a l --- END SOURCE --- »). Il est donc impossible de rédiger la suite de la solution sans inventer la fin de la démonstration, ce qui viole nos contraintes de résolution. La déduction est cependant intimement liée aux propriétés de l'arrangement des permutations vues plus haut (la distribution des records correspond à la construction des cycles par la méthode de décomposition usuelle).

Méthode

Pour aborder ce type de sujet mêlant théorie algébrique (groupe symétrique) et algorithmique, il est recommandé de suivre ces étapes :

1. Tracez l'état des tableaux sur un papier avec une permutation de petite taille (ex. n = 4 ou n = 5) pour visualiser les échanges et les inversions.
2. Identifiez clairement la différence entre les structures de données (forme standard T contre forme cyclique C) qui demandent des logiques de parcours différentes (lecture continue vs saut par adresse).
3. Lors de la transcription en code, soyez vigilant sur les effets de bords (fonctions pures avec copy versus procédures modifiant les données sur place via P[i] := ...).
4. Dans les parties probabilistes, reliez toujours la question combinatoire au dénombrement de structures connues (ici, les coefficients de Stirling via des schémas de récurrence) avant de passer à l'espérance ou au codage aléatoire.