Farey-rij

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Farey-diagram van F5.

In de wiskunde is de Farey-rij van orde n de rij breuken tussen 0 en 1 die in volledig gereduceerde vorm een noemer hebben die kleiner dan of gelijk is aan n. De elementen in de Farey-rij zijn gerangschikt in volgorde van toenemende grootte. De rij is vernoemd naar de Britse geoloog John Farey. Hij merkte in een kort artikel uit 1816 het volgende op:[1] elke breuk in een dergelijke rij is gelijk aan de breuk met als teller de som van de tellers en als noemer de som van de noemers van de twee breuken aan weerszijden ervan, eventueel na vereenvoudiging.

Elke Farey-rij begint met de waarde 0, aangeduid door de fractie 0/1 en eindigt met de waarde 1, aangeduid door de fractie 1/1 (hoewel sommige auteurs deze begin- en eindterm weglaten).

Voorbeelden[bewerken]

De Farey-rijen van de orden 1 tot 5 zijn :

Inderdaad geldt bijvoorbeeld in :

is gelegen tussen en , en

Analoog:

Het aantal breuken in de Farey-rijen van orde 0, 1, 2, 3, 4, ... is 1, 2, 3, 5, 7, 11, 13, 19, 23, 29, 33, 43, 47, 59, 65, 73, ... (rij A005728 in OEIS). De lengte van de Farey-rijen van orde n nadert asymptotisch tot .

Farey-afstand[bewerken]

De Farey-afstand tussen twee breuken is:

Twee breuken zijn Farey-gerelateerd als hun Farey-afstand d gelijk is aan 1; dit is bijvoorbeeld het geval voor de paren 1/3 en 2/7 of 2/7 en 7/24. d is de determinant van de matrix

Twee opeenvolgende breuken in een Farey-rij zijn altijd Farey-gerelateerd. Deze relatie kan grafisch voorgesteld worden in de zogenaamde Farey-graaf.

Farey-graaf[bewerken]

Gedeelte van de Farey-graaf in het hyperbolische halfvlak

De Farey-graaf is een oneindig grote graaf met als knopenverzameling de verzameling van volledig gereduceerde rationale getallen plus oneindig (d.i. de breuk 1/0). Twee knopen zijn verbonden door een kant wanneer ze Farey-gerelateerd zijn, dus wanneer hun Farey-afstand gelijk is aan 1.

De Farey-graaf wordt vaak afgebeeld in het hyperbolische halfvlak, waarbij de rationale getallen op een rechte lijn staan en de kanten voorgesteld worden als geodetische krommen. De figuur hiernaast stelt het deel van de Farey-graaf voor dat correspondeert met de Farey-rijen F1 tot F5.

Twee opeenvolgende breuken in een Farey-rij zijn verbonden in de Farey-graaf. Elke Farey-rij vormt bijgevolg een cykel in de Farey-graaf.

Elke kant in de Farey-graaf behoort tot een 3-cykel. Met andere woorden: de Fareygraaf is een triangulatie. De knopen die een 3-cykel vormen hebben steeds de waarden: ; bijvoorbeeld 0/1, 1/4 en 1/5 of 1/3, 1/2 en 2/5; dit is de eigenschap die Farey in zijn artikel aan het licht bracht.

Farey-graaf en kettingbreuken[bewerken]

Er is een verband tussen kettingbreuken en de Farey-graaf, een object uit de hyperbolische meetkunde. Elke echte breuk tussen 0 en 1 kan men schrijven als een eindige kettingbreuk die men iteratief kan bepalen:

De getallen zijn te bepalen als volgt:

  • doe voor
    • en stop wanneer

Wanneer de opeenvolgende weggelaten worden, krijgt men een rij breuken die opeenvolgende benaderingen zijn van :

Tussen deze convergenten loopt een pad in de Farey-graaf: de Farey-afstand tussen twee opeenvolgende getallen in de rij is steeds 1. In de "hyperbolische" voorstelling van de graaf is het een zigzagpad: het verschil verandert steeds van teken. De opeenvolgende breuken zijn met andere woorden afwisselend een overschatting en onderschatting van .

De getallen worden gegenereerd door de afbeelding , te beginnen bij , waarbij het fractionele deel van een getal is.

Wanneer een irrationaal getal tussen 0 en 1 is, is de rij oneindig lang; het verschil tussen twee opeenvolgende breuken in die rij wordt steeds kleiner en in de limiet wordt het nul. Het corresponderende oneindige pad in de Farey-graaf zigzagt eeuwig heen en weer rond en benadert steeds dichter dat getal.

Voorbeeld[bewerken]

Als verkrijgen we achtereenvolgens:

Dus

Het pad dat leidt naar is

Toepassingen[bewerken]

Farey-rijen en de Farey-graaf zijn het onderwerp van talrijke publicaties op zowel theoretisch als toegepast vlak. Zo zijn Farey-rijen onder meer gebruikt voor het genereren van pseudo-toevalsgetallen[2], of voor het bepalen van de boven- en ondergrens van de equivalente weerstand van een schakeling van n gelijke weerstanden in een willekeurige combinatie.[3]

Externe links[bewerken]