Combinaisons et arrangements
Mathématiquement, on dénombre les éléments d'un ensemble pour connaître son cardinal. Ce peut être un simple comptage ou l'utilisation de techniques moins... primaires. Autrefois, celles-ci étaient étudiées afin d'introduire le vaste chapitre des probabilités. Aujourd'hui, ces dernières sont enseignées de plus en plus tôt dans les études tandis que l'analyse combinatoire est enseignée en terminale spécialité maths. Il est pourtant plus logique que l'apprentissage du dénombrement précède celui des probabilités puisqu'il permet de déterminer l'univers des possibilités.
On dispose d’un certain nombre d’éléments et on cherche à les « combiner ». Combien existe-t-il de possibilités ? On distingue deux types principaux : soit ces éléments sont ordonnés soit ils ne le sont pas. Les suites de \(k\) éléments ordonnés sont appelées k-uplets. Ce sont les trois cas que nous étudierons ci-dessous. Si les éléments sont ordonnés, on parle de combinaison (en fin de page).
Ci-dessous, \(n\) et \(k\) sont deux entiers naturels.
La permutation
Le premier cas de figure est celui où l’on dispose de la totalité de \(n\) éléments dans un certain ordre. Ils peuvent être réagencés si l'on permute l'ordre dans lequel ils apparaissent. Combien de possibilités ? Réponse : \(n!\) (factorielle de \(n\)).
La page sur les permutations vous expliquera tout ceci.
La k-liste (ou arrangement avec répétition)
On l'appelle aussi p-liste. Là aussi, l’ordre a son importance, mais on peut réutiliser un élément (\(k\) fois). Le nombre de possibilités est chaque fois égal à \(n.\) Peu importe que \(n\) soit inférieur, égal ou supérieur à \(k.\) On cherche donc \(n^k.\) Sans toujours l'appeler k-liste, c'est en principe par ce calcul que sont abordées au lycée les probabilités d'évènements indépendants.
Exemple de k-liste : nombre de possibilités de codes de carte bancaire à quatre chiffres. Réponse : \(10^4 = 10\,000.\)
L’arrangement (sans répétition)
Cette notion est un peu moins utilisée. Elle ne figure d'ailleurs pas dans le programme de terminale bien qu'elle puisse être évoquée.
On ne prend qu’une seule fois un certain nombre d’éléments de l’ensemble (contrairement à la permutation) en s’attachant à l’ordre. Un arrangement de \(k\) éléments pris parmi \(n\) s'écrit et se calcule ainsi :
\[A_n^k = \frac{{n!}}{{(n - k)!}}\]
Exemple d’arrangement : quinze chevaux sont partants. Combien de possibilités de tiercés dans l’ordre existe-t-il ? \(A_3^{15} = 2\,730.\)
S’il n’y avait que trois chevaux partants, on se trouverait dans la situation d’une factorielle. Et comme l’arrivée des deux premiers impliquerait la place du troisième, on peut constater la double égalité suivante : \(A_n^n = A_n^{n-1} = n!\)
Note (hors programme du secondaire) : une façon très matheuse de présenter les choses est de considérer d'une part l'ensemble des places d'arrivée (premier, deuxième...) et d'autre part celui des partants, puis de considérer l'arrangement comme une injection du premier ensemble sur le deuxième (du moins en l'absence d'ex aequo) au contraire de la permutation qui est une bijection.
La combinaison
À la différence de l’arrangement, l’ordre des \(k\) éléments pris parmi \(n\) n'a aucune importance. La notion de combinaison est essentielle en statistiques et probabilités.
On l'écrit de moins en moins souvent \(C_n^k\) et de plus en plus \(\left( {\begin{array}{*{20}{c}} n\\ k \end{array}} \right)\).
La formule de calcul est \(\left( {\begin{array}{*{20}{c}} n\\ k \end{array}} \right) = \frac{n!}{k!(n-k)!}\)
C'est aussi \(\frac{A_n^k}{k!}.\)
\(n\) et \(p\) sont parfois nommés les coefficients binomiaux (on les retrouve dans la formule de la loi binomiale qui est une loi de probabilités). Plus souvent, c'est la combinaison elle-même qui est qualifiée de coefficient binomial. Dans cette loi de probabilités, elle dénombre les branches de l'arbre de probabilités qui satisfont à la condition cherchée (illustration en page de succession d'évènements indépendants).
Voir les propriétés en page de coefficient binomial et les démonstrations de combinatoire.
Exemple : combien de mains de cinq cartes sont-elles possibles sur un jeu de 52 ? Ici l'ordre n'a pas d'importance : on se fiche de la place de telle ou telle carte dans votre main. Réponse : 2 598 960.
Autre exemple : pendant les trois minutes qui précèdent une réunion, les trente participants se serrent tous la main. 435 poignées de mains échangées ! Effarant...
Vous en voulez d'autres ? Vous avez un accès illimité aux exercices de combinatoire !
Pour une utilisation avec une calculatrice TI, rendez-vous en page loi binomiale à la calculatrice. Avec une Casio, page de coefficient binomial. Avec Excel, utilisez la fonction COMBIN.
Le triangle de Pascal est une « table » des combinaisons, réalisable avec un tableur en quelques secondes. Sa construction est la façon la plus simple de déterminer une combinaison à la main.
La combinaison avec répétition
Beaucoup moins utilisée que les autres techniques de combinatoire, la combinaison avec répétition de \(k\) éléments pris parmi \(n\) n'est pas au programme du secondaire.
Comme les répétitions sont possibles, \(k\) peut être supérieur à \(n.\)
\[\Gamma _n^k = \left( {\begin{array}{*{20}{c}} {n + k - 1}\\ k \end{array}} \right)\]
C'est un coefficient binomial, donc il existe une formule équivalente.
\[\Gamma _n^k = \left( {\begin{array}{*{20}{c}} {n + k - 1}\\ {n - 1} \end{array}} \right)\]
Par exemple, nous possédons un chat blanc et un chat noir. Tous les soirs, nous en caressons un et un seul. Sur quatre jours, combien de possibilités, sachant que l'on ne se préoccupe pas de l'ordre ?
\[\Gamma _2^4 = \left( {\begin{array}{*{20}{c}} 5\\ 1 \end{array}} \right) = 5\]
\(E = \{(N,N,N,N)\,;\) \((N,N,N,B)\,;\) \((N,N,B,B)\,;\) \((N,B,B,B)\,;\) \((B,B,B,B)\}\)
