Arrangements de k éléments différents pris parmi {1, 2, ..., n}

On peut définir les arrangements de n éléments pris k à k ou encore les arrangements de k éléments parmi n éléments de diverses manières :

Un arrangement est une application injective de E = {1, 2, ..., k} vers un ensemble F de cardinal n (on peut prendre F = {1, 2, ..., n}).
Un arrangement est une suite finie (x₁, x₂, x₃, ..., x_n) de k éléments x_i tous différents pris dans l'ensemble F
Un arrangement est un mot de k lettres toutes différentes de l'alphabet F de n lettres

La figure de droite montre une injection de l'ensemble E = {1, 2, 3} vers l'ensemble F = {1, 2, 3, 4, 5, 6} et correspond donc à un arrangement de 3 éléments de F. On pourra écrire cet arrangement sous la forme d'une suite finie (3, 6, 2).

Lorsque k = n, les arrangements de n éléments de F sont les permutations de F.

Le nombre d'arrangements de k éléemnt d'un ensemble F de n éléments est A_kⁿ = n(n-1)(n-2)...(n-k+1) = n! / (n-k)!
Lorsque k = n, on a A_nⁿ = P_n = n! (n! se lit factorielle n et est le nombre de permutations de F).

Ne pas confondre les arrangements et les combinaisons, par exemple :
à une seule combinaison (un ensemble) {2, 3, 5} de trois éléments correspond six arrangements différents (2, 3, 5), (2, 5, 3), (3, 2, 5), (3, 5, 2), (5, 2, 3), (5, 3, 2).
Une combinaison de k éléments d'un ensemble F de n éléments est un ssous-ensemble de k éléments de F.
Le nombre A_kⁿ d'arrangements de k éléments parmi n est donc égal à k! fois le nombre de combinaisons de k éléments de F.

Arrangements

Arrangements de k = éléments parmi n = éléments.

Le nombre de ces arrangements est

ex. 1,   ex. 2,   ex. 3,   ex. 4,   ex. 5,   ex. 6,   ex. 7,   ex. 8,   ex. 9,   ex. 10,   ex. 11,   ex. 12,  

fonction arrangements(Liste L, Liste F, k) {
   si k est égal à 0, {
        afficher  L
   } sinon {
        pour tous les éléments x de l'ensemble F  {
             Liste G = F moins x 
                         (F auquel on a ôté l'élément x)
             Liste L2  = L plus x  
                         (on a concaténé x à la droite de la liste L)
             arrangements(L2, G , k-1)
        }
}

arrangements("", (1,2,3,4,5,6), 3);

Un programme écrit en C calculant tous les arrangements dans un tableau d'entiers de taille Anp × p pour qu'on puisse en faire ce qu'on veut ensuite. Toutefois, si c'est juste pour afficher les arrangements ou les envoyer à un autre programme, au fur et à mesure de leur création, le programme simplifié arrgt2.c suffira.
exemple :

       aven:~/arr\> arrgt 4 3
       (1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 4), (1, 4, 2), (1, 4, 3), 
       (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), (2, 4, 1), (2, 4, 3), 
       (3, 1, 2), (3, 1, 4), (3, 2, 1), (3, 2, 4), (3, 4, 1), (3, 4, 2),
       (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2),
       aven:~/arr\>

(Ar) rangement mathématique