Cours : Liste des coefficients binomiaux k parmi n pour n donné (avec la formule de Pascal) - Python

Formule et triangle de Pascal

Nous avons vu en cours la formule de Pascal, qui nous dit que, pour tous les entiers naturels $n\geq 2$ et $k$ tels que $1\leq k \leq n-1$ :

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

Nous savons aussi que, pour tout entier naturel $n$ :

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

Nous avons aussi donné le triangle de Pascal, que nous remettons ici jusqu’à $n=5$ :

À partir d’une ligne du triangle de Pascal connue, générer la ligne suivante

Ce que nous venons de rappeler dans la première partie nous permet de nous rendre compte que, connaissant une ligne du triangle de Pascal, nous pouvons en déduire la suivante.

• Commençons donc par voir l’algorithme qui permet ce calcul.

Nous allons nous servir des listes pour donner les coefficients binomiaux correspondant à un entier naturel $n$.

Exemple

Par exemple, pour $n=3$, les coefficients binomiaux se présenteront ainsi :

$$[1,\,3,\,3,\,1]$$

Avec donc : $\binom 30=1$, $\binom 31=3$, $\binom32=3$, $\binom32=1$.

• Créons une fonction que nous nommons : $\purple{\text{ligne\textunderscore suiv}}$, qui prendra comme paramètre $\purple{\text{ligne}}$, une ligne du triangle de Pascal donnée sous la forme d’une liste, et qui retournera la ligne suivante.

• Nous savons que, pour tout entier naturel $n$ : $\binom n0=1$.
• Le premier élément de la liste sera toujours $1$.

Nous créons donc une liste nommée $\purple{\text{suivante}}$, dont nous indiquons le premier élément :

• Nous allons maintenant générer les coefficients suivants de la nouvelle ligne grâce à une boucle.

Pour mieux comprendre comment borner cette boucle, prenons comme exemple la ligne donnant les coefficients binomiaux pour $n=3$ : $\purple{\text{ligne}}=[1,\,3,\,3,\,1]$.
Et nous souhaitons que la fonction qui prend cette liste en paramètre nous renvoie la ligne suivante, c’est-à-dire la liste des coefficients binomiaux pour $n=4$ : $\purple{\text{suivante}}=[1,\,4,\,6,\,4,\,1]$.

Nous avons déjà assigné la valeur $1$ à l’élément $0$ de $\purple{\text{suivante}}$. Nous savons aussi que son dernier élément sera égal à $1$.

• Ce sont donc les éléments $1$, $2$ et $3$ que nous voulons calculer.

$3$ est égal au nombre d’éléments de la liste $\purple{\text{ligne}}$ moins $1$, soit $4-1$.

Généralisons : pour $n$ donné, la liste $\purple{\text{suivante}}$ a $n+1$ éléments, qui donnent les $n+1$ coefficients binomiaux (de $k=0$ à $k=n$). Comme on connaît le premier et le dernier, il y en a donc : $n+1-2=n-1$ à trouver.

• En tenant compte de la particularité de la fonction $\purple{\text{range}}$ en Python, nous écrivons :

• Nous pouvons maintenant calculer ces coefficients grâce à la formule de Pascal.
• Par exemple, cette formule nous dit que :

$$\begin{aligned} \begin{pmatrix} n \\ 1 \end{pmatrix}&=\begin{pmatrix} n-1 \\ 1-1 \end{pmatrix} + \begin{pmatrix} n-1 \\ 1 \end{pmatrix} \\ &=\begin{pmatrix} n-1 \\ 0 \end{pmatrix}+\begin{pmatrix} n-1 \\ 1 \end{pmatrix} \\ \end{aligned}$$

Ainsi, le coefficient donné par l’élément $1$ de la liste $\purple{\text{suivante}}$ se calcule en faisant la somme des coefficients donnés par les éléments $1-1=0$ et $1$ de la liste $\purple{\text{ligne}}$.

• De la même façon :

$$\begin{aligned} \begin{pmatrix} n \\ 2 \end{pmatrix}&=\begin{pmatrix} n-1 \\ 2-1 \end{pmatrix} + \begin{pmatrix} n-1 \\ 2 \end{pmatrix} \\ &=\begin{pmatrix} n-1 \\ 1 \end{pmatrix}+\begin{pmatrix} n-1 \\ 2 \end{pmatrix} \\ \end{aligned}$$

Autrement dit, le coefficient donné par l’élément $2$ de la liste $\purple{\text{suivante}}$ se calcule en faisant la somme des coefficients donnés par les éléments $2-1=1$ et $2$ de la liste $\purple{\text{ligne}}$.

• De manière générale :

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

Et le coefficient donné par l’élément $\purple{\text{k}}$ de la liste $\purple{\text{suivante}}$ se calcule en faisant la somme des coefficients donnés par les éléments $\purple{\text{k}}-1$ et $\purple{\text{k}}$ de la liste $\purple{\text{ligne}}$.

• Nous ajoutons ces nouveaux éléments dans la liste $\purple{\text{suivante}}$ au fur et à mesure qu’ils sont calculés :

• Nous savons que, pour tout entier naturel $n$ : $\binom nn=1$.
• Nous ajoutons donc à $\purple{\text{suivante}}$ cet élément.

• Enfin, nous demandons à la fonction de retourner la liste $\purple{\text{suivante}}$ générée.

• Voici l’algorithme Python de cette fonction, où nous n’oublions pas de mettre les indentations :

Remarquons que, si le paramètre de la fonction est la liste $\purple{\text{ligne}}=\lbrack 1]$ (c’est la ligne pour $n=0$), alors on n’entrera pas dans la boucle, et la fonction renverra $\purple{\text{suivante}}=[1,\,1]$ (c’est la ligne pour $n=1$).

• La fonction s’applique dès la première ligne du triangle de Pascal.

Donner la liste des coefficients binomiaux pour $n$ donné

Nous venons de créer une fonction qui, à une ligne donnée du triangle de Pascal, renvoie la ligne suivante. En fait, le plus dur est fait.

• Pour un entier naturel donné $n$, nous souhaitons retourner la liste des coefficients binomiaux $\binom nk$, avec $0\leq k\leq n$.

Il s’agit donc de générer, de ligne en ligne, la liste qui nous intéresse, en partant de $\binom 00=1$.

• Et nous avons donc une fonction toute prête pour cela.
• Définissons la fonction $\purple{\text{liste\textunderscore coef(n)}}$, qui prendra comme paramètre un entier naturel $\purple{\text n}$ et qui affichera la liste des coefficients binomiaux correspondants.

• Nous initialisons la variable $\purple{\text{ligne}}$, qui sera affichée, avec la valeur de $\binom 00=1$.

• Nous générons, à partir de la liste $\purple{\text{ligne}}$ une nouvelle ligne, pour $\purple{\text{j}}$ allant de $0$ à $\purple{\text{n}}-1$ (pour avoir au final la ligne correspondant au $\purple{\text n}$ entré).
• En tenant compte de la particularité de la fonction $\purple{\text{range}}$, nous écrivons :

• Nous assignons à $\purple{\text{ligne}}$ la nouvelle ligne générée par la fonction $\purple{\text{ligne\textunderscore suiv}}$ que nous avons programmée.

• En sortie de boucle, nous affichons la liste obtenue.

• Et voici l’algorithme Python de la fonction, toujours sans oublier les indentations :

Remarquons que, si nous mettons comme paramètre $\purple {\text n}=0$, alors nous n’entrerons pas dans la boucle, et la fonction affichera $\lbrack 1]$ (c’est la ligne pour $n=0$).

• La fonction marche dès la première ligne du triangle de Pascal.

Algorithme complet

• Si nous entrons $\purple{\text{liste \textunderscore coef(6)}}$, nous aurons bien en retour :

$$[1,\,6,\,15,\,20,\,15,\,6,\,1]$$

Astuce

Si nous entrons un $n$ grand, par exemple $100$, nous aurons alors une liste longue et guère lisible.

• Nous pouvons, au moyen d’une petite boucle dans le programme principal, améliorer l’affichage, en précisant à chaque fois le $\purple {\text k}$ concerné et en rappelant le $\purple{\text n}$ donné. Par exemple :

$\begin{aligned} \textcolor{#A9A9A9}{\text{8}}&\quad \text{def liste\textunderscore coef(n):} \\ \textcolor{#A9A9A9}{\text{9}}&\quad\qquad \text{ligne=\lbrack 1]} \\ \textcolor{#A9A9A9}{\text{10}}&\quad\qquad \text{for j in range(n):} \\ \textcolor{#A9A9A9}{\text{11}}&\quad\qquad\qquad \text{ligne=ligne\textunderscore suiv(ligne)} \\ \textcolor{#A9A9A9}{\text{12}}&\quad\qquad \text{for k in range(n+1):} \\ \textcolor{#A9A9A9}{\text{13}}&\quad\qquad\qquad \text{print(k, $^{\backprime\backprime}$ parmi $^{\prime\prime}$,n, $^{\backprime\backprime}$ : $^{\prime\prime}$,ligne[k])} \end{aligned}$