Analyse combinatoire et dénombrement

Coefficient binomial Et triangle de pascal :

Jusqu’à présent, nous nous sommes intéressés aux arrangements et aux permutations, maintenant, nous allons étudier les combinaisons, qui nous permettront par la suite, d’établir deux théorèmes fondamentaux et de construire ce qu’on appelle le triangle de Pascal.

Combinaison sans répétition :

Tout d’abord, qu’est ce qu’une combinaison ? Une combinaison est une « sorte » d’arrangement, la différence c’est la notion d’ordre. En effet, lorsqu’on parle d’arrangement, on prend en compte l’ordre dans lequel on place des objets. Par exemple, si on prend une course de voitures, l’ordre d’arrivée des concurrents sera forcément ordonné. La première voiture à franchir la ligne d’arrivée sera nécessairement en première position, la deuxième en deuxième, etc…

Par conséquent, on peut s’appuyer sur la formule d’arrangement, mais il faut rajouter quelque chose pour être dans notre situation :

A^k_n=\displaystyle{=\frac{n{!}}{k{!}(n-k){!}}}

On a dit qu’il ne fallait pas de relation d’ordre, donc, il faut faire en sorte, lorsqu’on choisi un arrangement arbitraire, de retirer la possibilité d’avoir les autres, et ceci, pour chaque autre arrangement. Par exemple, si j’ai quatre trous, que j’ai 2 boules à placer dans ces 4 trous, et que je place la première boule au milieu, et ma seconde dans le trou à l’extrémité gauche, il faut que je retire la possibilité de placer ces boules dans le trou de droite et celui du milieu. Il faut donc retirer k{!} possibilités. On pourrait donc réécrire la formule comme ceci :

\displaystyle{\frac{A_k^n}{k{!}}=\frac{n{!}}{k{!}(n-k){!}}}

Ceci est la formule du coefficient binomial, qui est donc une combinaison sans répétition, on l’écrit comme ceci :

\begin{pmatrix}n \\ k \end{pmatrix}=\displaystyle{C_k^n=\frac{n{!}}{k{!}(n-k){!}}}

La parenthèse se lis k parmi n.

Prenons un exemple, nous avons une classe dans laquelle il y a 24 élèves, on veut former un comité de trois personnes et on veut savoir de combien de manière différentes on peut former ce comité à partir de cette classe de 24 élèves. On remarque bien l’absence d’ordre, en effet, choisir un élève en premier, ou ce même élève en second, n’a aucune importance. Ce que nous voulons, c’est uniquement en choisir 3, quelque soit l’ordre. On pose donc :

\begin{pmatrix} 24 \\ 3 \end{pmatrix}= \frac{24{!}}{3 \times 2 (24-3){!}}=\frac{24 \times 23 \times 22}{6}=2024

Il existe 2024 façons possibles de choisir 3 élèves parmi 24.

Il est également possible d’exprimer le coefficient binomial comme le nombre de k-arrangements dans l’ensemble n :

\displaystyle{A_n^k=\frac{C_n^k}{k{!}}=\frac{n{!}}{(n-k){!}}=\begin{pmatrix}n \\ k \end{pmatrix} k{!}}

Il ne s’agit ici que de manipulations algébriques, on simplifie par k{!} d’un côté, on multiplie donc l’autre côté par la même chose… Ce sont néanmoins différentes écritures à connaître…


A présent, voyons ce qu’est le triangle de Pascal, et comment il fût construit.
Si on reprend la formule du coefficient binomial, on peut se rendre compte d’une chose. Il existe un moyen, en connaissant la valeur de l’ensemble n, et la valeur de k, de trouver la valeur du nombre de combinaisons possibles de k parmi n.

la démarche de Pascal, a été de savoir si il était possible de construire un tableau dans lequel on pourrait relier ses valeurs entre elles, et immédiatement trouver le coefficient que l’on cherche. En effet, Pascal, qui ne fût pas le premier a créer ce tableau, fût en revanche le premier à démontrer nombreuses de ces propriétés et à mettre en place une version aboutie du raisonnement par récurrence. Voici le triangle de Pascal :

Les lignes représentent les valeurs de n, et les colonnes les valeurs de k.
Si on prend des valeurs de n et de k, au hasard, et qu’on y applique la formule du coefficient binomial, on voit qu’on trouve la même valeur que sur le tableau. Prenons n=6 et k=3 par exemple, on a alors :

\begin{pmatrix} 6 \\ 3 \end{pmatrix}=\displaystyle{\frac{6{!}}{3{!}(6-3){!}}=\frac{6 \times 5 \times 4 \times 3 \times 2}{3 \times 2(3 \times 2)}=\frac{6 \times 5 \times 4}{3 \times 2}=\frac{120}{6}=20}

On tombe bien sur la même valeur que dans le tableau 😀

Pourquoi le triangle de Pascal est aussi important ? En fait, il va nous permettre d’aller beaucoup plus loin que le calcul de simples coefficients binomiaux, mais avant de parler de notions comme le binôme de Newton par exemple, voyons quelques autres propriétés importantes du coefficient binomial :

La première, si on s’en réfère au triangle de Pascal, on sait que la somme de deux valeurs d’une même ligne, vaut la valeur se trouvant sur la ligne suivante, juste en dessous de la seconde valeur de la première ligne (Un schéma paraît plus évident) :

Comment pourrait-on exprimer ceci à travers une formule ? Tout simplement :

\begin{pmatrix} n \\ k \end{pmatrix}=\begin{pmatrix} n-1 \\ k-1 \end{pmatrix}+\begin{pmatrix} n-1 \\ k \end{pmatrix}

Il faudrait tout de même démontrer ceci rigoureusement. On pourrait estimer que le triangle de Pascal suffit, ce qui est généralement le cas, mais voyons si on peut arriver au même résultat algébriquement. on pose donc :

\begin{pmatrix} n-1 \\ k-1 \end{pmatrix}+\begin{pmatrix} n-1 \\ k \end{pmatrix}=\displaystyle{\frac{(n-1){!}}{(k-1){!}((n-1)-(k-1)){!}}+\frac{(n-1){!}}{k{!}((n-1)-k){!}}}

L’objectif va être de réduire au même dénominateur pour ensuite pouvoir extraire le résultat voulu. On va également simplifier certain termes :

\displaystyle{\frac{(n-1){!}}{(k-1){!}((n-1)-(k-1)){!}}+\frac{(n-1){!}}{k{!}(n-k-1){!}}=\frac{(n-1){!}k}{k{!}(n-k){!}}+\frac{(n-1){!}(n-k)}{k{!}(n-k){!}}}

*Notez que le dénominateur du premier terme se simplifie immédiatement, en effet, (n-1)-(k-1)=(n-k).
Maintenant, les dénominateurs sont les mêmes, on fait donc la somme des numérateurs :

\displaystyle{\frac{(n-1){!}k}{k{!}(n-k){!}}+\frac{(n-1){!}(n-k)}{k{!}(n-k){!}}=\frac{(n-1){!}(n-k+k)}{k{!}(n-k){!}}=\frac{(n-1){!}n}{k{!}(n-k){!}}=\frac{n{!}}{k{!}(n-k){!}}}

Ceci est exactement la formule des k parmi n. Par conséquent, on peut en déduire que :

\begin{pmatrix} n \\ k \end{pmatrix}=\begin{pmatrix} n-1 \\ k-1 \end{pmatrix}+\begin{pmatrix} n-1 \\ k \end{pmatrix}

Une deuxième propriété importante :

\begin{pmatrix} n+1 \\ k+1 \end{pmatrix}=\begin{pmatrix} n \\ k \end{pmatrix}+\begin{pmatrix} n \\ k+1 \end{pmatrix}

La méthode de démonstration est la même que précédemment. A l’aide du triangle de Pascal, le résultat est immédiat. Algébriquement… Nous n’allons pas refaire la démonstration, si vous suivez le procédé que nous avons utilisé, vous y arriverez sans trop de difficultés.

Trois dernières propriétés :

  • \begin{pmatrix} n \\ 0 \end{pmatrix}=\begin{pmatrix} n \\ n \end{pmatrix}=1

    En effet, il n’existe qu’un seul moyen d’avoir 0 ou n succès parmi n essais, et ceci se vérifie :

    \displaystyle{\begin{pmatrix} n \\ 0 \end{pmatrix}=\frac{n{!}}{0{!}(n-0){!}}=\begin{pmatrix} n \\ n \end{pmatrix}=\frac{n{!}}{n{!}(n-n){!}}=1}
  • Autre propriété :

    \displaystyle{\begin{pmatrix} n \\ 1 \end{pmatrix}=\begin{pmatrix} n \\ n-1 \end{pmatrix}=n}

    Lorsqu’on choisis 1 élément parmi n, on a n façon de disposer de cet élément, bien entendu, il en va de même si on prend (n-1) éléments. On a n combinaisons possibles.

    \displaystyle{\begin{pmatrix} n \\ 1 \end{pmatrix}=\begin{pmatrix} n \\ n-1 \end{pmatrix}=\frac{n{!}}{(n-1){!}(n-(n-1)){!}}=\frac{n{!}}{(n-1){!}}=n}
  • Pour finir :

    \displaystyle{\begin{pmatrix} n \\ k \end{pmatrix}=\begin{pmatrix} n \\ n-k \end{pmatrix}}

    Autant de chemins mènent à k succès et à k échecs, et lorsqu’on obtient k succès, cela revient à obtenir n - k échecs.

    \displaystyle{\begin{pmatrix} n \\ k \end{pmatrix}=\frac{n{!}}{k{!}(n-k){!}}=\begin{pmatrix} n \\ n-k \end{pmatrix}=\frac{n{!}}{(n-k){!}(n-(n-k)){!}}=\frac{n{!}}{(n-k){!}k{!}}}