Rij van Prouhet-Thue-Morse

De rij wordt gedefinieerd door de volgende vergelijkingen:

${\displaystyle t_{0}=0}$ 

${\displaystyle t_{2n}=t_{n}}$  en

${\displaystyle t_{2n+1}=1-t_{n}}$ 

waarbij ${\displaystyle n}$  een positief natuurlijk getal is.

 

Men kan de rij ook als volgt opbouwen:

• begin met de rij bestaande uit één term, namelijk 0;
• maak een nieuwe rij door in de vorige rij elke 0 te vervangen door een 1 en elke 1 door een 0;
• voeg deze nieuwe rij toe achteraan de bestaande rij;
• herhaal de twee voorgaande stappen.

Zo krijgt men achtereenvolgens:

• 0 gevolgd door 1 geeft 0, 1
• 0, 1 gevolgd door 1, 0 geeft 0, 1, 1, 0
• 0, 1, 1, 0 gevolgd door 1, 0, 0, 1 geeft 0, 1, 1, 0, 1, 0, 0, 1
• 0, 1, 1, 0, 1, 0, 0, 1 gevolgd door 1, 0, 0, 1, 0, 1, 1, 0 geeft 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0

enz. In de ${\displaystyle n}$ -de stap verkrijgt men zo een rij met ${\displaystyle 2^{n}}$  nullen en ${\displaystyle 2^{n}}$  enen. De rij die men in elke even stap verkrijgt is een palindroom.

Een alternatieve constructie is:

• begin met de rij "0"
• vervang in de rij elke "0" door "0 1" en elke "1" door "1 0"; herhaal deze stap.

Men kan dit overigens uitvoeren met eender welk paar van verschillende symbolen in plaats van 0 en 1.

Kenmerkend aan deze rij is dat er nooit drie opeenvolgende identieke symbolen (0 0 0 of 1 1 1) in voorkomen; men zegt dat ze "kubiekvrij" (Engels: cubefree) is. Dit geldt trouwens voor elk willekeurig "woord", zijnde een opeenvolging van tekens uit het gebruikt alfabet 0,1. Stel bijvoorbeeld W=0,1,1,0,1 dan komt W,W,W of 0,1,1,0,1,0,1,1,0,1,0,1,1,0,1 nergens voor in de rij van Prouhet-Thue-Morse. In het schaakspel is er een regel die zegt dat een partij in remise eindigt als drie achtereenvolgende zetten dezelfde stelling opleveren. Max Euwe heeft deze rij gebruikt om te bewijzen dat er schaakpartijen mogelijk zijn die oneindig lang duren, maar toch nooit opeenvolgend drie identieke stellingen bevatten.

Ze is ook niet-periodiek: er bestaat geen element ${\displaystyle t_{m}}$  vanwaar de rij terug van voor af aan begint.

De rij is self-similar: als men elk even symbool uit de rij weglaat, verkrijgt men de oorspronkelijke rij terug:

0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, ...

De rij kan geïnterpreteerd worden als een voorstelling van de pariteit van de binaire voorstelling van de natuurlijke getallen, dit is het aantal maal dat het cijfer 1 voorkomt in de binaire voorstelling van het getal ${\displaystyle n,}$  berekend modulo 2. Voor de eerste natuurlijke getallen geeft dit:

${\displaystyle n}$	binaire voorstelling van ${\displaystyle n}$	aantal 1	(aantal 1) mod 2
0	0	0	0
1	1	1	1
2	10	1	1
3	11	2	0
4	100	1	1
5	101	2	0
6	110	2	0
7	111	3	1
8	1000	1	1

enz. De rij van Prouhet-Thue-Morse is overigens verwant aan de gray-code.

De constante van Thue-Morse is het binaire getal gevormd door de opeenvolgende cijfers in de reeks te schrijven achter de komma:

${\displaystyle P=0{,}01101001100101101001011001101001\ldots _{2}}$ 

In decimale notatie is dit:

${\displaystyle P=0{,}4124540336401075977\ldots }$ 

Deze constante kan geschreven worden als een som:

${\displaystyle P=\sum _{i=0}^{\infty }{\frac {t_{i}}{2^{i+1}}}}$ 

met ${\displaystyle t_{i}}$  het ${\displaystyle i}$ -de element van de rij van Prouhet-Thue-Morse. Kurt Mahler bewees in 1929 dat dit een transcendent getal is.

• Mathworld pagina over de Thue-Morse-rij