[seqfan] Re: a last-minute entry for the A200000 race

[Benoît Jubin]

Write T(n,k) for the sequence of meanders on an (n,k)-grid and S(n,k)
for the same up to symmetry, that is,
S(n,k) <= T(n,k) <= (4 or 8)*S(n,k)
depending on whether n and k are equal or different (and the second
inequality gets asymptotically closer to an equality).

Looking at the possibilities within each cell, the interior ones, the
corners and the sides, we get the upper bound (for n,k>=2)
T(n,k) <= 10^((n-2)(k-2)) * 3^(2(n+k-4))
which is of course very rough (for instance if n or k >2, the four
cells which are diagonally one cell away from a corner have only 8 and
not 10 possibilities).

The first non trivial case is k=3; let b(n)=T(n,3). Then b(2)=1,
b(3)=0 and if n>3 it is not too hard to prove that
b(n) = 2*(b(n-2)+b(n-3)+b(n-4)....+b(2))
This is (shifted) twice the sequence A001045, which also has
combinatorial definitions (and this is not by chance!).

Benoit


On Mon, Nov 21, 2011 at 8:47 PM, Jon Wild <wild at music.mcgill.ca> wrote:
> On Mon, 21 Nov 2011, franktaw at netscape.net wrote:
>
>> Is there a table for the number of meanders in an n x k rectangle?
>
> I doubt it, but in a few days when I have time I can modify my program to
> generate such a table without too much hassle.
>
> There are many other variants that need to be produced too.
>
> Thanks to all who appreciated the sequence --Jon
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>