This site is supported by donations to The OEIS Foundation.
User:Peter Luschny/Meander
Contents
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.
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..m-1] 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[n-1]] = 1 if S[n] = Y and S[n-1] = 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,..,m-1 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, (n-k)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:
|
|
![{\displaystyle T(m,n,k)={\binom {n}{k}}^{m}+\left[m>1\right]{\binom {n}{k}}T(m-1,n,n-1-k).}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/71390f17d64a53048029517572c735535f620e26)
Or with Maple:
T := proc(m, n, k) local b; b := binomial(n, k);
if m > 1 then b := b * (b^(m-1) + T(m-1,n,n-1-k)) 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^(m-j)
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^2-kn+n^2 | (5n^3+6n^2+n)/6 | A033994 |
| P(3,n,k) | A198063 | 2k^2n-2kn^2+n^3 | (2n^4+3n^3 +n^2)/3 |
A098077 |
| P(4,n,k) | A198064 | k^4-2k^3n+4k^2n^2 -3kn^3+n^4 |
(16n^5+30n^4 +15n^3-n)/30 |
|
| P(5,n,k) | A198065 | 3nk^4-6k^3n^2 +7k^2n^3-4kn^4+n^5 |
(13n^6+30n^5 +20n^4-3n^2)/30 |
A simple way to compute this family of sequences is:
G := proc(m, n, k) if n = 2*k then m*k^(m-1)
else (k^m-(n-k)^m)/(2*k-n) fi end:
Then G(m, n, k) = P(m-1, 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-((n-k)/(1+k))^m)/(1+2*k-n) 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(n-k) 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'),
// (n-k)*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 (n-k)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^(n-1).
- A200062(n) = 1 if and only if n is prime.
- A199932(n) = 2^(n-1) + 1 iff n is prime.
The first observation comes from the fact that meanders with central angle equal to 360° are counted by the (n-1)-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_{d|n} 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/d-1,k)^d*((n/d)/(k+1))^j, i=0..d-1),j=0..d-1),k=0..(n/d-1)),d=numtheory[divisors](n))end:
Invertible meanders
A meander a = (a_1, .., a_n) is invertible if and only if
a* := (~a_n, .., ~a_(n-k+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 bit-wise 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 |
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) -> (n-k)*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, (n-k)*binomial(n,k)^3*(n^2-k*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 m-th 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.
Non-invertible meanders
The table below counts the non-invertible 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 |
New sequences are 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 non-invertible meanders by their binary sum.
Case m = 2: A000984 are the row sums of the triangle A008459.
Thus the number of non-invertible 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:
A := (n,k) -> `if`(n=0,1,
binomial(n,k)^3*(k^2-k*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,
Self-dual meanders
A meander M is self-dual if and only if M is an invertible meander and M = M*.
For example 10110010 is a self-dual meander. Note that a meander of odd length cannot be a self-dual meander. The table below enumerates the self-dual 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 self-dual 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 PE-problem 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([1-n,1-n,1-n],[3,3],-1); h23 := n-> hypergeom([2,1-n,1-n,1-n],[1,3,3],-1); A197657 := n -> (h22(n)*(n^3-n^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([1-n,1-n,1-n,1-n],[3,3,3],1); h33:= n-> hypergeom([2,1-n,1-n,1-n,1-n],[1,3,3,3],1); A198256 := n -> h32(n)*(n^4-n^6)/4+h31(n)*(1+n+n^2+n^3)+h33(n)*(n^4+n^5)/4;
P(m, n, k) as binomial-like 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
