(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/
Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.
Génération des coefficients binomiaux par la formule de Pascal, et propriétés des coefficients binomiaux.
Dans cette partie, nous étudierons le "triangle arithmétique" décrit par Blaise Pascal dans son traité paru en 1655, pour ensuite implémenter en Python la construction de ce triangle.
1.1. Suivre la vidéo suivante.
1.2. Tester la syntaxe Python fournie ci-dessous, qui permet de générer un tableau carré de dimension $N \times N$.
# Tester cette cellule
import numpy as np
N = 12 #nombre de lignes et de colonnes du tableau
T = np.array( [ [0 for k in range(N)] for n in range(N)] )
T
1.3. Écrire une fonction Python Pascal qui reçoit en argument un entier N et qui renvoie le tableau de dimension $N \times N$ contenant le triangle de Pascal, c'est à dire tel que le coefficient de la $n$ème ligne et de la $k$ème colonne sera $\begin{pmatrix} n \\ k \end{pmatrix}$
# Écrire ici la fonction Pascal
1.4. Effectuer un appel à la fonction Python Pascal avec $N=12$.
# Effectuer ici l'appel à la fonction
Dans cette partie, à l'aide de la relation de Pascal, nous construirons une formule des calculs des combinaisons basée sur la notion de factorielle.
2.1. Pour tout entier $n \geq 0$, on appelle factorielle de $n$ et on note $n!$ l'entier défini par :
$$n! = \left\{ \begin{array}{ll} 1 & \mbox{si } n =0 \\ 1 \times 2 \times ... \times n & \mbox{sinon.} \end{array} \right.$$$\quad$Écrire une fonction fact qui reçoit en argument un entier $n \geq 0$ et renvoie la valeur de $n!$ .
$\quad$Tester ensuite la fonction pour calculer $0!$ ; $3!$ et $6!$ .
# Écrire ici la fonction fact
# Utiliser cette cellule pour tester la fonction fact
2.2. Voici des extraits du traité de Pascal qui lui permettent de construire son triangle :
$\quad$Sous forme moderne, ces relations peuvent s'écrire :
$\quad$À l'aide de ces relations, démontrer par récurrence que : $$\forall \; n \geq 0 \;\;;\; \forall \; 0 \leq k \leq n \;\;;\;\; \color{#FF7F27}{ \begin{pmatrix} n \\ k \end{pmatrix}} = \color{#FF7F27}{ \frac{n!}{k!(n-k)!} }$$
$\quad$Note : Pascal avait déjà connaissance de cette méthode de calcul :
2.3. À l'aide de la fonction fact définie précédemment, écrire une fonction Python Combinaison qui reçoit en argument $n$ et $k$ et qui renvoie la valeur de $\begin{pmatrix} n \\ k \end{pmatrix}$.
# Écrire ici la fonction Combinaison
2.4. Effectuer un appel à votre fonction Combinaison pour calculer $\begin{pmatrix} 11 \\ 4 \end{pmatrix}$.
# Utiliser cette cellule pour tester la fonction Combinaison
Dans cette partie, nous nous intéresserons à des propriétés du triangle arithmétique que Pascal cite dans son traité, et en donnerons les formules équivalentes sous forme moderne.
Nous démontrerons les plus simples, et vérifierons simplement la validité des autres pour des valeurs particulières.
3.1. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peut s'écrire :
$$ \forall \; n \geq 1 \;\;;\; \forall \; 0 \leq k \leq n-1 \;\;; \color{#00B050}{\;\; \begin{pmatrix} n \\ k \end{pmatrix} \;}=\color{#00B050}{\; \sum\limits_{j=0}^{k} \begin{pmatrix} n-1-k+j \\ j \end{pmatrix} } $$$\quad$ Exécuter la cellule ci-dessous, qui permet de vérifier la validité de cette formule pour des valeurs particulières de $n$ et $k$.
# Exécuter cette cellule pour vérifier la formule dans un cas particulier
n=8
k=5
a = Combinaison(n,k)
b = sum( [ Combinaison(n-1-k+j,j) for j in range(k+1) ])
a,b
3.2. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peut s'écrire :
$$ \forall \; n \geq 1 \;\;;\; \forall \; 1 \leq k \leq n \;\;; \color{#FF7F27}{ \;\; \begin{pmatrix} n \\ k \end{pmatrix} } \;=\; \color{#FF7F27}{ \sum\limits_{j=0}^{n-k} \begin{pmatrix} n-j-1 \\ k-1 \end{pmatrix} }$$$\quad$ Proposer ci-dessous une saisie Python permettant de vérifier cette formule pour des valeurs particulières de $n$ et $k$.
$\quad\;$On pourra s'inspirer des syntaxes fournies dans la question 3.1.
# Proposer ici une vérification de la formule dans un cas particulier
n=8
k=5
3.3. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peut s'écrire :
$$ \forall \; n \geq 1 \;\;;\; \forall \; 1 \leq k \leq n-1 \;\;; \color{#00A2E8}{\;\; \begin{pmatrix} n \\ k \end{pmatrix} }\;-1=\color{#00A2E8}{ \sum\limits_{j=0}^{k-1} \sum\limits_{m=j}^{n-1-k+j} \begin{pmatrix} m \\ j \end{pmatrix}}$$$\quad$ Exécuter la cellule ci-dessous, qui permet de vérifier la validité de cette formule pour des valeurs particulières de $n$ et $k$.
n=8
k=5
a = Combinaison(n,k) -1
b = sum ( [sum( [ Combinaison(m,j) for m in range(j,n-k+j) ]) for j in range(k) ] )
a,b
3.4. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peut s'écrire :
$$ \forall \; n \geq 0 \;\;;\; \forall \; 0 \leq k \leq n \;\;; \color{#BF8F00}{\;\; \begin{pmatrix} n \\ k \end{pmatrix}} \;=\;\color{#BF8F00}{ \begin{pmatrix} n \\ n-k \end{pmatrix} }$$$\quad$ Démontrer cette propriété.
3.5. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peut s'écrire :
$$ \forall \; n \geq 1 \;\;; \color{#8080FF}{\; \sum\limits_{k=0}^{n} \begin{pmatrix} n \\ k \end{pmatrix} }\;= 2 \times \color{#404080}{ \sum\limits_{j=0}^{n-1} \begin{pmatrix} n-1 \\ j \end{pmatrix} }$$$\quad$ a. Proposer ci-dessous une saisie Python permettant de vérifier cette formule pour une valeur particulière de $n$.
$\quad\quad$On pourra s'inspirer des syntaxes fournies dans la question 3.1.
# Proposer ici une vérification de la formule dans un cas particulier
n=6
$\quad$b. En décomposant sous la forme :
$$\begin{matrix} {2\times \sum\limits_{j=0}^{n-1}\begin{pmatrix}n-1\\j\end{pmatrix}} & = & \begin{pmatrix}n-1\\0\end{pmatrix}+ & \begin{pmatrix}n-1\\1\end{pmatrix}+ & ...+ & \begin{pmatrix}n-1\\n-2\end{pmatrix}+ & \begin{pmatrix}n-1\\n-1\end{pmatrix} & {} \\ { } & {} & + & \begin{pmatrix}n-1\\0\end{pmatrix}+ & ...+ & \begin{pmatrix}n-1\\n-3\end{pmatrix}+ & \begin{pmatrix}n-1\\n-2\end{pmatrix}+ & \begin{pmatrix}n-1\\n-1\end{pmatrix} \end{matrix}$$$\quad\;\;\;$et en regroupant les termes par deux, démontrer la formule annoncée.
$\quad$ c. En déduire que la suite de terme général $\sum\limits_{k=0}^{n} \begin{pmatrix} n \\ k \end{pmatrix}$ est géométrique, en précisant son premier terme et sa raison.
$\quad\quad$ Donner ensuite l'expression de $\sum\limits_{k=0}^{n} \begin{pmatrix} n \\ k \end{pmatrix}$ en fonction de $n$. Ce résultat est énoncé ainsi par Pascal :
$\quad$ d. Déduire de la question précédente que $\forall \; n \geq 1 \;\;;\; \color{#8080FF}{\sum\limits_{k=0}^{n} \begin{pmatrix} n \\ k \end{pmatrix} }-1 = \color{#00A2E8}{\sum\limits_{m=0}^{n-1} \sum\limits_{k=0}^{m} \begin{pmatrix} m \\ k \end{pmatrix}} $. Ce résultat est énoncé ainsi par Pascal :
3.6. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peut s'écrire :
$$\ \forall \; n \geq 1 \;\;;\; \forall \; 1 \leq K \leq n-1 \;\;; \color{#C65911}{\;\; \sum\limits_{k=0}^{K} \begin{pmatrix} n \\ k \end{pmatrix} }\;=\; \color{#2F75B5}{ \sum\limits_{k=0}^{K} \begin{pmatrix} n-1 \\ k \end{pmatrix}}\;+\;\color{#00B0F0}{ \sum\limits_{k=0}^{K-1} \begin{pmatrix} n-1 \\ k \end{pmatrix} }$$$\quad$ Vérifier que cette propriété est correcte pour $n=6$ et $K=3$ (cellules représentées sur l'illustration).
3.7. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peuvt s'écrire :
$$ \forall \; k \geq 1 \;\;; \color{#FF7F27}{\;\; \begin{pmatrix} 2k \\ k \end{pmatrix} }\;= 2 \times \color{#FFAEC9}{\begin{pmatrix} 2k-1 \\ k \end{pmatrix}}\;= 2 \times \color{#FFC90E}{ \begin{pmatrix} 2k-1 \\ k-1 \end{pmatrix} }$$$\quad$ Démontrer cette propriété.
3.8. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peut s'écrire :
$$\forall \; n \geq 1 \;\;;\; \forall \; 1 \leq k \leq n \;\;;\quad \frac{ \color{#0070C0}{\begin{pmatrix} n \\ k \end{pmatrix}} }{ \color{#22B14C}{\begin{pmatrix} n \\ k-1 \end{pmatrix}} } = \frac{ \color{#0070C0}{n-k+1} }{ \color{#22B14C}{k} }$$$\quad$ Démontrer cette propriété.
3.9. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peut s'écrire :
$$\forall \; n \geq 1 \;\;;\; \forall \; 1 \leq k \leq n \;\;;\quad \frac{ \color{#0070C0}{\begin{pmatrix} n \\ k \end{pmatrix}} }{ \color{#22B14C}{\begin{pmatrix} n-1 \\ k \end{pmatrix}} } = \frac{ \color{#0070C0}{n} }{ \color{#22B14C}{n-k} }$$$\quad$ Démontrer cette propriété.
3.10. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peut s'écrire :
$$\forall \; n \geq 1 \;\;;\; \forall \; 1 \leq k \leq n \;\;;\quad \frac{ \color{#0070C0}{\begin{pmatrix} n \\ k \end{pmatrix}} }{ \color{#22B14C}{\begin{pmatrix} n-1 \\ k-1 \end{pmatrix}} } = \frac{ \color{#0070C0}{n} }{ \color{#22B14C}{k} }$$$\quad$ Démontrer cette propriété.
3.11. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peut s'écrire :
$$\forall \; n \geq 1 \;\;;\; \forall \; 1 \leq k \leq n \;\;;\quad \frac{ \color{#0070C0}{ \sum\limits_{j=0}^{k} \begin{pmatrix} n-k+j \\ j \end{pmatrix}} }{ \color{#22B14C}{\begin{pmatrix} n \\ k \end{pmatrix}} } = \frac{ \color{#0070C0}{n+1} }{ \color{#22B14C}{n+1-k} }$$$\quad$ Exécuter la cellule ci-dessous, qui permet de vérifier la validité de cette formule pour des valeurs particulières de $n$ et $k$.
# Exécuter cette cellule pour vérifier la formule dans un cas particulier
n=9
k=3
a = sum( [ Combinaison(n-k+j,j) for j in range(k+1) ] ) / Combinaison(n,k)
b = (n+1)/(n+1-k)
a,b
3.12. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peut s'écrire :
$$\forall \; n \geq 1 \;\;;\; \forall \; 0 \leq k \leq n-1 \;\;;\quad \frac{ \color{#0070C0}{ \sum\limits_{j=0}^{k+1} \begin{pmatrix} n-j \\ k+1-j \end{pmatrix}} }{ \color{#22B14C}{ \sum\limits_{j=0}^{k} \begin{pmatrix} n-j \\ k-j \end{pmatrix}} } = \frac{ \color{#0070C0}{n+1-k} }{ \color{#22B14C}{k+1} }$$$\quad$ Exécuter la cellule ci-dessous, qui permet de vérifier la validité de cette formule pour des valeurs particulières de $n$ et $k$.
# Exécuter cette cellule pour vérifier la formule dans un cas particulier
n=7
k=3
a = sum( [ Combinaison(n-j,k+1-j) for j in range(k+2) ] ) / sum( [ Combinaison(n-j,k-j) for j in range(k+1) ] )
b = (n+1-k)/(k+1)
a,b
3.13. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peut s'écrire :
$$\forall \; n \geq 1 \;\;;\; \forall \; 0 \leq k \leq n-1 \;\;;\quad \frac{ \color{#22B14C}{ \sum\limits_{m=k}^{n} \begin{pmatrix} m \\ k \end{pmatrix}} }{ \color{#0070C0}{ \sum\limits_{j=0}^{k} \begin{pmatrix} n-j \\ k-j \end{pmatrix}} } = \frac{ \color{#22B14C}{n+1-k} }{ \color{#0070C0}{k+1} }$$$\quad$ Proposer ci-dessous une saisie Python permettant de vérifier cette formule pour des valeurs particulières de $n$ et $k$.
$\quad\;$On pourra s'inspirer des syntaxes fournies dans la question 3.12.
# Proposer ici une vérification de la formule dans un cas particulier
n=7
k=4
3.14. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peut s'écrire :
$$\forall \; n \geq 1 \;\;;\; \forall \; 0 \leq k \leq n \;\;;\quad \frac{ \color{#0070C0}{ \sum\limits_{j=0}^{n-k} \begin{pmatrix} n-j \\ n-k-j \end{pmatrix}} }{ \color{#22B14C}{ \sum\limits_{j=0}^{k} \begin{pmatrix} n-j \\ k-j \end{pmatrix}} } = \frac{ \color{#0070C0}{n+1-k} }{ \color{#22B14C}{k+1} }$$$\quad$ Proposer ci-dessous une saisie Python permettant de vérifier cette formule pour des valeurs particulières de $n$ et $k$.
$\quad\;$On pourra s'inspirer des syntaxes fournies dans la question 3.12.
# Proposer ici une vérification de la formule dans un cas particulier
n=9
k=2
3.15. Extrait du traité de Pascal:
$\quad$ Sous forme moderne, cette propriété peut s'écrire :
$$ \forall \; k \geq 1 \;\;;\quad \frac{ \color{#22B14C}{ \begin{pmatrix} 2k \\ k \end{pmatrix}} }{ 4 \times \color{#0070C0}{ \begin{pmatrix} 2(k-1) \\ k-1 \end{pmatrix}} } = \frac{ \color{#22B14C}{2k-1} }{ \color{#0070C0}{2k} }$$$\quad$ Exécuter la cellule ci-dessous, qui permet de vérifier la validité de cette formule pour une valeur particulière de $k$.
# Exécuter cette cellule pour vérifier la formule dans un cas particulier
k=3
a = Combinaison(2*k,k) / (4*Combinaison(2*k-2,k-1))
b = (2*k-1)/(2*k)
a,b
(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/