4 Combiner et dénombrer

La combinatoire, c’est l’ensemble des méthodes et des techniques¹ mathématiques utilisé pour combiner des objets, c’est-à-dire les arranger, les sélectionner et les dénombrer selon des critères précis. Ces objets sont en nombre fini dès lors que leur dénombrement est nécessaire. Ils appartiennent à des structures comme des listes, des ensembles, des arbres, des graphes, appelées en informatique des structures de données.

Exemple : calcul (lien avec l’informatique), probabilité, complexité

4.1 Dénombrement

Pour dénombrer des ensembles, on utilise la fonction \(\card{}\) qui à tout ensemble fini associe le nombre de ses éléments. C’est un morphisme :

additif (somme (ou réunion) disjointe pour les ensembles, addition pour les entiers),
multiplicatif (produit cartésien pour les ensembles, produit pour les entiers).

Soit \(\Omega\) un ensemble fini. Nous allons dénombrer certaines structures élémentaires construites à partir de \(\Omega\).

Definition 4.1 (Arrangement) Un arrangement sur \(\Omega\) est une liste sans répétition formée d’éléments de \(\Omega\).

Exemple : si \(\Omega = \{a, b, c\}\), alors \(aa\), \(ba\) et \(ac\)² sont des listes, dont les deux dernières \(ba\) et \(ac\) sont des arrangements, la première \(aa\) étant une liste avec une répétition de \(a\).

Proposition 4.1 (Nombre d’arrangements) Le nombre d’arrangements de taille \(k\) dans l’ensemble \(\Omega\) de \(n\) éléments est

\[ \arrangement{n}{k} = \frac{n!}{(n - k)!}. \]

Démonstration

Pour construire un arrangement, on choisit un premier élément parmi les \(n\), puis un second parmi les \(n-1\) restants, et ainsi de suite jusqu’au \(k\)-ième choisi parmi les \(n-(k-1)\) restants, soit au total, \(n * (n-1) * \ldots * (n - (k- 1))\) constructions possibles. En multipliant par \((n-k)!\) le numérateur et le dénominateur, on obtient la fraction attendue \[ \frac{n!}{(n - k)!}. \]

Le nombre d’arrangements est aussi le nombre d’injections d’un ensemble de \(k\) éléments vers un ensemble de \(n\) éléments. Notamment, on peut prendre pour ensemble de départ l’ensemble \(\{1, \ldots, k\}\), qui correspond aux positions dans la liste : à \(1\) on associe l’élément en première position, à \(2\) on associe l’élément en seconde position, et ainsi de suite.

C’est aussi le nombre de feuilles de l’arbre dont l’ensemble des chemins de la racine à une feuille est exactement l’ensemble des listes sans répétition. La racine de l’arbre a \(n\) descendants, un par élément de \(\Omega\), les nœuds à la hauteur \(1\) ont \(n-1\) descendants, un par élément de \(\Omega\) privé du premier élément choisi, et ainsi de suite jusqu’aux nœuds à la hauteur \(k-1\) qui ont \((n - (k-1))\) descendants, la construction s’arrêtant aux nœuds à la hauteur \(k\).

stateDiagram-v2
    state "-" as p0
    state "a" as m1
    state "b" as m2
    state "c" as m3
    state "ab" as m12
    state "ac" as m13
    state "ba" as m21
    state "bc" as m23
    state "ca" as m31
    state "cb" as m32
     
    p0 --> m1: a
    p0 --> m2: b
    p0 --> m3: c
    m1 --> m12: b
    m1 --> m13: c
    m2 --> m21: a
    m2 --> m23: c
    m3 --> m31: a
    m3 --> m32: b

Figure 4.1: Arrangements de taille \(2\) dans un ensemble à \(3\) éléments \(\{a, b,c\}\).

Definition 4.2 (Combinaison) Une combinaison sur \(\Omega\) est un sous-ensemble³ de l’ensemble \(\Omega\).

Exemple : si \(\Omega = \{a, b, c\}\), alors \(\{a\}\) et \(\{a, b\}\) sont deux combinaisons, qu’on note comme des ensembles. On a les égalités suivantes : \(\{a, a\} = \{a\}\) et \(\{a, b\} = \{b, a\}\), puisque la répétition d’éléments ne change pas l’ensemble et l’ordre n’importe pas dans un ensemble.

Différence entre combinaison et arrangement - Dans une combinaison comme dans tout ensemble, il n’y a pas de séquence particulière entre les éléments, contrairement à un arrangement qui est une liste, donc une séquence ; à côté de cette différence fondamentale, un point commun demeure : dans les combinaisons comme dans les arrangements, il n’y a aucune répétition⁴.

Formalisation des combinaisons.

À partir des arrangements - Combinaison: classe d’équivalence sur les arrangements, deux arrangements étant équivalents s’ils sont égaux à une permutation près.
- Une classe d’équivalence contient tous les arrangements contenant exactement les mêmes éléments. Partant d’un arrangement appartenant à cette classe, tout arrangement de la classe s’obtient par une unique permutation (une bijection qui va permuter les éléments, les changer de place). Le cardinal de la classe est donc égal à \(k!\) si \(k\) est la taille de l’arrangement : pour construire une permutation, on choisit pour le premier élément une position parmi \(k\), pour le second une position parmi les \(k-1\) restantes, etc., soit au total \(k!\), égal à \(\arrangement{k}{k}\), une permutation étant une injection d’un ensemble fini vers lui-même.
Exemple : la classe associée à la combinaison \(\{a, b\}\) est l’ensemble d’arrangements \(\{ab, ba\}\).
À partir de l’ensemble \(\Omega\) - Fonction caractéristique (indiquant la présence ou non de l’élément dans le sous-ensemble formant la combinaison) de l’ensemble \(\Omega\) vers \(\boolD\)⁵, d’où le nombre total de combinaisons dans un ensemble de \(n\) éléments : \(2^n\).

Exemple : la combinaison \(\{a, b\}\) peut être représentée par la fonction \((a \mapsto \vrai{}, b \mapsto \vrai{}, c \mapsto \faux{})\), où \(\vrai{}\) est la valeur vraie, et \(\faux{}\) est la valeur fausse.

Proposition 4.2 (Nombre de combinaisons) Le nombre de combinaisons de taille \(k\) dans l’ensemble \(\Omega\) de \(n\) éléments est

\[ \combi{n}{k} = \frac{n!}{(n - k)! * k!}. \]

Démonstration en utilisant les classes d’équivalence

On construit tous les arrangements de taille \(k\) puis pour dénombrer les combinaisons, on compte les classes d’équivalence (chaque classe représentant une partie ou un sous-ensemble) pour obtenir le nombre de sous-ensembles de taille \(k\).

Nombre d’arrangements de taille \(k\) dans un ensemble de \(n\) éléments : \(\frac{n!}{(n - k)!}\)
Nombre de classes d’équivalence : comme le produit du nombre de classes d’équivalence par le cardinal de chaque classe d’équivalence (soit \(k!\)) est égal au nombre total d’arrangements de taille \(k\), on obtient le nombre de classes d’équivalence comme rapport de \(\frac{n!}{(n - k)!}\) sur \(k!\).

Démonstration voisine utilisant une épreuve aléatoire

Notons \(\combi{n}{k}\) le nombre de combinaisons formées de \(k\) éléments dans un ensemble de \(n\) éléments. Considérons l’épreuve aléatoire suivante.

Donnée : un ensemble de \(n\) éléments, identifiés par des numéros de \(1\) à \(n\),
Action : le tirage successif de \(k\) éléments d’une urne contenant les \(n\) éléments, sans remise⁶,
Résultat : la liste des \(k\) éléments triés suivant l’ordre des numéros.

Le tri final permet d’établir une correspondance bijective (\(1-1\)) entre les résultats de l’épreuve aléatoire et les combinaisons. La probabilité d’obtenir une combinaison, soit une certaine liste triée, est la somme des probabilités des listes dont le tri donne cette liste triée. Il y a \(k!\) telles listes, puisque chaque liste s’obtient par une unique permutation à partir de la liste triée. Chaque liste est un arrangement, si bien que la probabilité de l’obtenir est \(1/\arrangement{n}{k}\). On obtient donc l’égalité suivante entre probabilités :

\[ \frac{1}{\combi{n}{k}} = \frac{k!}{\arrangement{n}{k}}, \]

ce qui par inversion donne l’égalité attendue.

Démonstration alternative utilisant une épreuve aléatoire originale

Notons \(\combi{n}{k}\) le nombre de combinaisons formées de \(k\) éléments dans un ensemble de \(n\) éléments. Étant donné une combinaison de \(k\) éléments, pour distinguer ses éléments des autres élément de l’ensemble, colorions ses \(k\) éléments. Plaçons dans une urne les \(k\) éléments colorés avec les autres éléments incolorés. Considérons alors l’épreuve aléatoire suivante.

Donnée : un ensemble de \(n\) éléments, avec \(k\) éléments colorés et \(n-k\) éléments incolorés,
Action : le tirage successif de \(k\) éléments d’une urne contenant les \(n\) éléments, sans remise,
Résultat : un résultat binaire, vrai si les \(k\) éléments tirés sont colorés, faux sinon.

Le résultat final est vrai si et seulement si le tirage produit la combinaison colorée. La probabilité de tirer \(k\) éléments colorés est le produit des \(k\) probabilités de tirer un élément coloré, puisque ces \(k\) tirages sont indépendants les uns des autres. En revanche, la probabilité varie : la probabilité de tirer un élément coloré sachant qu’on a tiré auparavant \(j\) éléments colorés est \((k-j)/(n-j)\). Ainsi la probabilité de tirer cette combinaison est égale à \[ \frac{k}{n} * \frac{k-1}{n-1} * \ldots * \frac{1}{n - (k-1)}, \]

soit \(k! / (n! / (n- k)!)\). Par inversion, \(\combi{n}{k} = \frac{n!}{(n-k)! * k!}\).

Relations récurrentes entre les nombres de combinaisons - Du fait de la croissance très rapide des suites factorielles , il est préférable de calculer récursivement les combinaisons, en utilisant la forme implicite d’une relation de récurrence plutôt que la formule explicite avec les factorielles. Le nombre de combinaisons peut ainsi se calculer par récurrence grâce au triangle de Pascal, au nom très peu universel, auquel il est nécessaire d’associer dans son esprit le terme plus précis de “triangle des combinaisons” et l’idée que le nombre de combinaisons peut se calculer par récurrence sur les ensembles décomposés récursivement (un ensemble étant soit vide, soit construit à partir d’un élément et d’un ensemble).

\(\combi{0}{0} = 1:\) on compte une combinaison vide dans un ensemble vide,
\(\combi{n + 1}{0} = 1:\) on compte une combinaison vide dans un ensemble à \(n+1\) éléments,
\(\combi{n + 1}{n + 1} = 1:\) on compte une combinaison totale dans un ensemble à \(n+1\) éléments,
\(\combi{n + 1}{k + 1} = \combi{n}{k} + \combi{n}{k + 1}:\) : étant donné un une décomposition de l’ensemble de \(n+1\) éléments en un élément \(e\) et un sous-ensemble de \(n\) éléments \(S\), on compte les combinaisons de \(k+1\) en sommant
- les \(\combi{n}{k}\) combinaisons contenant \(e\) et \(k\) éléments de \(S\), et
- les \(\combi{n}{k + 1}\) combinaisons ne contenant pas \(e\) et contenant \(k+1\) éléments de \(S\).

Il existe d’autres relations de récurrence, comme celle découlant de la démonstration alternative :

\[ \combi{n + 1}{k + 1} = \frac{n+1}{k+1} * \combi{n}{k}. \]

On peut en déduire un autre algorithme efficace.

Ces nombres de combinaisons interviennent dans un développement célèbre et utile, connu comme la formule du binôme de Newton:

\[ (X + Y)^n = \Sigma_{i = 0}^n \coefBi{n}{i} X^i*Y^{n-i}. \]

Le coefficient \(\coefBi{n}{i}\) est une autre notation pour le nombres de combinaisons \(\combi{n}{i}\) et s’appelle un coefficient binomial⁷.

Comment retrouver cette formule ? Développons \((X + Y)^n\), soit \((X + Y) * \ldots * (X + Y)\), où \((X + Y)\) apparaît \(n\) fois. Pour chaque facteur \((X + Y)\), on doit choisir soit le terme gauche \(X\) soit le terme droit \(Y\), et finalement faire tous les choix possibles. Un choix de \(i\) \(X\) et donc de \(n - i\) \(Y\) engendre le produit binomial \(X^i * Y^{n-i}\) ; le nombre de tels choix est égal au nombre de sous-ensembles à \(i\) éléments dans un ensemble à \(n\) éléments, soit \(\combi{n}{i}\), noté ici \(\coefBi{n}{i}\)⁸. Il reste à sommer sur \(i\) pour obtenir la formule. La formule est évidente pour \(n = 1\) (puisqu’il n’y a aucun produit à faire), triviale pour \(n = 2\), puisqu’il s’agit d’une identité remarquable, facilement visualisable par le calcul de l’aire d’un carré de côté \((X + Y)\), et devrait être connu pour \(n = 3\) et pour \(n = 4\), les coefficients se calculant à l’aide du triangle de Pascal. Voir la Figure 5.2 qui illustre l’arborescence des choix dans le cas \(n = 3\).

stateDiagram-v2
    state "+" as p0
    state "*" as m1
    state "*" as m2
    state "*" as m21
    state "*" as m22
    state "*" as m23
    state "*" as m24
    state "X³" as m31
    state "X²*Y" as m32
    state "X²*Y" as m33
    state "X*Y²" as m34
    state "X²*Y" as m35
    state "X*Y²" as m36
    state "X*Y²" as m37
    state "Y³" as m38
    
    p0 --> m1: X
    p0 --> m2: Y
    m1 --> m21: X
    m1 --> m22: Y
    m2 --> m23: X
    m2 --> m24: Y
    m21 --> m31: X
    m21 --> m32: Y
    m22 --> m33: X
    m22 --> m34: Y
    m23 --> m35: X
    m23 --> m36: Y
    m24 --> m37: X
    m24 --> m38: Y

Figure 4.2: Développement du binôme \((X+Y)^3\).

Formule du binôme de Newton : démonstration par récurrence

\[ \begin{array}{rcl} (X + Y)^n & = & \Sigma_{k=0}^n \binom{n}{k} * X^k*Y^{n-k}.\\ \end{array} \]

\(n=0\) : \((X+Y)^0 = \Sigma_{k=0}^0 \binom{0}{k} * X^k*Y^{-k}\), car \(1 = 1\).

\(n\in\Nat{}\) : supposons \((X+Y)^n = \Sigma_{k=0}^n \binom{n}{k} * X^k*Y^{n-k}\). On a :

\[ \begin{array}{rcl} (X + Y)^{n+1} & = & (X + Y)*(X + Y)^n, \\ & = & (X + Y)*(\Sigma_{k=0}^n \binom{n}{k} * X^k*Y^{n-k}),\\ & = & X*(\Sigma_{k=0}^n \binom{n}{k} * X^k*Y^{n-k}) \\ & + & Y*(\Sigma_{k=0}^n \binom{n}{k} * X^k*Y^{n-k}), \\ & = & \Sigma_{k=0}^n \binom{n}{k} * X^{k+1}*Y^{n-k}\\ & + & \Sigma_{k=0}^n \binom{n}{k} * X^k*Y^{n+1-k}, \\ & = & \Sigma_{j=1}^{n+1} \binom{n}{j-1} * X^{j}*Y^{n+1-j} \\ & + & \Sigma_{k=0}^n \binom{n}{k} * X^k*Y^{n+1-k}, \\ & = & \binom{n}{n} * X^{n+1} \\ & + & \Sigma_{k=1}^n (\binom{n}{k} + \binom{n}{k-1}) * X^k*Y^{n+1-k} \\ & + & \binom{n}{0} * Y^{n+1}, \\ & = & \Sigma_{k=0}^{n+1} \binom{n+1}{k} * X^k*Y^{n+1-k}. \\ \end{array} \]

On utilise l’égalité \(\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}\), qui se démontre ainsi : si on choisit un des éléments parmi les \(n+1\), il y a \(\binom{n}{k-1}\) parties de \(k\) éléments qui le contiennent, et \(\binom{n}{k}\) parties de \(k\) éléments qui ne le contiennent pas, et leur somme donne le nombre de parties de \(k\) éléments dans un ensemble de \(n+1\) éléments, soit \(\binom{n+1}{k}\).

Conclusion : pour tout \(n\in\Nat{}\), \((X+Y)^n = \Sigma_{k=0}^n \binom{n}{k} * X^k*Y^{n-k}\)

Remarque : la seconde égalité s’obtient soit en permutant \(X\) et \(Y\), et en utilisant la commutativité, soit en sommant dans l’autre sens, \(\Sigma_{k=0}^n \binom{n}{k} * X^k*Y^{n-k} = \Sigma_{j=0}^n \binom{n}{n-j} * X^{n-j}*Y^{j}\), avec \(k = n-j\), et en remarquant que \(\binom{n}{k} = \binom{n}{n-k}\), du fait que les parties de \(k\) éléments et celles de \((n-k)\) se correspondent exactement, par complémentarité.

Etymologiquement, le suffixe atoire, variante de oire, désigne un moyen pour réaliser l’action de la racine du mot, ici combiner.↩︎
Nous notons les listes comme des mots, en accolant les éléments, ce qui peut être ambigu si les éléments sont composés de plusieurs caractères. Des notations non ambiguës sont les suivantes : \(a.b\), avec un opérateur noté par un point, \([a, b]\) ou \((a, b)\) avec un parenthésage comme en Python, ou encore \((\texttt{cons}\ a\ b)\) avec une notation fonctionnelle préfixe, comme en les langages de la famille Lisp.↩︎
On dit aussi une partie.↩︎
Un ensemble pour lequel on admet plusieurs occurrences d’un même élément est appelé un multi-ensemble. Dans ce cas, on pourrait parler d’une combinaison avec répétition.↩︎
L’ensemble a deux éléments, correspondant à vrai et faux, la fonction caractéristique associant vrai à un élément si l’élément appartient à la combinaison, faux sinon.↩︎
Sans remettre l’élément tiré dans l’urne avant le tirage suivant.↩︎
Binomial car associé aux binômes \(X^i\) et \(Y^{n-i}\).↩︎
Cette dernière notation semble progressivement s’imposer. AFFAIRE↩︎