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: 

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:

 en

waarbij  een positief natuurlijk getal is.

Andere definities

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 -de stap verkrijgt men zo een rij met  nullen en  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  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  berekend modulo 2.
Voor de eerste natuurlijke getallen geeft dit:
{| class="wikitable"
|||binaire voorstelling van ||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:

In decimale notatie is dit:

Deze constante kan geschreven worden als een som:

met  het -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

Wiskundige analyse