Meander (wiskunde)

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.

voorbeeld van een meander

Gesloten meander

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, ${\displaystyle 2n;}$ ${\displaystyle n}$ is de orde van de meander.

Meandrisch getal

Het aantal verschillende gesloten meanders met ${\displaystyle 2n}$ snijpunten noemt men het meandrisch getal of gesloten-meandrisch getal ${\displaystyle M_{n}.}$ 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.

• ${\displaystyle n=0:M_{0}=1}$ (een lijn en een cirkel die elkaar niet snijden)
• ${\displaystyle n=1:M_{1}=1}$ (een cirkel die een lijn tweemaal snijdt)
• ${\displaystyle n=2:M_{2}=2}$, namelijk:

• ${\displaystyle n=3:M_{3}=8}$, namelijk:

en hun spiegelingen ten opzichte van de rechte.

Met uitzondering van de triviale gevallen ${\displaystyle n=0}$ en ${\displaystyle n=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 ${\displaystyle 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 voor ${\displaystyle n.}$ Enkel de meandrische getallen tot en met ${\displaystyle n=24}$ zijn reeds bekend.^[1]

Voor een stelsel met ${\displaystyle k}$ gesloten krommen wordt het meandrisch getal voorgesteld als ${\displaystyle M_{n}^{(k)}.}$ Voorbeelden:

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

Er geldt:^[2]

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

dit is het ${\displaystyle n}$-de Catalan-getal.

Open meanders

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

Voorbeelden

• 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:

• De open meander van orde 2 snijdt de lijn tweemaal:

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

Open-meandrisch getal

Het aantal verschillende open meanders van orde ${\displaystyle n}$ is het open-meandrisch getal ${\displaystyle m_{n}.}$ Dit is het aantal manieren waarop een rivier een weg ${\displaystyle 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 ${\displaystyle m_{n}}$ vanaf ${\displaystyle 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 ${\displaystyle n=43}$ berekend.

Verband met gesloten-meandrische getallen

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

${\displaystyle M_{n}=m_{2n}-1}$

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

Semi-meander

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 ${\displaystyle n}$ bestaat uit een gesloten zichzelf niet snijdende kromme die de halflijn in ${\displaystyle n}$ punten snijdt. ${\displaystyle n}$ kan nu wel oneven zijn bij een gesloten kromme.

Dit zijn de semi-meanders van orde 3:

Dit zijn de semi-meanders van orde 4:

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

Toepassingen

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

• vouwproblemen: bijvoorbeeld
  • het kaartenvouwprobleem: op hoeveel manieren kan je een rechthoekige landkaart opvouwen?;
  • het postzegelprobleem: op hoeveel manieren kan je een strip postzegels opvouwen?;
  • op hoeveel manieren kunnen polymeerketens zich opvouwen?^[2]
• in de computerwetenschap staan ze in verband met het sorteren van Jordan-reeksen, die bepaald worden door de opeenvolgende ${\displaystyle x}$-coördinaten van de snijpunten van een Jordan-kromme met de ${\displaystyle x}$-as.^[5]
• in de theoretische informatica zijn ze in verband gebracht met de Gray-codering van strings in bepaalde formele talen.^[6]
• ze houden ook verband met het opsommen van "ovalen" in vlakke algebraïsche krommen.

Bronnen, noten en/of referenties

1. Iwan Jensen. Enumerations of plane meanders. arXiv.org, 20 oktober 1999
2. 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. Gearchiveerd op 12 mei 2013. Geraadpleegd op 18 december 2013.
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