Rij van Prouhet-Thue-Morse

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

Recursieve definitie[bewerken]

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[bewerken]

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 2n nullen en 2n 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[bewerken]

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 tm 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[bewerken]

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

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[bewerken]