Sierpiński et Pascal sont dans un triangle

Dans cet article, nous allons évoquer le triangle de Sierpinski, le triangle de Pascal, un lien qui les unit, un théorème de Lucas, une démonstration due à un certain N.J. Fine ainsi qu’une illustration de tout cela dans Minecraft. Rien que ça.

Triangle de Sierpiński

Si vous êtes amateur de fractales, vous avez sans doute déjà vu un triangle de Sierpiński. Pour ceux qui ne connaîtraient pas, voici une petite explication.

Prenez un triangle équilatéral « plein » (que nous appellerons $S_0$ ). Ôtez-lui le petit triangle formé en joignant les milieux des trois côtés comme montré ci-dessous. On appelle $S_1$ le triangle à trou obtenu :

Recommencez ce même processus avec chacun des triangles « pleins » restants:

Le triangle troué obtenu après $n$ itérations sera noté $S_n$ . Par exemple, pour $n=7$ , voici la figure qui apparaît:

Et lorsque vous itérez une infinité de fois ce processus, vous obtenez ce qu’on appelle le triangle de Sierpiński (du nom du mathématicien qui l’a découvert).

Triangle de Pascal

Vous avez sans doute aussi entendu parlé du triangle de Pascal. Rappelons tout de même de quoi il s’agit en introduisant quelques notations.

Si $n$ et $k$ sont deux entiers naturels, la notation ${n \choose k}$ désigne le nombre de parties à $k$ éléments dans un ensemble à $n$ éléments. De manière peut-être plus parlante, c’est le nombre de façons de choisir un groupe de $k$ personnes dans un groupe de $n$ personnes. Rappelons comment sont calculés les nombres ${n \choose k}$ :

Soit en utilisant la formule ${n \choose k}=\dfrac{n!}{k!(n-k)!}$ ;
Soit par récurrence, en utilisant la formule de Pascal: ${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$

Une façon élégante de représenter ces nombres (aussi appelés coefficients binomiaux) est de les placer dans un triangle, qu’on appelle triangle de Pascal, de la manière suivante:

Dans la première ligne, on place le nombre ${0 \choose 0}$
Dans le deuxième ligne, on place les nombres ${1 \choose 0}$ et ${1 \choose 1}$
Dans la troisième ligne, on place les nombres ${2 \choose 0}$ , ${2 \choose 1}$ et ${2 \choose 2}$
…
Dans la $n+1$ -ème ligne, on place les nombres ${n \choose 0}$ , ${n \choose 1}$ , … , ${n \choose n}$

Tous ces nombres sont placés de façon à former un triangle. Par exemple, le triangle obtenu pour $n=5$ est le suivant:

Nous noterons $P_5$ ce triangle. Plus généralement, le triangle de Pascal obtenu en allant jusqu’à l’entier $n$ sera noté $P_n$ . Il contient donc $n+1$ lignes.

Après calculs, voilà ce que donne le triangle de Pascal $P_5$ :

Quand Pascal rencontre Sierpiński

Reprenons nos triangles de Sierpiński et superposons-les avec nos triangles de Pascal:

Comme on peut le voir, tous les petits triangles de $S_n$ sont occupés par des coefficients binomiaux impairs. Et aucun coefficient impair n’est en dehors d’un petit triangle.

Nous constatons donc que pour tout $n\geq 1$ , le triangle $S_n$ correspond au triangle de Pascal $P_{2^n-1}$ dans lequel on a retiré tous les coefficients binomiaux qui sont pairs. Génial, non ? Moi, je trouve ça superbe. (Bon c’est vrai que nous ne l’avons pas prouvé mathématiquement mais nous l’admettrons ici…)

Dessinons de beaux triangles de Sierpiński…

Le constat précédent nous donne donc un moyen pratique de dessiner le triangle de Sierpiński $S_n$ : il suffit de découper un triangle équilatéral en de petits triangles équilatéraux ( de sorte que chaque côté du grand triangle équilatéral soit découpé en $2^n$ parts égales), de superposer le triangle de Pascal $P_{2^n-1}$ puis de noircir les petits triangles qui correspondent à des coefficients binomiaux impairs.

Voici une illustration de ceci dans Minecraft, où on a représenté le triangle $S_{7}$ à l’aide du triangle de Pascal $P_{127}$ et d’un algorithme basé sur ce principe de parité des coefficients binomiaux:

Je n’ai pas posé moi-même ces milliers de blocs (2187 si mes calculs sont exacts), j’ai juste utilisé une petite tortue dans laquelle j’ai entré un programme puis je l’ai laissée travailler toute seule, comme une grande…

Le théorème de Lucas

Le seul souci avec cette méthode de construction des triangles de Sierpiński à l’aide des coefficients binomiaux, c’est que ces derniers peuvent être assez grands et donc difficiles à calculer. Par exemple, dans le triangle représenté dans Minecraft ci-dessus, il aurait fallu calculer à un moment ${127 \choose 56}$ qui est de l’ordre de $5.10^{36}$ . Pas très pratique tout ça, surtout quand on sait que ce n’est pas le seul coefficient binomial qu’il faudrait calculer pour réaliser cette construction…

Comment remédier à ce souci ? Puisqu’il n’y a que la parité du nombre ${n \choose k}$ qui nous intéresse, on peut être plus astucieux et s’éviter le calcul complet de ce nombre. En fait, l’astuce vient d’un théorème qu’on doit au mathématicien français du 19ème siècle nommé Édouard Lucas:

Si $\displaystyle{ n=\sum_{i=0}^{m}a_i 2^i }$ et $k=\displaystyle{ \sum_{i=0}^{m} b_i 2^i}$ sont les écritures de $n$ et $k$ en base 2 (avec éventuellement des zéros à gauche de façon à ce que ces deux écritures contiennent le même nombre $m$ de chiffres) alors:

${n \choose k} \equiv {a_m \choose b_m} ... {a_ 1 \choose b_1} {a_0 \choose b_0} \mod(2)$

Donnons tout de suite un exemple pour clarifier les choses. On veut savoir si le coefficient ${14 \choose 5}$ est pair, sans avoir à le calculer.

1) On commence par déterminer la décomposition de ces deux nombres en base 2:

$n=14= 1110$ en base 2
$k=5=101$ en base 2

2) Puis, on fait en sorte que ces deux nombres aient le même nombre de chiffres en base 2 en rajoutant des zéros à gauche si besoin: on a donc $n=1110$ et $k=0101$ .

3) On forme les coefficients binomiaux obtenus en prenant successivement chaque chiffre de $n$ et $k$ . Par exemple, le premier chiffre de $n$ en partant de la gauche est 1 et le premier chiffre de $k$ est 0. On calcule donc le coefficient binomial ${1 \choose 0}$ . On fait de même avec le deuxième chiffre de $n$ et $k$ : on doit donc calculer ${1 \choose 1}$ . Les troisièmes et quatrièmes chiffres donneront respectivement les coefficients ${1 \choose 0}$ et ${0 \choose 1}$ . Le théorème de Lucas nous dit que ${14 \choose 5}$ aura la même parité que le produit:

${14 \choose 5} \equiv {1 \choose 0} {1 \choose 1} {1 \choose 0} {0 \choose 1} \mod(2)$

4) On calcule le produit ${1 \choose 0} {1 \choose 1} {1 \choose 0} {0 \choose 1}$ . Or ${1 \choose 0}=1$ , ${1 \choose 1}=1$ , ${1 \choose 0}=1$ et ${0 \choose 1}=0$ (car il y a zéro façons de choisir 1 élément dans un ensemble à 0 élément !). Ainsi, le produit vaut $1 \times 1 \times 1 \times 0=0$ . D’après le théorème de Lucas, ${14 \choose 5} \equiv 0 \mod(2)$ . C’est donc un nombre pair ! (Pour vérification, ${14 \choose 5}=2002$ , qui est bien pair).

En fait, on remarque que dès qu’il y a un rang pour lequel le chiffre de $k$ est strictement supérieur au chiffre de $n$ alors le coefficient ${0 \choose 1}=0$ apparaîtra dans le produit, et ce produit sera donc nul. Ainsi, une façon plus commode d’utiliser le théorème de Lucas est de représenter les écritures de $n$ et $k$ en base 2 dans un tableau en alignant les chiffres et s’il y a une colonne où le chiffre de $k$ est strictement supérieur au chiffre de $n$ , alors ${n \choose k}$ sera pair. Sinon, il est impair.

Par exemple, pour savoir si le coefficient ${24 \choose 9}$ est pair, on aligne les écritures de 24 et 9 en base 2:

$\begin{array}{c|ccccc|} n=24 & 1 & 1 & 0 & 0 & 0 \\ \hline k=9 & 0 & 1 & 0 & 0 & 1 \\ \hline \end{array}$

On voit qu’il y a une colonne dans laquelle le chiffre de $k$ est strictement supérieur au chiffre de $n$ (la dernière colonne) donc on en déduit que ${24 \choose 9}$ est pair ! (ce qui est bel et bien vrai car ${24 \choose 9}=1 207 504$ )

Everything is Fine

En fait, le théorème de Lucas est vrai même en base $p$ où $p$ est un nombre premier. Mais nous allons le montrer uniquement pour $p=2$ (la démonstration étant identique dans le cas général…). La (très élégante) démonstration que nous allons donner suit une démonstration donnée par un certain N.J. Fine en 1947. Mais avant cela, rappelons deux ou trois bricoles.

Dans toute la suite, nous allons raisonner modulo 2. Raisonner modulo 2, ça veut dire que chaque fois qu’il y a un nombre pair, on peut le remplacer par 0 et chaque fois qu’il y a un nombre impair, on peut le remplacer par 1. Hormis cela, tous les autres calculs se font de la même manière que les calculs dont vous avez l’habitude.

Commençons par une petite propriété très utile quand on raisonne modulo 2: si $a$ et $b$ sont deux nombres entiers, alors $(a+b)^2 \equiv a^2 + b^2 \mod(2)$ . Cela vient du fait que $(a+b)^2=a^2+2.ab +b^2$ et du fait que le terme $2ab$ vaut 0 modulo 2 (car c’est un nombre pair). Dans la suite, nous nous passerons du symbole $\equiv$ et nous noterons $(a+b)^2 = a^2 + b^2$ tout en se souvenant qu’on raisonne modulo 2. On en déduit facilement par récurrence, que pour tout entier naturel $i$ , $(a+b)^{2^i}=a^{2^i} + b^{2^i}$ . Bon, cela étant dit, passons aux choses (très) sérieuses.

Pour prouver le théorème de Lucas, nous allons écrire de deux façons différentes un même polynôme calculé modulo 2 puis identifier les coefficients. Ce polynôme en question, c’est $(1+X)^n$ .

D’une part, la formule du binôme de Newton nous donne:

$\displaystyle (1+X)^n = \sum_{k=0}^{n} {n \choose k}X^k$

D’autre part, en utilisant la décomposition de $n$ en base 2 et la petite propriété décrite plus haut, on obtient:

Ainsi, nous avons démontré l’égalité:

Maintenant, prenons $k$ un entier compris entre $0$ et $n$ .

Dans le polynôme de gauche, le coefficient du terme de degré $k$ est évidemment ${n \choose k}$ .
Dans le polynôme de droite, le coefficient de degré $k$ est obtenu pour tous les $m$ -uplets $(j_0,j_1,\cdots,j_m)$ tels que $k=\sum_{i=0}^{m} j_i 2^i$ . Par unicité de la décomposition d’un entier en base 2, il n’y a qu’un seul tel $m$ -uplet, et il s’agit de $(b_0,b_1, \cdots, b_m)$ où les $b_i$ sont les chiffres de $k$ en base 2. On en déduit que le coefficient de degré $k$ du polynôme de droite est ${a_0 \choose b_0} {a_1 \choose b_1} \cdots {a_m \choose b_m}$ .

Par identification, nous en déduisons donc que l’égalité suivante est vraie modulo 2:

${n \choose k} = {a_0 \choose b_0} {a_1 \choose b_1} \cdots {a_m \choose b_m}$

Voilà, nous avons bien prouvé le théorème de Lucas ! J’ai mis cette même preuve dans un pdf (car je trouve ça plus propre quand c’est dans un seul et même fichier… T.O.C.) :

Theoreme_de_Lucas

Et en programme ça donne quoi ?

Disons que vous voulez savoir si ${n \choose k}$ est pair ou non. Voici un programme possible (en Lua) qui, après avoir entré $n$ et $k$ affiche 0 si le coefficient binomial est pair, et 1 sinon. (J’ai utilisé cette partie de code pour réaliser le triangle de Sierpinski dans Minecraft posté plus haut)


local parite=1

while(n>0 and k>0) do

-- Si le chiffre de droite de n est plus grand ou égal
-- à celui de k, on le supprime:

     if( (n%2)>=(k%2) ) then

          n = (n-n%2)/2
          k = (k-k%2)/2

-- Sinon, on peut s'arrêter car
-- le coefficient binomial
-- sera forcément pair dans ce cas

     else
          parite=0
          n=0
     end

end

print(parite)

A vous de dessiner des triangles de Sierpinski maintenant.

Notes:

La démonstration originale de N.J. Fine.
Un joli site (que je viens de découvrir après l’écriture de cet article) où on peut visualiser de magnifiques triangles de Sierpinski-Pascal (et pas nécessairement modulo 2 !)

Publicités

3 commentaires pour Sierpiński et Pascal sont dans un triangle

kikoolol dit :

18 août 2014 à 21 h 14 min

Voici un lien pour dessiner un beau triangle en LaTeX : http://www.texample.net/tikz/examples/pascals-triangle-and-sierpinski-triangle/

Réponse
- blogdemaths dit :
  
  18 août 2014 à 22 h 17 min
  
  J’avais fait ça sous Geogebra à l’époque… mais c’est tellement plus beau avec Tikz! Merci du lien 😉
  
  Réponse
Ping : Triangulando: Pascal versus Sierpinski - Cuaderno de Cultura Científica

Laisser un commentaire Annuler la réponse.

Entrez votre commentaire...

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

E-mail (adresse strictement confidentielle)

Nom

Site web

Vous commentez à l'aide de votre compte WordPress.com. ( Déconnexion / Changer )

Vous commentez à l'aide de votre compte Google+. ( Déconnexion / Changer )

Vous commentez à l'aide de votre compte Twitter. ( Déconnexion / Changer )

Vous commentez à l'aide de votre compte Facebook. ( Déconnexion / Changer )

Annuler

Connexion à %s