Rij van Prouhet-Thue-Morse

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

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

Recursieve definitie[bewerken | brontekst bewerken]

De rij wordt gedefinieerd door de volgende vergelijkingen:

en

waarbij een positief natuurlijk getal is.

Andere definities[bewerken | brontekst 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, 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[bewerken | brontekst 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 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:

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

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