Suite de pliage de papier

Construction récursive.

En mathématiques, et notamment en combinatoire des mots, la suite de pliage de papier régulière, connue aussi sous le nom de suite de la courbe du dragon, est une suite automatique composée de 0 et de 1. Les premiers termes de la suite sont :

0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, . . . (c'est la Modèle:OEIS)

Le nom provient de la construction suivante : si l'on prend une bande de papier que l'on plie en deux, toujours dans le même sens (à gauche par exemple), la forme résultante présente une suite de changements de direction que l'on peut coder par G pour gauche et D pour droite. On obtient alors la suite :

G

G G D

G G D G G D D

G G D G G D D G G G D D G D D

G G D G G D D G G G D D G D D G G G D G G D D D G G D D G D D etc.

. . .

Bande de papier pliée 3 fois puis dépliée et montrant 7 pliures de directions variables. La dernière illustration montre la génération par symétrie des pliures pour 4 pliages.

Chaque ligne est obtenue, à partir de la précédente, en commençant par écrire la ligne précédente, puis en lui ajoutant un G au bout (extrémité droite) et enfin en recopiant la ligne précédente en la lisant de droite à gauche et en échangeant systématiquement chaque G et chaque D.

Les suites successives sont : G, GGD, GGDGGDD, GGDGGDDGGGDDGDD, etc

La régularité dans le nom réfère au fait que l'on plie la bande toujours dans le même sens. Lorsque l'on déplie la bande, la figure s'approche de la courbe du dragon.

La suite de 0 et 1 donnée plus haut s'obtient en replaçant G par 0 et D par 1. Si on remplace au contraire G par 1 et D par 0, on obtient la suite « duale » :

1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, ... (c'est la Modèle:OEIS)

Définitions équivalentes

Définition formelle

Soit $(w_n)$ la suite de mots sur $\{0,1\}$ définie par :

• $w_0=\epsilon$ (le mot vide)
• $w_{n+1}=w_{n}0{w_n}^{\prime }$, où $x^{\prime }$ désigne le mot obtenu en prenant le retourné de $x$, et en échangeant les $0$ et les $1$.

Les premiers mots de la suite sont :

$\begin{array}{c}{w}_0=\epsilon \\ w_1=0\\ w_2=001\\ w_3=0010011\\ w_4=001001100011011\\ w_5=0010011000110110001001110011011\end{array}$

La suite de pliage est la limite de cette suite de mots. C'est le mot infini :

$p=0010011000110110001001110011011\cdots$

Calcul récursif

On peut montrer que la valeur $p(n)$ du $n$-ième symbole du mot $p$ se calcule récursivement par les formules :

$\begin{array}{c}p(4n)=0\\ p(4n+2)=1\\ p(2n+1)=p(n)\end{array}$

Ainsi $p(12)=0$ et $p(13)=p(6)=1$. Ces formules se traduisent en un autre procédé de construction. On commence par une suite alternée de 0 et de 1, séparée par des « trous ». Dans un deuxième temps, ces trous sont remplis, à leur tour, par une suite alternée de 0 et de 1 lacunaire, etc. La suite résultante est la suite de pliage :

0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 .  
  0   .   1   .   0   .   1   .   0   .   1   .   0   .   1   .   0   .   1   .
      0       .       1       .       0       .       1       .  
              0               .               1 

d'où la suite totale :

0 0 1 0 0 1 1 0 0 0 1 1 0 1 1.

Automate

Automate du pliage de papier régulier. Les états jaunes produisent un 0, les autres un 1.

Comme la suite des pliages est automatique, elle est engendrée par un automate. On voit sur l'automate ci-contre que 01 conduit, depuis tout état, à l'état $b0$, donc que $p(4n+1)=0$; de même, 11 conduit à l'état $c1$, donc $p(4n+3)=1$.

Morphisme

La suite de pliage est un mot 2-morphique. Le morphisme 2-uniforme sur l'alphabet à quatre lettres $\{a,b,c,d\}$ engendré par le morphisme

$\begin{array}{c}a\mapsto ab\\ b\mapsto cb\\ c\mapsto ad\\ d\mapsto cd\end{array}$

à partir de la lettre $a$ est

$abcbadcbabcdadcb\cdots$

ce qui donne le mot $p$ en envoyant $a$ et $b$ sur $0$ et $c$ et $d$ sur $1$.

Noyau

On a

$\begin{array}{c}p(4n)=0\\ p(4n+2)=1\\ p(2n+1)=p(n)\end{array}$

Le 2-noyau a donc trois éléments: la suite $p$, la suite constante égale à 1, et la suite constante égale à 0.

Série génératrice

Soit

$G(X)=\sum _{n=1}^{\mathrm{\infty }}p(n)X^n$

la série formelle génératrice. La construction par récurrence implique que

$G(X)=\sum _{n=0}^{\mathrm{\infty }}{X}^{4n+2}+\sum _{n=1}^{\mathrm{\infty }}p(n)X^{2n+1}=\frac{X^2}{1-X^4}+XG(X^2)$

Sur le corps des fractions rationnelles $F_2((X))$, on a

$G(X^2)=G(X{)}^2$

donc $Y=G(X)$ vérifie l'équation

$X{Y}^2+Y+\frac{X^2}{1+X^4}=0$.

Propriétés

Complexité des facteurs

On note $c_p(n)$ le nombre de facteurs (ou blocs distincts) de longueur $n$ de la suite de pliage $p$. On a les valeurs suivantes :

$n$	0	1	2	3	4	5	6	$\ge 7$
$c_p(n)$	1	2	4	8	12	18	23	$4n$

On a donc $c_p(n)=4n$ pour $n\ge 7$.

Complexité des palindromes

Il n'y a qu'un nombre fini de palindromes distincts qui sont facteurs de la suite $p$. Plus précisément, il n'y a pas de palindrome de longueur 14 ou plus qui est facteur de la suite $p$.

Suites de pliage étendues

On utilise la définition originelle pour étendre la suite de pliage aux cas où l'on ne plie pas toujours dans le même sens. Une suite d'instructions de pliage est une suite $f=(f_n)$ de valeurs 0 ou 1. On définit alors une suite $(w_n)$ de mots sur $\{0,1\}$, dépendant de $f$, par :

• $w_0=\epsilon$ (le mot vide)
• $w_{n+1}=w_n{f}_n{w_n}^{\prime }$, où $f_n$ est la $n$-ième instruction de pliage.

La suite de pliage avec instructions $f$ est la limite, notée $p_f$, de cette suite de mots. Si la suite d'instructions ne contient que des 0, on obtient la suite de pliage régulière. On peut montrer que

• toutes les suites de pliage $p_f$ ont même complexité de facteurs;
• toutes les suites de pliage $p_f$ ont même complexité de palindromes;
• une suite de pliage $p_f$ est une suite automatique si et seulement si la suite d'instructions $f$ est ultimement périodique.

La constante du pliage de papier

C'est le nombre dont le développement binaire est le complémentaire de la suite de pliage. Il est donc égal à

$1-\sum _{n=1}^{\mathrm{\infty }}\frac{p(n)}{2^n}=\sum _{k=0}^{\mathrm{\infty }}\frac{8^{2^k}}{2^{2^{k+2}}-1}=0,850736\dots$ (Modèle:OEIS).

Il est transcendant, comme tous les nombres irrationnels dont le développement dans une base est automatique.

Liens externes

• Modèle:Lien web
• Modèle:Lien web

Articles liés

• mot automatique
• mot de Toeplitz