title: Farey-rij
text: 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: 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
  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, ... (). De lengte van de Farey-rijen van orde n nadert asymptotisch tot .
  
  Farey-afstand
  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
  
  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
  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
  Als  verkrijgen we achtereenvolgens:
  
  Dus
   
  
  Het pad dat leidt naar  is
  
  Toepassingen
  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, of voor het bepalen van de boven- en ondergrens van de equivalente weerstand van een schakeling van n gelijke weerstanden in een willekeurige combinatie.
  
  Externe links
   "Fibonacci-getallen, gulden snede, kettingbreuken en toepassingen" 
   Cursusnota over kettingbreuken en de Farey-graaf 
  
  Getaltheorie