Rij van Prouhet-Thue-Morse

De rij van Prouhet-Thue-Morse is een oneindige wiskundige rij die als volgt begint:

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, 0, 1, 1, 0, 1, 0, 0, 1

enz. In de n-de stap verkrijgt men zo een rij met 2ⁿ nullen en 2ⁿ enen. De rij die men in elke 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. Max Euwe heeft deze rij gebruikt om te bewijzen dat er schaakpartijen mogelijk zijn die oneindig lang duren maar toch nooit drie identieke opeenvolgende zetten 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 trouwens 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...₂

In decimale notatie is dit:

P = 0,4124540336401075977...

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