Médaille
N°1 pour apprendre & réviser du collège au lycée.

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

Déjà plus de

1 million

d'inscrits !

Introduction :

Dans cette fiche, nous allons voir un programme en Python qui va nous permettre, grâce à la formule de Pascal découverte en cours, de donner la liste des coefficients binomiaux (nk)\binom nk pour un entier naturel nn donné.

Formule et triangle de Pascal

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

(nk)=(n1k1)+(n1k)\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 nn :

(n0)=(nn)=1\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=5n=5 :

nk^{k\,\rightarrow}_{n\,\downarrow} 00 11 22 33 44 55
00 11
11 11 11
22 11 22 11
33 11 33 33 11
44 11 44 66 44 11
55 11 55 1010 1010 55 11

À 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 nn.

bannière exemple

Exemple

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

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

Avec donc : (30)=1\binom 30=1, (31)=3\binom 31=3, (32)=3\binom32=3, (32)=1\binom32=1.

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

    def lignesuiv(ligne):\text{def ligne\textunderscore suiv(ligne):}suiv(ligne):
    • Nous savons que, pour tout entier naturel nn : (n0)=1\binom n0=1.
    • Le premier élément de la liste sera toujours 11.

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

    suivante=\text{suivante=\lbrack1]}
    • 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=3n=3 : ligne=[1,3,3,1]\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=4n=4 : suivante=[1,4,6,4,1]\purple{\text{suivante}}=[1,\,4,\,6,\,4,\,1].

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

    • Ce sont donc les éléments 11, 22 et 33 que nous voulons calculer.

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

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

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

    for k in range(1,len(ligne)):\text{for k in range(1,len(ligne)):}
    • Nous pouvons maintenant calculer ces coefficients grâce à la formule de Pascal.
    • Par exemple, cette formule nous dit que :

    (n1)=(n111)+(n11)=(n10)+(n11)\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 11 de la liste suivante\purple{\text{suivante}} se calcule en faisant la somme des coefficients donnés par les éléments 11=01-1=0 et 11 de la liste ligne\purple{\text{ligne}}.

    • De la même façon :

    (n2)=(n121)+(n12)=(n11)+(n12)\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 22 de la liste suivante\purple{\text{suivante}} se calcule en faisant la somme des coefficients donnés par les éléments 21=12-1=1 et 22 de la liste ligne\purple{\text{ligne}}.

    • De manière générale :

    (nk)=(n1k1)+(n1k)\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 k\purple{\text{k}} de la liste suivante\purple{\text{suivante}} se calcule en faisant la somme des coefficients donnés par les éléments k1\purple{\text{k}}-1 et k\purple{\text{k}} de la liste ligne\purple{\text{ligne}}.

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

    suivante.append(ligne[k-1]+ligne[k])\text{suivante.append(ligne[k-1]+ligne[k])}
    • Nous savons que, pour tout entier naturel nn : (nn)=1\binom nn=1.
    • Nous ajoutons donc à suivante\purple{\text{suivante}} cet élément.

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

    return suivante\text{return suivante}
    • Voici l’algorithme Python de cette fonction, où nous n’oublions pas de mettre les indentations :

    1def lignesuiv(ligne):2suivante=3for k in range(1,len(ligne)):4suivante.append(ligne[k-1]+ligne[k])5suivante.append(1)6¨C11Creturn suivante\begin{aligned} \textcolor{#A9A9A9}{\text{1}}&\quad\text{def ligne\textunderscore suiv(ligne):} \ \textcolor{#A9A9A9}{\text{2}}&\quad\qquad\text{suivante=\lbrack1]} \ \textcolor{#A9A9A9}{\text{3}}&\quad\qquad\text{for k in range(1,len(ligne)):} \ \textcolor{#A9A9A9}{\text{4}}&\quad\qquad\qquad\text{suivante.append(ligne[k-1]+ligne[k])} \ \textcolor{#A9A9A9}{\text{5}}&\quad\qquad\text{suivante.append(1)} \ \textcolor{#A9A9A9}{\text{6}}&\quad\qquad\text{return suivante} \end{aligned}suiv(ligne):suivante=for k in range(1,len(ligne)):suivante.append(ligne[k-1]+ligne[k])suivante.append(1)return suivante

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

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

    Donner la liste des coefficients binomiaux pour nn 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é nn, nous souhaitons retourner la liste des coefficients binomiaux (nk)\binom nk, avec 0kn0\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 (00)=1\binom 00=1.

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

      def listecoef(n):\text{def liste\textunderscore coef(n):}coef(n):
      • Nous initialisons la variable ligne\purple{\text{ligne}}, qui sera affichée, avec la valeur de (00)=1\binom 00=1.

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

      for j in range(n):\text{for j in range(n):}
      • Nous assignons à ligne\purple{\text{ligne}} la nouvelle ligne générée par la fonction lignesuiv\purple{\text{ligne\textunderscore suiv}}suiv que nous avons programmée.

        ligne=lignesuiv(ligne)\text{ligne=ligne\textunderscore suiv(ligne)}suiv(ligne)
        • En sortie de boucle, nous affichons la liste obtenue.

        print(ligne)\text{print(ligne)}

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

        8def listecoef(n):9ligne=10for j in range(n):11ligne=lignesuiv(ligne)12print(ligne)\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{print(ligne)} \end{aligned}

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

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

        Algorithme complet

        1def lignesuiv(ligne):2suivante=3for k in range(1,len(ligne)):4suivante.append(ligne[k-1]+ligne[k])5suivante.append(1)6¨C11Creturn suivante78¨C12Cdef listecoef(n):9¨C13C¨C14Cligne=10¨C15Cnnfor j in range(n):11(n0)=1\binom n0=1¨C19Cligne=lignesuiv(ligne)12¨C20C¨C21Cprint(ligne)\begin{aligned} \textcolor{#A9A9A9}{\text{1}}&\quad\text{def ligne\textunderscore suiv(ligne):} \ \textcolor{#A9A9A9}{\text{2}}&\quad\qquad\text{suivante=\lbrack1]} \ \textcolor{#A9A9A9}{\text{3}}&\quad\qquad\text{for k in range(1,len(ligne)):} \ \textcolor{#A9A9A9}{\text{4}}&\quad\qquad\qquad\text{suivante.append(ligne[k-1]+ligne[k])} \ \textcolor{#A9A9A9}{\text{5}}&\quad\qquad\text{suivante.append(1)} \ \textcolor{#A9A9A9}{\text{6}}&\quad\qquad\text{return suivante} \ \textcolor{#A9A9A9}{\text{7}}& \ \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{print(ligne)} \end{aligned}suiv(ligne):suivante=for k in range(1,len(ligne)):suivante.append(ligne[k-1]+ligne[k])suivante.append(1)return suivantedef listecoef(n):ligne=for j in range(n):ligne=lignesuiv(ligne)print(ligne)
        • Si nous entrons liste coef(6)\purple{\text{liste \textunderscore coef(6)}}coef(6), nous aurons bien en retour :

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

          bannière astuce

          Astuce

          Si nous entrons un nn grand, par exemple 100100, 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 k\purple {\text k} concerné et en rappelant le n\purple{\text n} donné. Par exemple :

          8def listecoef(n):9ligne=10for j in range(n):11ligne=lignesuiv(ligne)12for k in range(n+1):13¨C11C¨C12Cprint(k,  parmi ,n,  : ,ligne[k])\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}