This site is supported by donations to The OEIS Foundation.
User:Peter Luschny/Meander
From OeisWiki
Meanders and
Walks on a Circle
KEYWORDS: Binary curves, meanders, walks on a circle.
Concerned with sequences:
A198060, A199932, A200062, A200583; A007318, A000012,
A000079; A103371, A003056, A001700;
A194595, A073254, A197657; A197653, A198063, A198256;
A197654, A198064, A198257; A197655, A198065, A198258.
Contents 
The definitions
Satellite photo of the Songhua River in northeast China.
Recently Susanne Wienand contributed a series of sequences to the OEIS related to meanders which we want to explore. But what are meanders? Roughly speaking meanders are closed curves drawn by arcs (and only arcs). In particular we will look at meanders whose arcs have a fixed central angle and have equal length. However, the term 'meander' is used in many different ways and therefore we will elaborate on the formal definition used here.
Definition. A binary curve C is a pair (m, S) such that
(a) S is a list with values in {L, R} which
(b) starts with an L, and
(c) m > 0 is an integer which divides the length of S.
Given a binary curve C = (m, S) we call m the modulus of the curve and S the steps of C. The use of 'L' and 'R' here is for mnemonic reason: 'L' stands for a positively oriented arc (left curve) and 'R' for a negatively oriented arc (right curve).
Examples. C1 = (2, LRRLRR) and C2 = (3, LRRRLL) are binary curves of length 6. In contrast neither (3, LRRRLLR) nor (2, RLRRRL) is a binary curve.
Next we associate with each step of a binary curve a direction. To this end we define a function dir: S → [0..m1] recursively.
Definition: The first step has direction 1, dir(S[0]) = 1. Assume now step n > 0.
dir(S[n]) = (dir(S[n−1])+[S[n]=L=S[n−1]]−[S[n]=R=S[n−1]]) mod m.
Here [ ] is the Iverson bracket. This means [S[n]=Y=S[n1]] = 1 if S[n] = Y and S[n1] = Y, otherwise 0.
We say a binary curve changes direction if two consecutive steps are of the same type. Thus whenever a binary curve changes direction the direction of the curve is increased by one if the step is of type L and decreased by one if the step is of type R, modulo m.
Mapping the direction function on the steps of a binary curve gives a list DIR(C) of length(S).
For example let S = LLLLRLLRLLRLRRLLLLLRRLLLRRRRLR and C = (6,S). Then DIR(C) = 123444555000055012332234432111.
Definition. A binary curve C = (m, S) is a meander if and only if each of the values 0,..,m1 occur with equal frequency in DIR(C).
In the last example above this is indeed the case.
The routine 'isMeander' below decides if a given binary curve is a meander. It counts the number of occurrences of the values of dir(S[n]) and as soon as a value occurs more than length(S)/m times returns with 'false'. If this does not happen all values are equal distributed and the routine returns 'true'.
def isMeander(m, S) : # Sage/Phython vec = [0]*m max = len(S) // m dir = 0 os = S[0] for s in S : if s and os : dir = dir + 1 elif not s and not os : dir = dir  1 dir = dir % m v = vec[dir] + 1 vec[dir] = v if v > max : return False os = s return True
Remark: A meander is a closed curve. Conversely, a closed curve is not necessarily a meander.
For example let S = LRRRRRRRRRRRLRLLRRRRRLRL. Then the binary curve (6, S) is closed but not a meander. On the other hand the binary curve (2, S) is a meander.
Plotting meanders
With Asymptote, a vector graphics language based on previous work of John D. Hobby (MetaPost) and Donald E. Knuth's MetaFont, meanders are easily visualized.
size(12cm,0); bool L = true, R = false, StepLast; real AngInc, Ang; pair Z, A; void Step(bool StepAct) { if(StepLast != StepAct) { Z = 2*A  Z; Ang += 180; } real OldAng = Ang; Ang += StepAct ? AngInc : AngInc; A = Z + dir(Ang); pen Pen = StepAct ? orange : green; draw(arc(Z,1,OldAng,Ang,StepAct),Pen,ArcArrow); StepLast = StepAct; } void Walk(int m, bool[] steps) { AngInc = 360 / m; Ang = AngInc; StepLast = L; Z = (0,0); A = Z + (1,0); for(bool s : steps) Step(s); } bool[] meander = {L,R,L,L,L,R,R,R,R,L,R,R,L,R,L,L,L,L,R,L,L,R,L,L,L}; Walk(5, meander); shipout("Meander", bbox(0.3cm));
Enumerating meanders
Susanne Wienand posed the question:
In how many ways can a meander be drawn by arcs with a central angle of 360/m degrees and of equal length, (nk)m of which are negatively and (k+1)m positively oriented, starting with a positively oriented arc? (m>0, n≥0, k≥0)
Wienand computed some of the values by brute force and observed that these values also can be found using a recurrence (see her article on OpenCS). Using the Iverson bracket [ ] this recurrence can be written:

Or with Maple:
T := proc(m, n, k) local b; b := binomial(n, k); if m > 1 then b := b * (b^(m1) + T(m1,n,n1k)) fi; b end:
For fixed m we get a numerical triangle. For example in the case m = 5 we find:
m = 5  
n \ k  0  1  2  3  4  Sum 
0  1  1  
1  5  1  6  
2  31  62  1  94  
3  121  1215  363  1  1700  
4  341  13504  20256  1364  1  35466 
The first step
Our exposition is based on a single function. This function gives for m = 0,1,2,... a sequence of integer triangles similar to Pascal's triangle, with which they share the symmetry between left and right.
P(m,n,k) = Sum{j=0..m}Sum{i=0..m}(1)^(j+i)C(i,j) n^j k^(mj)
The sequences start with the simplest sequence of all; the first six cases are:
m  T(n, k)  Sum_{k=0..n} T(n, k)  Sum(n,k)  
P(0,n,k)  A000012  1  n+1  A000027 
P(1,n,k)  A003056  n  n^2+n  A002378 
P(2,n,k)  A073254  k^2kn+n^2  (5n^3+6n^2+n)/6  A033994 
P(3,n,k)  A198063  2k^2n2kn^2+n^3  (2n^4+3n^3 +n^2)/3 
A098077 
P(4,n,k)  A198064  k^42k^3n+4k^2n^2 3kn^3+n^4 
(16n^5+30n^4 +15n^3n)/30 

P(5,n,k)  A198065  3nk^46k^3n^2 +7k^2n^34kn^4+n^5 
(13n^6+30n^5 +20n^43n^2)/30 
A simple way to compute this family of sequences is:
G := proc(m, n, k) if n = 2*k then m*k^(m1) else (k^m(nk)^m)/(2*kn) fi end:
Then G(m, n, k) = P(m1, n, k) for m > 0.
The second step
On top of this sequence of triangles we define a second sequence of triangles. The first triangle is Pascal's triangle.
A007318(n,k) = A000012(n+1,k+1)C(n,k)^1/(k+1)^0 = H(1,n,k) A103371(n,k) = A003056(n+1,k+1)C(n,k)^2/(k+1)^1 = H(2,n,k) A194595(n,k) = A073254(n+1,k+1)C(n,k)^3/(k+1)^2 = H(3,n,k) A197653(n,k) = A198063(n+1,k+1)C(n,k)^4/(k+1)^3 = H(4,n,k) A197654(n,k) = A198064(n+1,k+1)C(n,k)^5/(k+1)^4 = H(5,n,k) A197655(n,k) = A198065(n+1,k+1)C(n,k)^6/(k+1)^5 = H(6,n,k)
These triangles can be computed with Maple as follows:
H := proc(m, n, k) if n = 1+2*k then m else (1+k)*(1((nk)/(1+k))^m)/(1+2*kn) fi; %*binomial(n, k)^m end:
Note that in this function the factor of binomial(n, k)^m can also be written as a sum.

The special case H(m, 2n, n) is particularly simple:
H(m,2n,n) = C(2n,n)^(m+1)*((n+1)^(m+1)n^(m+1))/(n+1)^m.
Next we look at the row sums of these triangles.
J := proc(m, n) local k; add(H(m, n, k),k=0..n) end:
A000079(n) = Sum{k=0..n} A007318(n,k) = J(1,n) A001700(n) = Sum{k=0..n} A103371(n,k) = J(2,n) A197657(n) = Sum{k=0..n} A194595(n,k) = J(3,n) A198256(n) = Sum{k=0..n} A197653(n,k) = J(4,n) A198257(n) = Sum{k=0..n} A197654(n,k) = J(5,n) A198258(n) = Sum{k=0..n} A197655(n,k) = J(6,n)

These sums are the answer to our problem. Thus J(m, n) is the number of ways a meander can be drawn by m(n+1) arcs with a central angle of 360/m degrees and of equal length, starting with a positively oriented arc.
Walks on a circle
We give another interpretation of the meanders as walks on a circle, starting and ending in the same point. Now a 'step' equates to an 'arc' and the 'orientation' (positively/negatively) to the 'direction' (forward/backwards). This gives a bijection between the meanders and the walks on the circle subject to the meander condition. The problem can now be restated as:
How many walks on the circle exist returning to the start with m(n+1) steps with m(k+1) forward steps and m(nk) backward steps, provided that the first step is a forward step and each sector is visited with equal frequency.
A script for plotting these walks with Asymptote is given below. It requires as an input a binary representation of the walk given as a list of L's and R's which denote the direction (respectively the orientation) of the step.
// Walks on the circle. size(200,200); int deg = 60; int a = deg; int b = 0; real r = 0.3; bool dir = CCW; // CounterClockWise bool L = true, R = false; bool lastDir = L; pen PurplePen = purple+0.5mm; pen OrangePen = orange+0.5mm; pen Pen = OrangePen; void Step(bool dir) { if(lastDir == dir) { int i = dir ? deg : deg; a += i; b += i; } else { int c = a; a = b; b = c; r += 0.1; Pen = dir ? OrangePen : PurplePen; lastDir = dir; } draw(arc((0,0),r,a,b,lastDir),Pen,Arrow(2mm)); } void Walk(bool[] s) { for(bool s : S) Step(s); } // m = 6, 360/m = 60 deg, n = 4, k = 2, // (k+1)*m = 18 forward steps ('L'), // (nk)*m = 12 backward steps ('R'), 30 steps in total. bool[] steps = {L,L,L,L,R,L,L,R,L,L,R,L,R,R,L,L,L,L,L,R,R,L,L,L,R,R,R,R,L,R}; Walk(steps); shipout("WalkingTheCircle", bbox(0.3cm));
Safe cracking
Visualize a safe and the movements of the lock necessary to open the safe. These movements can be interpreted as a walk on a circle. Fix a carve on the moveable part of the lock, say at the number 0, and watch this carve when opening the safe. The trace of the carve will look like a walk on a circle as in the plot above.
Image: Combinatoria by rpongsaj, Boston Public Library.
Wienand's question can now be rephrased as: How many secret codes exist if the structural design of the lock was a meander?
What we need next is a way to generate all possible secret codes fast. Then it is not difficult to build a device which can crack a meander lock by trying the codes. We will for obvious reasons not enlarge upon this topic. But you can watch a similar device in action on YouTube, a robotic safe cracker.
Generating meanders
Still we have to find a way to generate meanders. Susanne Wienand gives a brute force search on her user page. A 'brute force search' here means that all 2^n combinations are tested whether they satisfy the meander condition.
We will give a version which makes use of the modular structure of the problem, i.e. that (k+1)m forward steps and (nk)m are backward steps are looked for. This reduces the number of test cases considerably. The implementation is in Sage.
Basically it consists of three simple functions:
 parts
Lists the partitions which are the candidates to be scanned.  isMeander
Tests if a binary curve is a meander. (This function was given above.)  generateMeanders
Filters the candidates according to the criterion.
def parts(m, len) : a = m p = [] while True : b = len  a if a > len : break p.append([a, b]) a = a + m return p def generateMeanders(m, len) : count = 0 P = parts(m, len) for p in P : S = [True for i in range(p[0])]+[False for j in range(p[1])] for c in Permutations(S) : if not c[0] : continue if isMeander(m, c) : count = count + 1 PrintAsBinaryString(c) return count
A faster version written in C# can be found on the author's homepage.
Representing the meanders as binary strings ('L' maps to '1' and 'R' maps to '0') we give
some examples of simple cases. The meanders are listed in the coolex order as
given by the C# program.
m  len  card  meander  m  len  card  meander 
1  3  4 
100 
3  9  22 
100000011 
2  6  10 
100001 

3  6  4 
100011 

4  8  5 
10000111 
Meanders of length n
Let us look now at meanders of length n. They come in two flavors: First we count all meanders and then only those with central angle < 360°.
len  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 
A199932  1  3  5  12  17  47  65  169  279  645  1025  2698  4097  9917  17345 
A200062  0  1  1  4  1  15  1  41  23  133  1  650  1  1725  961 
Three observations are immediate:
 A200062(n) = A199932(n) − 2^(n1).
 A200062(n) = 1 if and only if n is prime.
 A199932(n) = 2^(n1) + 1 iff n is prime.
The first observation comes from the fact that meanders with central angle equal to 360° are counted by the (n1)th row of Pascal's triangle. The second observation is obviously true. The third is a consequence of the first two facts.
Here you can download the plots as a pdf for the cases n = 6, n = 8 and n = 9.
More generally we might look at the table of meanders of length n and central angle 360/m. In this funny shaped table the nonzero entries in the rows are indexed by the divisors of n. For example the values in row 12 refer to meanders with central angle 360/m where m = 1, 2, 3, 4, 6 and 12 respectively.
n \ m  1  2  3  4  5  6  Sum 
1  1  1  
2  2  1  3  
3  4  1  5  
4  8  3  1  12  
5  16  1  17  
6  32  10  4  1  47  
7  64  65  
8  128  35  5  169  
9  256  22  279  
10  512  126  6  645  
11  1024  1025  
12  2048  462  134  46  7  2698  
13  4096  4097  
14  8192  1716  9917  
15  16384  866  94  17345  
16  32768  6435  485  39698  
17  65536  65537  
18  131072  24310  5812  190  161395  
19  262144  262145  
20  524288  92378  5626  1700  624004  
21  1048576  40048  1089007  
OEIS  A000079  A001700  A197657  A198256  A198257  A199932 
This table read by rows is A200583. Another systematic overview with a formula which covers all cases is given by A198060. One might also observe the curved diagonals, for example the third one 4, 10, 22, 46, 94, 190,... which is A099018 (A033484).
Looking at the row sums we are indeed back at an extended version of the formula given above as the first step. It can be written as:
A199932(n) = Sum_{dn} A198060(d−1,n/d−1).
In other symbols, the meanders of length n are given by:

For those who whish to test such a formidable formula we offer a Maple snippet.
M := proc(n) local d, k, j, i; add(add(add(add( (1)^(j+i)*binomial(i,j)*binomial(n/d1,k)^d*((n/d)/(k+1))^j, i=0..d1),j=0..d1),k=0..(n/d1)),d=numtheory[divisors](n))end:
Invertible meanders
A meander a = (a_1, .., a_n) is invertible if and only if
a* := (~a_n, .., ~a_(nk+1), .., ~a_1) is a meander.
In this case we call a* the dual of a (or the reversed complement of a).
Here '~' denotes the negation operator and in the definition of the meander 'L' and 'R' is to be read as the Boolean values 'true' and 'false' respectively.
Examples:
 (10001010)* = 10101110.
 The binary sequence (6, 110011101) is a meander but is not an invertible meander.
 The figure below shows an invertible meander and its dual.
A more functional way to express these relations is:
Let {0,1}^n denote the set of all strings of length n with values 0 or 1. Then define an operator R : {0,1}^n → {0,1}^n which reverses a string and an operator ' : {0,1}^n → {0,1}^n which complements bitwise the values of the string, setting 0' = 1 and 1' = 0. Then M* = R(M'). Clearly M** = M since R(R(M')') = R(s_n, ..., s_1) = R(s_n, ..., s_1) = (s_1, ..., s_n) = M.
Proposition: Let M be (the binary representation of) a meander. Then M* is a meander if and only if the last bit of M is 0.
'→' If M* is a meander then it starts with bit 1. Thus M = M** = R(M*') = R(1',...,s_n') = (s_n',...,0).
'←' Since the last bit of M is 0 the first bit of M* is 1. We have to check that the directions of M* appear equally often.
Since M is a meander every direction in M will lead to a direction in M* of the opposite kind. In fact DIR(M*) is the reverse
of DIR(M) and therefore a direction is assumed with equal frequency in M and in M*. Thus M* is indeed a meander. q.e.d.
The table below counts the invertible meanders of length n and of type m.
n \ m  1  2  3  4  5  6  7  Sum 
1  0  0  
2  1  0  1  
3  2  0  2  
4  4  1  0  5  
5  8  0  8  
6  16  4  1  0  21  
7  32  0  32  
8  64  15  1  80  
9  128  8  136  
10  256  56  1  313  
11  512  512  
12  1024  210  54  16  1  1305  
13  2048  2048  
14  4096  792  1  4889  
15  8192  368  32  8592  
16  16384  3003  189  19577  
17  32768  32768  
18  65536  11440  2550  64  79591  
19  131072  131072  
20  262144  43758  2336  648  308886  
21  524288  17952  128  542368  
OEIS  A000079  A001791  A201640  A201642 
New sequences are A201640 = 0, 1, 8, 54, 368, 2550, 17952, 128086, ...
and in the case m = 4 the sequence 0, 1, 16, 189, 2336, 29750, 389712, ...
Again the columns of the tables can be seen as the row sums of symmetric triangles similar to Pascal's triangle. These triangles classify the invertible meanders on a finer scale by looking at their binary sum. (The binary sum of a meander is the sum of the binary digits of the binary representation of the meander, for instance the binary sum of 110011101 is 6.)
Case m = 2: A001791 are the row sums of the triangle A132812.
A132812 := (n,k) > (nk)*binomial(n,k)^2/(1+k); 0 1, 0 2, 2, 0 3, 9, 3, 0 4, 24, 24, 4, 0 5, 50, 100, 50, 5, 0 6, 90, 300, 300, 90, 6, 0 7, 147, 735, 1225, 735, 147, 7, 0
Case m = 3: A201640 are the row sums the triangle A202409:
A202409 := (n,k) > `if`(n=0,0, (nk)*binomial(n,k)^3*(n^2k*n+k+k^2)/((1+k)^2*n)); 0, 1, 0, 4, 4, 0, 9, 36, 9, 0, 16, 168, 168, 16, 0, 25, 55, 140, 55, 25, 0, 36, 1440, 7500, 7500, 1440, 36, 0, 49, 3234, 30135, 61250, 30135, 3234, 49, 0,
In general the mth column lists the row sums of the triangle A_m where A_m(n, k) is the number of meanders of length (n+1)m which have binary sum mk.
For example the entry in the table for n = 12 and m = 3 says that there are 54 invertible meanders of length 12 and modulus 3. The 3rd row of the triangle A202409, which is [9, 36, 9], tells us that 9 of those have binary sum 3, 36 have binary sum 6 and 9 binary sum 9.
Noninvertible meanders
The table below counts the noninvertible meanders of length n and of type m.
n \ m  1  2  3  4  5  6  7  Sum 
1  1  1  
2  1  1  2  
3  2  1  3  
4  4  2  1  7  
5  8  1  9  
6  16  6  3  1  26  
7  32  1  33  
8  64  20  4  89  
9  128  14  143  
10  256  70  5  332  
11  512  513  
12  1024  252  80  30  6  1393  
13  2048  2049  
14  4096  924  7  5028  
15  8192  498  62  8753  
16  16384  3432  296  20121  
17  32768  32769  
18  65536  12870  3262  126  81804  
19  131072  131073  
20  262144  48620  3290  1052  315118  
21  524288  22096  254  546639  
OEIS  A000079  A000984  A202410  A202411 
New sequences are A202410 = 1, 3, 14, 80, 498, 3262, 22096, ...
and in the case m = 4 the sequence 1, 4, 30, 296, 3290, 39312, ...
Again the columns of the tables can be seen as the row sums of triangles. These triangles classify the noninvertible meanders by their binary sum.
Case m = 2: A000984 are the row sums of the triangle A008459.
Thus the number of noninvertible meanders classified by their binary sum are in the case m = 2 the square of the entries of Pascal's triangle.
A008459 := (n,k) > binomial(n,k)^2; 1 1, 1 1, 4, 1 1, 9, 9, 1 1, 16, 36, 16, 1 1, 25, 100, 100, 25, 1 1, 36, 225, 400, 225, 36, 1
Case m = 3: A202410 are the row sums of the triangle A:
A := (n,k) > `if`(n=0,1, binomial(n,k)^3*(k^2k*n+n+n^2)/(n*(1+k))); 1, 2, 1, 3, 10, 1, 4, 45, 30, 1, 5, 136, 288, 68, 1, 6, 325, 1600, 1200, 130, 1, 7, 666, 6375, 11000, 3825, 222, 1,
Selfdual meanders
A meander M is selfdual if and only if M is an invertible meander and M = M*.
For example 10110010 is a selfdual meander. Note that a meander of odd length cannot be a selfdual meander. The table below enumerates the selfdual meanders.
n \ m  1  2  3  4  5  6  7  Sum 
1  0  0  
2  1  0  1  
3  0  0  0  
4  2  1  0  3  
5  0  0  0  
6  4  0  1  0  5  
7  0  0  0  
8  8  3  1  12  
9  0  0  0  
10  16  0  1  17  
11  0  0  
12  32  10  4  0  1  47  
13  0  0  
14  64  0  1  65  
15  0  0  0  0  
16  128  35  5  169  
17  0  0  
18  256  0  22  1  279  
19  0  0  
20  512  126  0  6  645  
21  0  0  0  0  
OEIS  A000079  A138364 A088218 
A197657  A198256  A198257  A199932 
The columns in this table are an aerated version of the columns of the table A200583 above. The figure below shows an example of a selfdual meander.
Next month we will look at Fibonacci meanders.
Acknowledgments
I would like to thank Susanne Wienand for helpful discussions. I also would like to acknowledge the work of the Project Euler team. It was a PEproblem that inspired this investigation.
Appendix
J(m, n) as hypergeometric sums
A000079 := n > Sum{k=0..n} A007318(n,k); h01 := n > hypergeom([n],[],1); A000079 := n > h01(n);
A001700 := n > Sum{k=0..n} A103371(n,k); h11 := n > hypergeom([n,n],[2],1); A001700 := n > (n+1)*h11(n);
A197657 := n > Sum{k=0..n} A194595(n,k); h21 := n> hypergeom([n,n,n],[2,2],1); h22 := n> hypergeom([1n,1n,1n],[3,3],1); h23 := n> hypergeom([2,1n,1n,1n],[1,3,3],1); A197657 := n > (h22(n)*(n^3n^4)+h21(n)*4*(1+n+n^2)+n^3*h23(n))/4;
A198256 := n > Sum{k=0..n} A197653(n,k); h31:= n> hypergeom([n,n,n,n],[2,2,2],1); h32:= n> hypergeom([1n,1n,1n,1n],[3,3,3],1); h33:= n> hypergeom([2,1n,1n,1n,1n],[1,3,3,3],1); A198256 := n > h32(n)*(n^4n^6)/4+h31(n)*(1+n+n^2+n^3)+h33(n)*(n^4+n^5)/4;
P(m, n, k) as binomiallike triangles
A000012(n, k) = P(0,n,k)
1 1, 1 1, 1, 1 1, 1, 1, 1 1, 1, 1, 1, 1 1, 1, 1, 1, 1, 1
A003056(n, k) = P(1,n,k)
0 1, 1 2, 2, 2 3, 3, 3, 3 4, 4, 4, 4, 4 5, 5, 5, 5, 5, 5
A073254(n, k) = P(2,n,k)
0 1, 1 4, 3, 4 9, 7, 7, 9 16, 13, 12, 13, 16 25, 21, 19, 19, 21, 25
A198063(n, k) = P(3,n,k)
0 1, 1 8, 4, 8 27, 15, 15, 27 64, 40, 32, 40, 64 125, 85, 65, 65, 85, 125
A198064(n, k) = P(4,n,k)
0 1, 1 16, 5, 16 81, 31, 31, 81 256, 121, 80, 121, 256 625, 341, 211, 211, 341, 625
A198065(n, k) = P(5,n,k).
0 1, 1 32, 6, 32 243, 63, 63, 243 1024, 364, 192, 364, 1024 3125, 1365, 665, 665, 1365, 3125