Liczby otwarto-meandryczne

Rzeka ma źródło na południowym-zachodzie i wpływa do morza na wschodzie. Z zachodu na wschód jest też droga, na której jest n mostów nad rzeką. Na ile możliwych sposobów może ta rzeka przecinać drogę?

Rozwiązanie tego problemu w zależności od n tworzy ciąg tzw. liczb otwarto-meandrycznych (open meandric numbers) - oznaczany m_i. Meandryczne - oczywiście od meandrów rzeki, natomiast otwartość bierze się z faktu, iż rzeka to krzywa otwarta. Liczby meandryczne dotyczą krzywych zamkniętych - pytanie jak taka rzeka płynie ;)

Spróbujmy znaleźć parę początkowych liczb otwarto-meandrycznych.

Na początek sprecyzujmy pojęcie "sposobu w jaki rzeka przecina drogę" - chodzi o to w jakiej kolejności przepływa ona pod mostami na drodze.

1. Brak mostów

Sprawa prosta - rzeka płynie cały czas po południowej stronie drogi

czyli m₀ = 1.

2. Jeden most

Znowu prosta sprawa:

zatem m₁ = 1.

3. Dwa mosty

Dwa mosty rzeka może przekroczyć tylko na jeden sposób - najpierw pierwszy, potem drugi. Jeżeli najpierw by przekroczyła drugi, to sama sobie odcina drogę powrotu do morza:

czyli m₂ = 1.

4. Trzy mosty

To pierwszy ciekawy przypadek - są dwie możliwe kolejności, w jakich rzeka przepływa pod mostami:
a) pierwszy, drugi, trzeci
b) trzeci, drugi, pierwszy.

Więc m₃ = 2.

5. Cztery mosty

Tu mamy już trzy możliwości. Co ciekawe dwie możliwości to lustrzane odbicie takiego samego meandra:

Mamy w takim razie m₄ = 3.

6. Pięć mostów

Pierwszy naprawdę ciekawy przypadek :) Zresztą zobaczcie sami:

Otrzymujemy więc m₅ = 8.

I parę kolejnych liczb otwarto-meandrycznych:

m₆ = 14
m₇ = 42
m₈ = 81
m₉ = 262
m₁₀ = 538

Jeżeli liczycie teraz na ogólny wzór lub coś podobnego to niestety - nie ma go jeszcze, nawet rekurencyjnego. Wszystkie liczby muszą być wyliczane metodami mniej lub bardziej siłowymi. Taki prosty problem, a nie ma ogólnego rozwiązania - ciekawe, nie?

Więcej:
http://www.research.att.com/~njas/sequences/A005316
http://en.wikipedia.org/wiki/Meander_%28mathematics%29#Open_meandric_numbers