Accueil / Combinatoire / Combinatoire Permutations / Arrangements

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

Présentation

Définition

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 (x1, x2, x3, ..., xn) de k éléments xi tous différents pris dans l'ensemble F
application injective Un arrangement est un mot de k lettres toutes différentes de l'alphabet F de n lettres

Exemple

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).

Propriétés immédiates et remarques

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 Akn = n(n-1)(n-2)...(n-k+1) = n! / (n-k)!
Lorsque k = n, on a Ann = Pn = 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 Akn d'arrangements de k éléments parmi n est donc égal à k! fois le nombre de combinaisons de k éléments de F.

Recherche des arrangements

Application

Arrangements


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

en les choisissant dans l'ensemble

Le nombre de ces arrangements est


Exemples

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

Algorithme utilisé

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\>

arrangement
(Ar) rangement mathématique




D'autres pages sont consacrées aux nombres de permutations, combinaisons et arrangements aux nombres de Catalan ainsi qu'à d'autres suites de nombres entiers naturels

Accueil / Combinatoire / Combinatoire Permutations / Arrangements

















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014