Fiche 3 : triangle de Pascal, binôme de Newton et démonstrations

Méthode

On utilise $\dbinom n0=\dbinom nn=1$ et la relation de Pascal : chaque terme est la somme des deux termes situés au-dessus de lui.

Le triangle

• ligne $0$ : $1$
• ligne $1$ : $1\ \ 1$
• ligne $2$ : $1\ \ 2\ \ 1$
• ligne $3$ : $1\ \ 3\ \ 3\ \ 1$
• ligne $4$ : $1\ \ 4\ \ 6\ \ 4\ \ 1$
• ligne $5$ : $1\ \ 5\ \ 10\ \ 10\ \ 5\ \ 1$
• ligne $6$ : $1\ \ 6\ \ 15\ \ 20\ \ 15\ \ 6\ \ 1$
• ligne $7$ : $1\ \ 7\ \ 21\ \ 35\ \ 35\ \ 21\ \ 7\ \ 1$

Lecture

✅ $\dbinom73=35$

Vérifications

Somme de la ligne $5$ : $1+5+10+10+5+1=32=2^5$ ✓

Somme de la ligne $7$ : $1+7+21+35+35+21+7+1=128=2^7$ ✓

On écrit les deux coefficients avec les factorielles :

On met au même dénominateur $(k+1)!\,(n-k)!$. On utilise $(k+1)!=(k+1)\,k!$ et $(n-k)!=(n-k)\,(n-k-1)!$.

Comme $(n+1)-(k+1)=n-k$, c'est exactement $\dbinom{n+1}{k+1}$.

✅ $\dbinom nk+\dbinom n{k+1}=\dbinom{n+1}{k+1}$ ∎

Soit $E=\{1{,}2,\dots,n+1\}$. Le nombre de parties de $E$ à $k+1$ éléments est $\dbinom{n+1}{k+1}$. On les compte en séparant deux cas disjoints, selon que la partie contient ou non l'élément $n+1$.

Cas 1 : la partie contient $n+1$. Il faut choisir les $k$ autres éléments parmi les $n$ éléments $\{1,\dots,n\}$. Il y a $\dbinom nk$ parties.

Cas 2 : la partie ne contient pas $n+1$. Il faut choisir les $k+1$ éléments parmi $\{1,\dots,n\}$. Il y a $\dbinom n{k+1}$ parties.

Les deux cas sont disjoints et couvrent toutes les possibilités.

✅ $\dbinom{n+1}{k+1}=\dbinom nk+\dbinom n{k+1}$ ∎

Question 1

Soit $E$ un ensemble à $n$ éléments.

Chaque partie de $E$ a un cardinal $k$ compris entre $0$ et $n$.

Il y en a $\dbinom nk$ de cardinal $k$.

En sommant sur $k$, le nombre total de parties est $\displaystyle\sum\binom nk$.

Or $E$ a $2^n$ parties (chaque élément est dans la partie ou non).

✅ $\displaystyle\sum_{k=0}^n\binom nk=2^n$ ∎

Question 2

D'après la formule du binôme avec $a=1$ et $b=-1$ :

Pour $n\ge1$, $0^n=0$.

✅ $\displaystyle\sum_{k=0}^n(-1)^k\binom nk=0$ ∎

Question 3

Notons $P$ la somme des $\dbinom nk$ pour $k$ pair. Notons $I$ la somme des $\dbinom nk$ pour $k$ impair. La question 1 donne $P+I=2^n$. La question 2 donne $P-I=0$. Donc $P=I=\dfrac{2^n}2$.

✅ $P=I=2^{n-1}$ ∎

Pour $n=5$ : $16$ parties de cardinal pair et $16$ de cardinal impair.

Méthode

On utilise $(a+b)^n=\displaystyle\sum\binom nk\,a^{n-k}\,b^k$.

Question 1

Avec la ligne $4$ du triangle ($1\ 4\ 6\ 4\ 1$) :

✅ $(x+1)^4=x^4+4x^3+6x^2+4x+1$

Avec la ligne $5$ ($1\ 5\ 10\ 10\ 5\ 1$), $a=2x$ et $b=-1$ :

$(2x-1)^5=(2x)^5-5(2x)^4+10(2x)^3-10(2x)^2+5(2x)-1$

✅ $(2x-1)^5=32x^5-80x^4+80x^3-40x^2+10x-1$

Question 2

Le terme général de $(x+2)^6$ est $\dbinom6k\,x^{6-k}\,2^k$. Le degré $3$ correspond à $6-k=3$, donc $k=3$. $\dbinom63\times2^3=20\times8$.

✅ Le coefficient de $x^3$ est $160$.

Question 3

Le terme général de $\left(x+\dfrac1x\right)^6$ est $\dbinom6k\,x^{6-k}\left(\dfrac1x\right)^k=\dbinom6k\,x^{6-2k}$. Il est constant si $6-2k=0$, donc $k=3$.

✅ Le terme constant est $\dbinom63=20$.

Méthode

On reconnaît la formule du binôme avec $a=1$ : $(1+b)^n=\displaystyle\sum\binom nk\,b^k$.

Question 1

Avec $b=2$ : $\displaystyle\sum\binom nk2^k=(1+2)^n$

✅ $3^n$

Question 2

Avec $b=3$ : $\displaystyle\sum\binom nk3^k=(1+3)^n$

✅ $4^n$

Question 3

Avec $b=-2$ : $\displaystyle\sum\binom nk(-2)^k=(1-2)^n$

✅ $(-1)^n$

Contrôle pour $n=3$ : $1-6+12-8=-1=(-1)^3$ ✓

Question 1

✅ $k\dbinom nk=n\dbinom{n-1}{k-1}$ ∎

Question 2

Le terme $k=0$ est nul. D'après la question 1 :

d'après la somme des coefficients pour l'entier $n-1$.

✅ $\displaystyle\sum_{k=0}^nk\binom nk=n\times2^{n-1}$ ∎

Pour $n=4$ : $0+4+12+12+4=32=4\times2^3$ ✓

Question 3

Comptons les comités (parties de $\{1,\dots,n\}$) munis d'un président (un membre du comité désigné).

Première façon : on choisit un comité de $k$ membres ($\dbinom nk$ façons), puis son président ($k$ façons). En sommant sur $k$, on obtient $\displaystyle\sum k\binom nk$.

Seconde façon : on choisit d'abord le président ($n$ façons). Puis on décide pour chacun des $n-1$ autres membres s'il est dans le comité ou non ($2^{n-1}$ façons).

Les deux comptages sont égaux.

✅ $\displaystyle\sum k\binom nk=n\,2^{n-1}$ ∎

Soit $E$ un ensemble de $2n$ éléments. Il est partagé en deux ensembles disjoints $A$ et $B$ de $n$ éléments chacun. On compte les parties $S$ de $E$ à $n$ éléments.

Première façon : il y en a $\dbinom{2n}n$.

Seconde façon : on classe les parties $S$ selon $k=|S\cap A|$, avec $0\le k\le n$. Une telle partie est déterminée par :

• le choix de $k$ éléments de $A$ : $\dbinom nk$ façons ;
• le choix de $n-k$ éléments de $B$ : $\dbinom n{n-k}=\dbinom nk$ façons.

Il y a donc $\dbinom nk^2$ parties pour chaque $k$. En tout : $\displaystyle\sum\binom nk^2$.

Les deux comptages sont égaux.

✅ $\displaystyle\sum_{k=0}^n\binom nk^2=\binom{2n}n$ ∎

Vérification pour $n=3$ : $1^2+3^2+3^2+1^2=20=\dbinom63$ ✓

Question 1

def pascal(n):
    ligne = [1]
    for i in range(n):
        nouvelle = [1]
        for k in range(len(ligne) - 1):
            nouvelle.append(ligne[k] + ligne[k + 1])
        nouvelle.append(1)
        ligne = nouvelle
    return ligne

Pour chaque nouvelle ligne, on ajoute deux $1$ aux extrémités. Entre eux, on met les sommes de termes consécutifs de la ligne précédente. pascal(6) renvoie [1, 6, 15, 20, 15, 6, 1].

Question 2

from math import comb

for n in range(1, 11):
    l = pascal(n)
    assert sum(l) == 2**n
    assert sum(c**2 for c in l) == comb(2*n, n)

Aucune erreur n'est levée : les deux identités sont vérifiées pour $n$ de $1$ à $10$.

Attention : un test sur quelques valeurs ne remplace pas une démonstration. Mais il permet de détecter une erreur de formule.