[seqfan] Re: a last-minute entry for the A200000 race
Benoît Jubin
benoit.jubin at gmail.com
Wed Nov 23 08:36:19 CET 2011
On Tue, Nov 22, 2011 at 8:24 PM, Jon Wild <wild at music.mcgill.ca> wrote:
>
> 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.)
Then also add to A078008 the recurrence I found in the previous email,
and the relation A078008(n+1) = 2*A001045(n). Thanks!
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/
>>
>>
>
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
More information about the SeqFan
mailing list