Rij van Prouhet-Thue-Morse

De rij van Prouhet-Thue-Morse is een oneindige wiskundige rij die begint door een 0 op te schrijven en vervolgens steeds een 0 te vervangen door 01 en een 1 door 10. Zo ontstaat:

$0\to 01\to 0110\to 01101001\ldots$

Het begin van de rij is:

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, ...

Deze rij werd voor het eerst vermeld in 1859 door de Franse wiskundige Eugène Prouhet (1817-1867) in het kader van de getaltheorie. Ze werd later herontdekt door de Noorse wiskundige Axel Thue in het begin van de twintigste eeuw, die ze gebruikte bij de studie van niet-repetitieve reeksen van symbolen of "woorden" in formele talen, en door de Amerikaan Harold Calvin Marston Morse (1892-1977), die ze gebruikte in differentiaalmeetkunde. In de Angelsaksische landen noemt men dit de rij van Thue-Morse.

Definitie

Recursieve definitie

De rij wordt gedefinieerd door de volgende vergelijkingen:

$t_{0}=0$

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

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

waarbij $n$ een positief natuurlijk getal is.

Andere definities

constructie van de rij van Prouhet-Thue-Morse

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 $n$-de stap verkrijgt men zo een rij met $2^{n}$ nullen en $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.

Eigenschappen

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 $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 $n,$ berekend modulo 2. Voor de eerste natuurlijke getallen geeft dit:

$n$	binaire voorstelling van $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.

Constante van Thue-Morse

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

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

In decimale notatie is dit:

$P=0{,}4124540336401075977\ldots$

Deze constante kan geschreven worden als een som:

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

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

Externe links

• Mathworld pagina over de Thue-Morse-rij