La sucesión de Thue-Morse

Axel_ThueEl matemático noruego Axel Thue nació un 19 de febrero, así que hoy es un buen día para hablar de la conocida como sucesión de Thue-Morse que ha aparecido en contextos matemáticos tan diferentes como la teoría de los números –Eugène Prouhet–, la combinatoria –Alex Thue–, la geometría diferencial –Marston Morse– o el ajedrez –Max Euwe–.

Se trata de una sucesión binaria que tiene la siguiente propiedad: ninguna secuencia finita de números se repite tres veces en la sucesión. Es decir, no hay nunca tres ‘0’ o tres ‘1’ seguidos, ni tres ’00’, tres ’01’ o tres ’10’ consecutivos, ni tres ‘100’, tres ‘101’, tres ‘110’, tres ‘111’, tres ‘000’, tres ‘001’, tres ‘010’ o tres ‘011’  seguidos, etc.

Se define de manera muy sencilla: si u(k) denota el k-ésimo término de la sucesión, entonces u(0)=0, u(2n)=u(n) y u(2n+1)=1-u(n).

Empieza así: 01101001100101101001011001101001…,

Otra forma recurrente de definirla es la siguiente: si a(n) denota los 2n primeros términos de la sucesión, entonces  a(0)=0 y a(n+1)=a(n)b(n), donde b(n) se obtiene a partir de a(n) al intercambiar los 0’s y los 1’s.

auto

Autómata de Thue-Morse

Además u(k) es la suma, módulo 2, de las cifras en el desarrollo binario de k. Por ejemplo, (18)2=10010 y por lo tanto u(18)=0. Este cálculo se realiza por medio del autómata de Thue-Morse: partiendo del estado inicial, se siguen las transiciones indicadas por los bits del desarrollo binario. Dependiendo del color del estado de llegada, el término de la sucesión es 0 ó 1. Por ejemplo, para el 18, se obtiene:

a0\xrightarrow1b1\xrightarrow0b1\xrightarrow0b1\xrightarrow1a0\xrightarrow0a0

y entonces el valor es 0.

PD: Esta entrada participa en la edición 4.1 del Carnaval de Matemáticas cuyo blog anfitrión es Tito Eliatron Dixit.

1 Response to “La sucesión de Thue-Morse”


  1. 1 Marta MS 19/02/2016 a las 09:46

    Reblogueó esto en Martams's Blogy comentado:

    El matemático noruego Axel Thue (1863-1922) nació un 19 de febrero

    Me gusta


Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s




UPV/EHU
UPV/EHU
UPV/EHU
Premio a la Mejor Entrada de marzo del Carnaval de Física 2014: El lago elgygytgyn (por Marta Macho)
Premio Mejor Post en la VII Edición del Carnaval de Humanidades..Gracias a Marta Macho
Premio a la Mejor Entrada de la Edición 4.1231 del Carnaval de Matemáticas.

Egutegia | Calendario

febrero 2013
L M X J V S D
« Ene   Mar »
 123
45678910
11121314151617
18192021222324
25262728  

Artxiboak | Archivo

Estatistika | Estadística

  • 2,520,983 sarrerak | visitas

RSS Noticias UPV/EHU

  • Ha ocurrido un error; probablemente el feed está caído. Inténtalo de nuevo más tarde.

RSS UPV/EHU Albisteak

  • Ha ocurrido un error; probablemente el feed está caído. Inténtalo de nuevo más tarde.

RSS Eventos UPV/EHU

  • Ha ocurrido un error; probablemente el feed está caído. Inténtalo de nuevo más tarde.

RSS UPV/EHU Ekitaldiak

  • Ha ocurrido un error; probablemente el feed está caído. Inténtalo de nuevo más tarde.

A %d blogueros les gusta esto: