Meander (wiskunde)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
voorbeeld van een meander

In de wiskunde wordt met meander een configuratie aangeduid van twee krommen in het vlak, die zichzelf niet snijden maar die elkaar een aantal maal snijden. Wanneer de twee krommen open zijn en homeomorf met een rechte, spreekt men van een open meander. Wanneer een van de twee krommen gesloten is en de andere open, spreekt men van een gesloten meander. De krommen zijn Jordan-krommen; voor de eenvoud wordt een ervan (een open kromme) steeds voorgesteld als een rechte. Een stelsel van meanders bestaat uit een rechte en meerdere Jordan-krommen die elkaar niet snijden.

Gesloten meander[bewerken]

Meander van orde 1: de enige manier waarop een gesloten kromme een lijn tweemaal kan snijden.

Een gesloten meander wordt dus gevormd door een gesloten kromme die zichzelf niet snijdt en een rechte. De kromme heeft met de rechte ofwel geen, ofwel een even aantal snijpunten, 2n; n is de orde van de meander.

Meandrisch getal[bewerken]

Het aantal verschillende gesloten meanders met 2n snijpunten noemt men het meandrisch getal of gesloten-meandrisch getal Mn. Hierbij zijn twee meanders verschillend indien men niet door continue vervorming van de kromme van de ene meander naar de andere kan overgaan zonder het aantal of de volgorde van de snijpunten te veranderen.

  • n = 0: M0 = 1 (een lijn en een cirkel die elkaar niet snijden)
  • n = 1: M1 = 1 (een cirkel die een lijn tweemaal snijdt)
  • n = 2: M2 = 2, namelijk:
Meanders2.jpg
  • n = 3: M3 = 8, namelijk:
Meanders4.jpg

en hun spiegelingen omheen de rechte.

Met uitzondering van de triviale gevallen n = 0 en 1 zijn de gesloten-meandrische getallen even getallen: de ene helft van de mogelijke configuraties is het spiegelbeeld omheen de rechte van de andere helft.

De eerste meandrische getallen vanaf n = 0 zijn:

1, 1, 2, 8, 42, 262, 1828, 13820, 110954, 933458, 8152860, ... (rij A005315 in OEIS).

Het opsommen van alle mogelijke meanders is een combinatoriaal probleem, waarbij het aantal mogelijke configuraties exponentieel stijgt met toenemende n. Enkel de meandrische getallen tot en met n=24 zijn reeds bekend.[1]

Voor een stelsel met k gesloten krommen wordt het meandrisch getal voorgesteld als Mn(k). Voorbeelden:

  • voor k = 2, n = 2, 3, 4, 5, ... is dit de reeks: 2, 12, 84, 640, 5236, 45164...[2]
  • voor k = 3, n = 3 ,4, 5, 6, ... is dit de reeks: 5, 56, 580, 5894, 60312, 624240...[2]

Er geldt:[2]

M_{n}^{(n)}  = \frac {1}{2n+1} \binom{2n + 1}{n} = \frac{(2n)!}{n! (n+1)!}

dit is het n-de Catalan-getal.

Open meanders[bewerken]

Een open meander van orde n bestaat uit een open kromme die zichzelf niet snijdt en een rechte, waarbij de kromme de rechte n maal snijdt. Twee open meanders worden als gelijkwaardig beschouwd als ze homeomorf zijn in het vlak.

Voorbeelden[bewerken]

  • De enig mogelijke open meander van orde nul bestaat uit of is homeomorf met twee evenwijdige lijnen.
  • De enig mogelijke open meander van orde 1 snijdt de lijn eenmaal:
OpenMeanderM1.svg
  • De open meander van orde 2 snijdt de lijn tweemaal:
Open Meander M2 jaredwf.png

Bruce Bobier en Joe Sawada hebben een algoritme ontwikkeld dat snel alle open meanders of "meandrische stelsels" van orde n kan genereren.[3]

Open-meandrisch getal[bewerken]

Het aantal verschillende open meanders van orde n is het open-meandrisch getal mn. Dit is het aantal manieren waarop een rivier een weg n maal kan kruisen. Conventioneel wordt hierbij verondersteld dat de kromme vanuit het zuidwesten komt en van west naar oost verloopt, met andere woorden dat ze minstens een uiteinde heeft dat onder de rechte ligt.

De eerste open-meandrische getallen mn vanaf n=0 zijn:

1, 1, 1, 2, 3, 8, 14, 42, 81, 262, 538, 1828, 3926, 13820, 30694, 110954, ... (rij A005316 in OEIS).

Iwan Jensen[4] heeft de open-meandrische getallen tot orde n=43 berekend.

Verband met gesloten-meandrische getallen[bewerken]

Er is een 1-op-1-relatie tussen een lus (gesloten kromme) die een rechte in 2n punten snijdt en een lijn (open kromme) die een rechte in 2n-1 punten snijdt; er geldt:

Mn = m2n−1

Dus de oneven open-meandrische getallen zijn gelijk aan de gesloten-meandrische getallen.

Semi-meander[bewerken]

Bij een (open of gesloten) meander wordt verondersteld dat de rechte lijn aan beide zijden oneindig lang doorloopt. Wanneer de rechte een halflijn is met een eindpunt en slechts aan één zijde oneindig doorloopt, spreekt men van een semi-meander. Ook hier geldt dat twee semi-meanders verschillend zijn als ze niet homeomorf zijn.

Een (gesloten) semi-meander van orde n bestaat uit een gesloten zichzelf niet snijdende kromme die de halflijn in n punten snijdt. n kan nu wel oneven zijn bij een gesloten kromme.

Dit zijn de semi-meanders van orde 3:

Semimeanders3.jpg

Dit zijn de semi-meanders van orde 4:

Semimeanders4.jpg

Het aantal verschillende semi-meanders van orde n wordt aangeduid door het semi-meandrische getal \overline{M_n}.

Toepassingen[bewerken]

Wiskundige meanders duiken in diverse studiegebieden op[1], waaronder

Bronnen, noten en/of referenties
  1. a b Iwan Jensen. Enumerations of plane meanders. arXiv.org, 20 oktober 1999
  2. a b c d P. Di Francesco, O. Golinelli, E. Guitter. "Meander, folding, and arch statistics." Mathematical and Computer Modelling (Okt.-nov. 1997), vol. 26 nrs. 8-10, blz. 97-147. DOI:10.1016/S0895-7177(97)00202-1
  3. Bruce Bobier, Joe Sawada. "A Fast Algorithm to Generate Open Meandric Systems and Meanders." ACM Transactions on Algorithms (2010), vol. 6 nr. 2, blz. 42:1-42:12. DOI:10.1145/1721837.1721858
  4. Iwan Jensen: number of plane meanders
  5. Kurt Hoffmann, Kurt Mehlhorn, Pierre Rosenstiehl. "Sorting Jordan Sequences in Linear Time Using Level-Linked Search Trees." Information and Control (1986), vol. 68 nr. 1-3, blz. 170-184.
  6. Yue Li, Joe Sawada. "Gray codes for reflectable languages." Information Processing Letters (2009), vol. 109 nr. 5, blz. 296-300. DOI:10.1016/j.ipl.2008.11.007