[seqfan] Re: a last-minute entry for the A200000 race
Jon Wild
wild at music.mcgill.ca
Wed Nov 23 05:24:25 CET 2011
Benoît,
I just adjusted my program to enumerate meanders on an (n,k) grid. Using
your nomenclature, I found that T(n,3) is given by A078008, the expansion
of (1-x)/(1-x-2*x^2). (I'll add a comment to A078008.) And this is
interesting: S(n,3) is given by A090597, which "arises from a conjecture
about sequence of rational links with n crossings". (I'll add a comment
here, too.)
T(n,4) starts 4, 42, 199, 858, 3881, 17156... , which is not in the oeis.
Neither is S(n,4).
I'll compile proper entries for the S(n,k) and T(n,k) sequences in the
next few days. I also just realised a big speed-up in my program so I
should be able to get a bit farther in all the sequences.
--Jon
On Mon, 21 Nov 2011, Benoît Jubin wrote:
> 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/
>>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
More information about the SeqFan
mailing list