Suite de pliage de papier

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
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 suite A014707 de l'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.

. . .

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[1].

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 suite A014577 de l'OEIS)

Définitions équivalentes[modifier | modifier le code]

Définition formelle[modifier | modifier le code]

Soit la suite de mots sur définie par :

  • (le mot vide)
  • , où désigne le mot obtenu en prenant le retourné de , et en échangeant les et les .

Les premiers mots de la suite sont :

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

Calcul récursif[modifier | modifier le code]

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

Ainsi et . 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 0.

Automate[modifier | modifier le code]

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 , donc que ; de même, 11 conduit à l'état , donc .

Morphisme[modifier | modifier le code]

La suite de pliage est un mot 2-morphique. Le morphisme 2-uniforme sur l'alphabet à quatre lettres engendré par le morphisme

à partir de la lettre est

ce qui donne le mot en envoyant et sur et et sur .

Noyau[modifier | modifier le code]

On a

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

Série génératrice[modifier | modifier le code]

Soit

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

Sur le corps des fractions rationnelles , on a

donc vérifie l'équation

.

Propriétés[modifier | modifier le code]

Complexité des facteurs[modifier | modifier le code]

On note le nombre de facteurs de longueur de la suite de pliage . On a les valeurs suivantes :

  0    1    2    3    4    5    6     
  1   2   4   8   12   18   23    

On a donc pour .

Complexité des palindromes[modifier | modifier le code]

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

Suites de pliage étendues[modifier | modifier le code]

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. Un suite d'instructions de pliage est une suite de valeurs 0 ou 1. On définit alors une suite de mots sur , dépendant de , par :

  • (le mot vide)
  • , où est la -ième instruction de pliage.

La suite de pliage avec instructions est la limite, notée , 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 ont même complexité de facteurs;
  • toutes les suites de pliage ont même complexité de palindromes;
  • une suite de pliage est une suite automatique si et seulement si la suite d'instructions est ultimement périodique.

La constante du pliage de papier[modifier | modifier le code]

C'est le nombre[2] dont le développement binaire est le complémentaire de la suite de pliage. Ce nombre est

.

Il a l'expression close

C'est le nombre donné par la suite A143347 de l'OEIS. C'est un nombre transcendant, comme tous les nombres irrationnels dont le développement dans une base est automatique.

Références[modifier | modifier le code]

  • Jean-Paul Allouche et Jeffrey O. Shallit, Automatic sequences : Theory, applications, generalizations, Cambridge University Press, (ISBN 0-521-82332-3, Math Reviews 1997038)Document utilisé pour la rédaction de l’article