This site is supported by donations to The OEIS Foundation.

User:Susanne Wienand

From OeisWiki

Jump to: navigation, search


About me

I am an engineer of chemical technics, though with few and long ago working experience (graduation in 1988, TU Dortmund).
One of my hobbies are mathematical online games where regularly problems are published to be solved by the users.
If I do not find a fast solution for a problem, I mostly calculate results for small parameters and look for a pattern. The OEIS is helpful to find such patterns. It is a very nice encyclopedia.
I registered at the OEIS in order to submit a pattern which I had used to solve a problem of project euler.

Sequences which I submitted

I submitted A194595, A197653, A197654, A197655, A197657, A198256, A198257 and A198258. These are number triangles and their row sums. They are about a certain kind of binary curves for which Peter Luschny introduced the name 'meander'. You can find much information about this kind of meanders on his user page in his BLOG on OEIS (Meanders and walks on the circle and Fibonacci Meanders).

Definition of meanders concerned by these sequences

A binary curve C is a triple (m, S, dir) such that

  1. S is a list with values in {L,R} which starts with an L,
  2. dir is a list of m different values, each value of S being allocated a value of dir,
  3. consecutive Ls increment the index of dir,
  4. consecutive Rs decrement the index of dir,
  5. the integer m>0 divides the length of S and
  6. C is a meander if each value of dir occurs length(S)/m times.

An example of a meander

Below a meander is shown. The list S consists of 24 elements with values of either 'L' or 'R' and starts with an 'L'. The values of dir are 0, 1 or 2. Each of them occurs eight times in the course of the curve.

The meander is illustrated as a curve of arcs with 120° (plotted by the help of the vector graphics language Asymptote and Windows Paint).


In the illustration there are arcs which coincide, so a point moving along the curve shows the meander more clearly.


The animation is plotted by the help of sage (version 4.8).

Counting amounts of meanders

The following brute force code counts the amounts of meanders for a certain value of m, a certain length of S and different compositions of S. S is initialized as an array which consists of a one ensued by length-1 zeroes. The one stands for an L and the zeroes stand for Rs. S is incremented until it consists just of ones. For each state of S, it is tested if all values of dir are allocated length(S)/m times to a value of S. If this is the case, the curve is counted as a meander.


using System;
namespace count_meanders
    class Program
        static int length = 1;
        static int[] S = new int[length];
        static int m = 1;
        static int[] count_dir = new int[m];
        static int dir = 0;
        static int max = length / m;
        static int[] amount_L = new int[length + 1];
        static long amount_total = 0;
        static void Main(string[] args)
            if (length % m != 0)
                Console.WriteLine("m does not divide the length of S.");
                S[0] = 1;
                while (count_up() == true)
                int sum = 0;
                for (int i = m; i <= length; i += m)      //print a row of the number triangle
                    sum += amount_L[i];
                    Console.Write("counted meanders with " + i + " Ls: " + amount_L[i]);
                    if (i < length)
                Console.WriteLine("     sum: " + sum);                            //row sum
                Console.WriteLine("totally counted meanders: " + amount_total);   //row sum
        static void test()
            int Ls = 1;
            for (int i = 0; i < m; i++)
                count_dir[i] = 0;
            dir = 0;
            for (int i = 1; i < length; i++)
                if (S[i] == 1 && S[i - 1] == 1)
                    dir = (dir + 1) % m;
                if (S[i] == 0 && S[i - 1] == 0)
                    dir = (dir - 1 + m) % m;
                if (++count_dir[dir] > max)
                if (S[i] == 1)
        static bool count_up()
            int index = length-1;
            while (S[index] == 1)
                S[index] = 0;
                if (index <= 0)
                    return false;
            S[index] = 1;
            return true;

Some results of this counting for small values of length(S) are summarized in the tables below.

File:Table_1.png File:Table_2.png File:Table_3.png File:Table_4.png File:Table_5.png File:Table_6.png File:Table_7.png

The tables match with the number triangles

  1. A007318 (Pascal's triangle) (m=1)
  2. A103371 (m=2)
  3. A194595 (m=3)
  4. A197653 (m=4)
  5. A197654 (m=5)
  6. A197655 (m=6)

For m=1, the amounts of meanders with a certain length and a certain number of Ls are found in A007318. For m=1, there is only one value of dir, so that in this case all binary strings of Ls and Rs which begin with an L are meanders. If the list S has a length of (n+1)\cdot1 = n+1 and contains (k+1)\cdot1 = k+1 Ls, there are n positions for k Ls (the first element in S is always an L). The number of ways to build up such strings is \binom{n}{k}, the values in Pascal's triangle. However, if m exceeds 1, it is not yet proved for any length of S that the triangles match with the amounts of meanders.

How to determine amounts of meanders faster

So far, you saw a brute force method to determine and count the meanders. Peter Luschny describes an improved approach in his blog, under generating meanders. Using brute force, you know all meanders which are counted exactly.
However, in order to know how many meanders with a certain amount of Ls and Rs exist, dynamic programming can do the work. Start with one curve that consists of an L. Say it has got direction 0. It can be extended by either an R or an L and thus is the predecessor of two possible curves of length two. Add Rs and Ls until the whished-for length of curve is reached and keep track of the data needed to sum up the relevant binary curves: The total amount of Ls, the total amount of Rs, the last character, the direction resulting from that character and also how often each direction occurred. Concatenated to a string, these data can be the key of a hash. It's value can contain the amount of meanders belonging to that key. At last all curves with the required amounts of Ls and Rs for which all directions occurred equally often, are summed up, yet the exact course of these curves is unknown.

Comparison of brute force and dynamic programming

Below, in two tables an example of brute force and an example of dynamic programming for counting meanders of length 6 which contain three Ls and have a central angle of 120° are shown. The frequencies of the directions are denoted by f0, f1, and f2. The meanders are marked by an x.

brute force
dynamic programming
lengthno. of predecessoramount of Lsamount of Rslast characterlast directionf0f1f2no.remarks
2.221L03discarded, f0 too big
43.14discarded, too many Ls
3.231L113discarded, f1 too big
54.14discarded, too many Ls
4.232L03discarded, f0 too big
4.332L03discarded, f0 too big
4.323R2203discarded, f2 too big
4.414discarded, too many Rs
65.14discarded, too many Ls
5.224discarded, too many Rs
5.324discarded, too many Rs

As with the brute force method, dynamic programming counts three meanders, one of them ending with character R and direction 0, two of them ending with character L and direction 2. These two, numbered by 6.2, can be pooled under the same key.

A dynamic programming code to count meanders


Example of a meander counted by A197654


The curve is plotted by Asymptote Vector Graphics Language and the text is inserted by Microsoft Paint.

Asymptote-code for this plot:

import settings;
int m = 5;
string[] S = {"L","R","R","R","R","R","L","L","R","L","R","R","L","R","R","R","R","L","R","L","L","L","R","R","L"};
real angle = 360/m;
real x_m = 0;
real y_m = 0;
real a_0 = 0;
real a_1 = angle;
for (int i = 1; i <S.length; ++i)
      if (S[i] == "L" && S[i-1] == "L")
              a_0 = a_1;
              a_1 += angle;
      if (S[i] == "R" && S[i-1] == "R")
              a_0 = a_1;
              a_1 -= angle;
      if (S[i] == "L" && S[i-1] == "R")
              x_m += 2*cos(a_1*pi/180);
              y_m += 2*sin(a_1*pi/180);
              a_0 = a_1 - 180;
              a_1 = a_1 - 180 + angle;
      if (S[i] == "R" && S[i-1] == "L")
             x_m += 2*cos(a_1*pi/180);
             y_m += 2*sin(a_1*pi/180);
             a_0 = a_1 + 180;
             a_1 = a_1 + 180 - angle;
shipout("example of a meander", bbox(0.3cm));

Personal tools