Brontekst bekijken van Rij van Prouhet-Thue-Morse

De '''rij van Prouhet-Thue-Morse''' is een oneindige [[Rij (wiskunde)|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: 
:<math>0\to 01 \to 0110 \to 01101001 \ldots</math>

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 taal|formele talen]], en door de Amerikaan [[Marston Morse|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:

:<math>t_0 = 0</math>
:<math>t_{2n} = t_n</math> en
:<math>t_{2n+1} = 1-t_n</math>

waarbij <math>n</math> een positief [[natuurlijk getal]] is.

===Andere definities===
[[Bestand:Morse-Thue sequence.gif|thumb|right|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 <math>n</math>-de stap verkrijgt men zo een rij met <math>2^n</math> nullen en <math>2^n</math> 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 <math>t_m</math> 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, <del>1</del>, 1, <del>0</del>, 1, <del>0</del>, 0, <del>1</del>, 1, <del>0</del>, 0, <del>1</del>, 0, <del>1</del>, 1, <del>0</del>, 1, <del>0</del>, 0, <del>1</del>, 0, <del>1</del>, 1, <del>0</del>, 0, <del>1</del>, 1, <del>0</del>, 1, <del>0</del>, 0, <del>1</del>, ...

De rij kan geïnterpreteerd worden als een voorstelling van de [[Pariteit (wiskunde)|pariteit]] van de [[binair getal|binaire voorstelling]] van de natuurlijke getallen, dit is het aantal maal dat het cijfer 1 voorkomt in de binaire voorstelling van het getal <math>n,</math> berekend [[modulair rekenen|modulo]] 2.
Voor de eerste natuurlijke getallen geeft dit:
:{| class="wikitable"
|<math>n</math>||binaire voorstelling van <math>n</math>||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:
:<math>P = 0{,}01101001100101101001011001101001\ldots _2</math>

In decimale notatie is dit:
:<math>P = 0{,}4124540336401075977\ldots </math>

Deze constante kan geschreven worden als een som:
:<math>P = \sum_{i=0}^\infty \frac{t_i}{2^{i+1}}</math>

met <math>t_i</math> het <math>i</math>-de element van de rij van Prouhet-Thue-Morse. [[Kurt Mahler]] bewees in 1929 dat dit een [[transcendent getal]] is.

==Externe links==
* [http://mathworld.wolfram.com/Thue-MorseSequence.html Mathworld pagina over de Thue-Morse-rij]

[[Categorie:Wiskundige analyse]]