Arrangement

Pour les articles homonymes, voir Arrangement (homonymie).

La notion d'arrangement est utilisée en probabilités, et notamment pour les dénombrements en analyse combinatoire.

En mathématiques, lorsque nous choisissons k objets parmi n objets et que l’ordre dans lequel les objets sont sélectionnés revêt une importance, nous pouvons les représenter par un k-uplet d'éléments distincts et on en constitue une liste ordonnée sans répétition possible, c'est-à-dire dans laquelle l'ordre des éléments est pris en compte (si l'on permute deux éléments de la liste, on a une liste différente, et un élément ne peut être présent qu'une seule fois).

Une telle liste ordonnée est appelée un arrangement. Le nombre d'arrangements que l'on peut faire est noté $A^k_n$ et vaut :

$A^k_n = n \left(n - 1\right) \left(n - 2\right) \cdots \left(n - k + 1\right)$

Cette formule peut se comprendre à l'aide d'un arbre des choix successifs, puisque le premier élément est choisi parmi n, le second parmi (n-1) ... et le dernier parmi (n-k+1). Avec la notation factorielle, où n! = 1×2×...n, cette formule devient

$A^k_n = \dfrac{n!}{(n-k)!}\quad\mbox{pour }k\leq n,$

pendant que $A^k_n=0$ pour $k > n$ (ce qui exprime le principe des tiroirs).

A^k_n est en fait le nombre d'injections que l'on peut faire d'un ensemble à k éléments vers un ensemble à n éléments. Le nombre d'arrangements est lié au coefficient binomial ${n \choose k}$ (anciennement $C^k_n$ ) par :

${n \choose k} = \dfrac{A^k_n}{k!}$

Exemple : À un examen, cinq candidats tirent les uns après les autres un sujet dans une urne contenant des questions toutes différentes. Le premier tirage se fera sur un ensemble de 50 questions possibles. À chaque tirage suivant, la question qui vient d'être tirée est enlevée de l'urne. Ainsi, en faisant passer les cinq candidats, le tirage se fait d'abord sur 50, puis sur 49, et ainsi de suite jusqu'à 46 qui représente l'ensemble des questions restantes dans l'urne pour le dernier tirage. L'arrangement va consister à additioner à chaque modification possible de cet ensemble de départ la nouvelle probabilité de piocher une question donnée. La solution pour cet exemple est donc un arrangement de 5 (k) à 50 (n).

Si on remettait la question tirée de nouveau dans l'urne à chaque tirage, ce serait un arrangement avec répétition de 5 (k) à 50 (n), et la solution vaudrait 50^5.

Exemples d'arrangements :

une phrase sans répétition de mot est un arrangement du dictionnaire ;
une association forme son bureau (président, trésorier, secrétaire) à partir des membres de l'association ; le bureau est un arrangement de l'association ;
le podium d'une course est un arrangement de l'ensemble des participants.

Définition mathématique

Définition

Soient E un ensemble fini de cardinal n et k un entier naturel. Un k-arrangement sans répétition de E est une application injective de {1, 2, ..., k} dans E.

Autre définition

Soient E un ensemble fini de cardinal n et k un entier naturel. Un k-arrangement de E (ou k-arrangement sans répétition de E, ou encore arrangement sans répétition de n éléments pris k à k) est un k-uplet (a₁, a₂, ..., a_k) d'éléments de E tel que a_i≠a_j qqsoit i, j € [1,k] avec i≠j, . Un tel k-uplet est aussi appelé k-liste distincte d'éléments de E.

Théorème

Soient E et F deux ensembles finis de cardinaux respectifs n et k. L’ensemble $\mathcal I(F, E)$ des applications injectives de F dans E est fini et son cardinal est égal à n(n-1)... (n-k+1) si k≤n et 0 sinon. Ce cardinal se note $A_n^k$ et se lit « Ank ». On dit aussi qu'on a un arrangement de k à n.

Démonstration

Si k > n, alors il n'existe aucune injection de F dans E et donc $A_n^k=0$ .
Si k < n, alors démontrons l'égalité par récurrence sur l'entier k.
- Si k = 1 alors F est un singleton et toute application de F dans E est injective donc $A_n^1 = n$ .
- Supposons l'égalité vérifiée pour tout ensemble F de cardinal k - 1 (2 ≤ k ≤ n) et démontrons la au rang k :
  Soit F un ensemble de cardinal k, et x un élément de F. Posons G=F\{x}. Nous avons card(G)=k-1.
  Considérons la relation qui relie deux injections de F dans E quand elles ont même restriction à G. Les classes d'équivalence partitionnent $\mathcal I(F,E)$ en classes ayant toutes comme cardinal n-(k-1). En effet, il y a autant de façons de prolonger une injection de G dans E en une injection de F dans E que de choix de l'image de x parmi les n-k+1 images possibles. De plus le nombre de classes d'équivalence est égal au nombre de restrictions différentes d'applications de $\mathcal I(F,E)$ à G; il y en a donc $\rm{card}\left(\mathcal I(G, E)\right)$ (la restriction d'une injection à une partie étant injective). D'après le lemme des bergers :
  $A_n^k = (n - k + 1). A_n^{k-1}= n(n - 1) \ldots (n-k+2)(n- k+1)$ .
Si k=0, nous poserons par convention pour tout entier naturel n $A_n^0=1$ , puisqu'il existe une seule application qui va de l'ensemble vide ∅ dans un ensemble quelconque E qui de plus est injective !

Démonstration (élémentaire)

Si 1 ≤ k ≤ n alors supposons que F={x₁, x₂, ..., x_k}. Pour construire une application injective de F dans E, nous devons

choisir l'image de x₁ et il y a n images possibles,
choisir l'image de x₂ et il reste n-1 images possibles,
...
choisir l'image de x_k, il reste dans l'ensemble E n - (k-1) éléments non atteints donc n - (k-1) images possibles.

Au total, nous avons construit n.(n-1).....(n - k + 1) applications injectives différentes.

Corollaire

$A_n^k$ est aussi le nombre de k-arrangements sans répétition d'un ensemble E de cardinal n et nous avons $\forall n, k \in \mathbb{N}, A_n^k=\left\{\begin{matrix}0 & \rm{\,si\,} & k>n\\\dfrac{n!}{(n-k)!} & \rm{\,si\,} & k\leq n\\\end{matrix}\right.$

Démonstration

Supposons F={x₁, x₂, ..., x_k}. Une injection f de F dans E s'identifie au k-uplet d'éléments distincts (f(x₁), f(x₂), ..., f(x_k)). Il y a donc une bijection entre l'ensemble des applications injectives de F dans E et l'ensemble des k-uplets d'éléments distincts de E.

Remarque

Construire un arrangement revient à placer les uns après les autres, k objets discernables pris parmi n, dans k cases numérotées et donc une permutation de n éléments est un n-arrangement de n éléments. La notion d'arrangement généralise donc celle de permutation.

Algorithme de calcul

Fonction Arrangements (n, k)

    Ank = 1

    // Test aux limites
    Si k < 0 ou k > n alors
        Retourner 0
    Fin Si
    
    // Calcul de Ank (boucle de i = n - k + 1 à n)
    i = n - k + 1
    Tant que i < n + 1
        Ank = Ank * i
        i = i + 1
    Fin tant que
    Retourner Ank

Fin fonction

Voir aussi

Liens internes

v · d · m

Opérations binaires

Numériques	En ensemble ordonné	Structurelles	Autres

Élémentaires $+$ Addition $-$ Soustraction $\times$ Multiplication $\div$ Division $\hat{}$ Puissance Arithmétiques $div$ Quotient euclidien $mod$ Reste euclidien $pgcd$ PGCD $ppcm$ PPCM Combinatoires $()$ Coefficient binomial $A$ Arrangement	Ensembles de parties $\cup$ Union $\backslash$ Complémentation $\cap$ Intersection $Δ$ Différence symétrique Ordre total $min$ Minimum $max$ Maximum Treillis $\wedge$ Borne inférieure $\vee$ Borne supérieure	Ensembles $\times$ Produit cartésien $\dot{\cup}$ Somme disjointe $\hat{}$ Puissance ensembliste Groupes $\oplus$ Somme directe $\ast$ Produit libre $\wr$ Produit en couronne Modules $\otimes$ Produit tensoriel $Hom$ Homomorphisme $Tor$ Torsion $Ext$ Extension Arbres $\vee$ Enracinement Variétés connexes $\#$ Somme connexe Espaces pointés $\vee$ Bouquet $\wedge$ Smash produit $\ast$ Joint	Fonctionnelles $\circ$ Composition de fonctions $\ast$ Produit de convolution Vectorielles $\cdot$ Produit scalaire $\wedge$ Produit vectoriel $\times\,$ Produit vectoriel généralisé Algébriques $[,]$ Crochet de Lie ${,}$ Crochet de Poisson $\wedge$ Produit extérieur Homologiques $\smile$ Cup produit $\cdot$ Produit d'intersection Séquentielles $+$ Concaténation

Logique booléenne : $\land$ ET (conjonction) • $\lor$ OU (disjonction) • $\oplus$ OU exclusif • $\Rightarrow$ IMP (implication) • $\Leftrightarrow$ EQV (équivalence)

Portail des mathématiques

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Arrangement de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

arrangement — [ arɑ̃ʒmɑ̃ ] n. m. • XIIIe; de arranger ♦ Action d arranger; son résultat. 1 ♦ Action de disposer dans un certain ordre; la disposition qui en résulte. ⇒ disposition; assemblage, constitution, organisation. Arrangement d une maison, d un mobilier … Encyclopédie Universelle
arrangement — UK US /əˈreɪndʒmənt/ noun ► [C, usually plural] a plan or preparation for how something will happen: make an arrangement »There wasn t enough time for him to make alternative arrangements. arrangement (for sb) to do sth »Some people have very… … Financial and business terms
Arrangement — Ar*range ment, n. [Cf. F. arrangement.] 1. The act of arranging or putting in an orderly condition; the state of being arranged or put in order; disposition in suitable form. [1913 Webster] 2. The manner or result of arranging; system of parts… … The Collaborative International Dictionary of English
arrangement — ARRANGEMENT. sub. m. Ordre, état de ce qui est arrangé. Arrangement de livres. Arrangement de vases, de porcelaines, de tableaux. Il y a du goût dans l arrangement de ces meubles. [b]f♛/b] Il se dit aussi De la disposition et de l ordre qu on… … Dictionnaire de l'Académie Française 1798
arrangement — I (ordering) noun adaption, arraying, collocation, compositio, composition, conformation, conlocatio, formation, method, regularity, schematism, symmetry, systematization, uniformity II (plan) noun conception, concoction, contrivance, course of… … Law dictionary
arrangement — Arrangement. s. m. v. Ordre, estat de ce qui est arrangé. Arrangement de livres. arrangement de vases, de porcelaines. Il se dit aussi de la disposition & de l ordre qu on observe dans un discours en mettant chaque terme à la place qui luy… … Dictionnaire de l'Académie française
arrangement — [n1] an understanding adjustment, agreement, compact, compromise, deal, frame up*, game plan*, layout*, organization, package*, package deal*, plan, preparation, provision, schedule, settlement, setup, terms; concept 684 arrangement [n2]… … New thesaurus
arrangement — (n.) 1727, from Fr. arrangement, from arranger arrange (see ARRANGE (Cf. arrange)) … Etymology dictionary
Arrangement — (franz., spr. angsch māng), Anordnung, Einrichtung; Abfindung, Vergleich, gütliche Übereinkunft. Blumen A., Blumengewinde, Blumenkorb. – In der Musik heißt A. insbes. die Bearbeitung eines Tonstücks für andre Instrumente, als der Komponist es… … Meyers Großes Konversations-Lexikon
Arrangement — (frz., spr. angsch máng), Einrichtung, Anordnung; gütlicher Vergleich; Bearbeitung (s. Arrangieren). Arrangementsgeschäft, in Österreich s.v.w. Zeitgeschäft, im Gegensatz zu Kassageschäft … Kleines Konversations-Lexikon
arrangement — may refer to a variety of formal or informal agreements concerning the conditions under which a bankrupt company may operate; often, it refers to an extension of time in which debt can be paid off. This was the term used under the old Chapter XI… … Glossary of Bankruptcy

Dictionnaires et Encyclopédies sur 'Academic'

Arrangement

Sommaire

Définition mathématique

Algorithme de calcul

Voir aussi

Liens internes

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Arrangement

Sommaire

Définition mathématique

Algorithme de calcul

Voir aussi

Liens internes

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link