Combinatoire

Un octet est une suite de $8$ chiffres binaires : c'est une $8$-liste de $\{0,1\}$. Il y en a $2^8=256$ — d'où les $256$ valeurs que peut coder un octet. Et si l'on s'interdisait de réutiliser deux fois le même symbole, combien en resterait-il ?

Les $p$-arrangements sont les $p$-listes sans répétition : on s'interdit de prendre deux fois le même élément.

Soit une urne contenant $n$ boules numérotées de $1$ à $n$.

• Si l'on tire successivement $p$ boules sans remise, alors chaque tirage est un $p$-arrangement de $\llbracket 1,n\rrbracket$.
• En revanche, si l'on tire successivement $p$ boules avec remise, alors chaque tirage est une $p$-liste de $\llbracket 1,n\rrbracket$.

Si $p>n$, il n'existe aucun $p$-arrangement (on ne peut pas tirer plus d'éléments qu'il n'y en a dans l'ensemble). La notation traditionnelle $A_n^p$ n'est plus guère utilisée.

Intuitivement, on dispose de $n$ possibilités pour le premier élément ; pour chacun de ces choix, il reste $n-1$ éléments, donc $n-1$ possibilités pour le deuxième, soit $n(n-1)$ possibilités pour les deux premiers. Pour le troisième élément, les deux premiers étant fixés, il reste $n-2$ possibilités, soit $n(n-1)(n-2)$ possibilités. Et ainsi de suite : pour le $p$-ième élément, il reste $n-p+1$ possibilités. Au total, il y a donc $n(n-1)(n-2)\cdots(n-p+1)$ possibilités pour le choix ordonné de $p$ éléments sans répétition.

Si $\operatorname{Card} E=n$, les permutations de $E$ sont les $n$-arrangements de $E$, c'est-à-dire les listes de tous les éléments de $E$ sans répétition.

Effectuer une permutation sur un ensemble, c'est changer l'ordre de ses éléments. Les permutations sont en fait exactement les bijections de $E$ sur lui-même. Lorsque l'on compte les éléments de $E$, on leur attribue un ordre (par la bijection de $\llbracket 1,n\rrbracket$ sur $E$) ; une permutation revient simplement à « changer cet ordre » par une bijection.

Par définition, il n'y a pas d'ordre dans un ensemble et tous les éléments y sont deux à deux distincts. Ainsi, les $p$-combinaisons, à l'instar des $p$-arrangements, sont constituées d'éléments deux à deux distincts ; la différence est que les $p$-arrangements prennent en compte l'ordre, alors qu'il est indifférent pour les combinaisons. À une $p$-combinaison correspondent donc autant de $p$-arrangements qu'il y a de façons de réordonner ses éléments, soit $p!$ (le nombre de permutations de $p$ éléments). Il y a donc $p!$ fois plus de $p$-arrangements que de $p$-combinaisons, ce qui donne la formule

Le principe de comptage précédent se formalise par le lemme des bergers : pour compter les moutons d'un pré, le plus simple est de compter le nombre de pattes et de diviser par $4$. Formellement : si $A$ est un ensemble non vide admettant une partition $E_1,E_2,\dots,E_n$ telle que chaque $E_i$ ait exactement $p$ éléments, alors $A$ possède $p\times n$ éléments. Autrement dit : si $f$ est une application surjective de $A$ sur $E$ telle que $\forall y\in E,\ \operatorname{Card} f^{-1}(\{y\})=p$, alors $p\times\operatorname{Card} E=\operatorname{Card} A$. Les deux énoncés sont équivalents, et la preuve s'écrit directement avec le cardinal d'une partition (union disjointe).

Dans un jeu de $32$ cartes, une main de $5$ cartes est une $5$-combinaison : la main $\{\text{As}\heartsuit,\ \text{Roi}\spadesuit,\ \dots\}$ ne change pas selon l'ordre où les cartes ont été distribuées. En revanche, la même distribution carte par carte, en notant l'ordre d'arrivée, serait un $5$-arrangement. Combien de fois plus d'arrangements que de mains, exactement ?

On considère le nombre de $p$-arrangements (ou $p$-listes sans répétition) lorsque l'ordre a de l'importance. Lorsque l'ordre n'a pas d'importance, on considère le nombre de parties à $p$ éléments (c'est-à-dire que l'on divise par $p!$).

Tableau récapitulatif :