This site is supported by donations to The OEIS Foundation.

User:Susanne Wienand

From OeisWiki

Jump to: navigation, search

Contents

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).


File:Meander,_m=3.png

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

File:Meander_m=3.gif

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.

c#-code:

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.");
            else
            {
                S[0] = 1;
                test();
                while (count_up() == true)
                    test();
                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();
                }
                Console.WriteLine("     sum: " + sum);                            //row sum
                Console.WriteLine();
                Console.WriteLine("totally counted meanders: " + amount_total);   //row sum
                Console.ReadLine();
            }
        }
        static void test()
        {
            int Ls = 1;
            for (int i = 0; i < m; i++)
                count_dir[i] = 0;
            dir = 0;
            count_dir[dir]++;
            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)
                    return;
                if (S[i] == 1)
                    Ls++;
            }
            amount_L[Ls]++;
            amount_total++;
        }
        static bool count_up()
        {
            int index = length-1;
            while (S[index] == 1)
            {
                S[index] = 0;
                index--;
                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 it is obvious that 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.

Example of a meander counted by A197654

File:Exa.png

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

Asymptote-code for this plot:

import settings;
size(8cm,0);
outformat="pdf";
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;
draw(arc((x_m,y_m),1,a_0,a_1),orange,ArcArrow);
for (int i = 1; i <S.length; ++i)
{
      if (S[i] == "L" && S[i-1] == "L")
      {
              a_0 = a_1;
              a_1 += angle;
              draw(arc((x_m,y_m),1,a_0,a_1),orange,ArcArrow);
      }
      if (S[i] == "R" && S[i-1] == "R")
      {
              a_0 = a_1;
              a_1 -= angle;
              draw(arc((x_m,y_m),1,a_0,a_1),heavygreen,ArcArrow);
      }
      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;
              draw(arc((x_m,y_m),1,a_0,a_1),orange,ArcArrow);
      }
      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;
             draw(arc((x_m,y_m),1,a_0,a_1),heavygreen,ArcArrow);
      }
}
dot((1,0),black);
shipout("example of a meander", bbox(0.3cm));

Personal tools