How many ways can a road cross a river?

Question

Imagine a straight river and a road that goes across the river n times through bridges. The road does not loop on itself and is infinitely long. This road would be considered an open meander. An open meander is an open curve, that does not intersect itself and extends infinitely at both ends, which intersects a line n times.

A valid meander may be described entirely by the order of the intersection points it visits.

The number of distinct patterns of intersection with n intersections a meander can be is the nth meandric number. For example, n = 4:

The first few numbers of this sequence are:

1, 1, 1, 2, 3, 8, 14, 42, 81, 262, 538, 1828, 3926, 13820, 30694, 110954...

This is OEIS sequence A005316.

Challenge

Write a program/function that takes a positive integer n as input and prints the nth meandric number.

Specifications

• Standard I/O rules apply.
• Standard loopholes are forbidden.
• Your solution can either be 0-indexed or 1-indexed but please specify which.
• This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
• Your code will be scored in bytes, usually in the encoding UTF-8, unless specified otherwise.
• Built-in functions that compute this sequence are allowed but including a solution that doesn't rely on a built-in is encouraged.
• Explanations, even for "practical" languages, are encouraged.

Test cases

These are 0-indexed. Note that you need not handle numbers this big if your language cannot by default.

Input      Output

1          1
2          1
11         1828
14         30694
21         73424650
24         1649008456
31         5969806669034

In a few better formats:

1 2 11 14 21 24 31
1, 2, 11, 14, 21, 24, 31

Answer 1

Python 3, 208 188 187 184 180 177 171 bytes

lambda n:sum(all(i-j&1or(x<a<y)==(x<b<y)for(i,(a,b)),(j,(x,y))in d(enumerate(map(sorted,zip((0,)+p,p+(n,)))),2))for p in d(range(n)))
from itertools import*;d=permutations

Try it online!

Now 1-indexed (was previously 0-indexed but 1-indexing saved a byte due to a lucky quirk regarding the behavior of meanders).

Explanation

This may be the same as the link posted by Jenny_mathy, but I didn't end up reading the paper, so this is just the logic behind my method.

I will be using the following illustration provided on OEIS in order to visualize the results.

Each valid meander may be described entirely by the order of the intersection points it visits. This may be trivially observed in the image; the entry segment is always on the same side (otherwise the number would be double). We can represent the tendency of both the entry and exit segments to their respective infinities by simply adding to every order a point on either side - that is to say, the order (2, 1, 0) would become (-1, 2, 1, 0, 3).

With this in mind, the task is to find the number of orders, or permutations of the range up to n, which do not intersect with themselves. Intersections are only an issue between pairs of points for which the connecting segment lies on the same side. For any two pairs of consecutive points in a permutation whose segments share a side, whether or not they intersect is equivalent to whether one, and only one, of the points of one pair is between the two elements of the other pair. As such, we can determine if an order is valid by whether there are no pairs with one point contained by another pair with a segment on the same side.

Finally, having determined the validity of each permutations, the output of the function comes down to the number of permutations found to be valid.

Answer 2

Haskell, 199 bytes

1!x=x
-1!(-1:x)=1:x
n!(i:x)=i:(n-i)!x
0#([],[])=1
0#_=0
n#(a,b)=sum$((n-1)#)<$>(-1:a,-1:b):[(a,-i:b)|i:a<-[a]]++[(-j:a,b)|j:b<-[b]]++[(j!a,i!b)|i:a<-[a],j:b<-[b],i+j>=0]
f n=n#([],[-1,1])+n#([1],[1])

Try it online!

Based on an extension of the ideas in Iwan Jensen, Enumerations of plane meanders, 1999 to the case of open meanders. This runs through n = 1, …, 16 in about 20 seconds on TIO.

Answer 3

APL (Dyalog Classic), 127 115 bytes

⊃⊃⌽{↓⍉(⊃,/c),∘(+/)⌸(≢¨c←{1↓¨⍳¨⍨0,¨((×2↑¯1⌽⍵)/¯1 1⌽¨⊂⍵),(⊂∊#⍵#),(××/m,≠/m)/⊂1↓¯1↓(⊢-⍵×~)⍵∊m←2↑¯1⌽⍵}¨⊃⍵)/⊃⌽⍵}⍣⎕⌽1,⊂⍳2

Try it online!