[seqfan] Re: questions about walks in the plane

[John Machacek]

Hello,

I can explain the following

%C A085363 Apparently, the number of 2-D directed walks of semilength n
starting at (0,0) and ending on the X-axis using steps NE, SE, NW and SW
avoiding adjacent NW/SE and adjacent NE/SW. - _David Scambler_, Jun 20 2013

I come up with a new formula. I wasn't able to count the walks directly
with anything in A085363. Let s(n) be the number of such 2-D directed walks
of semilength n satisfying the conditions. I claim

s(n) = Sum_{k=1..n} [2^(2*n-2*k+2)*binomial(n-1,k-1)^2 +
2^(2*n-2*k+3)*binomial(n-1,k-1)*binomial(n-1,k-2)].

Then using Zeilberger's Algorithm we find that n*s(n) = (10*n-6)*s(n-1) -
(9*n-18)*s(n-2) which is the same recursion as for a(n) in A085363. We can
check the initial values match. Therefore s(n) = a(n) = A085363(n).

To see why the s(n) formula is correct let's look at an example.

Let's look at the term 2^(2n-2k+2)*binomial(n-1,k-1)*(binomial(n-1,k-1)
with n=4 and k = 2. Here choose two integer compositions of n each with k
parts. For example, (3,1) and (2,2). We then interleave to make a word
UUUDDUDD where U means up and D means down.

UUU (D)D (U) (D)D

Now with the exception of the letters in parentheses each U can be replaced
with NE or NW and similarly each D can be replaced with SE or SW. The
letters in parentheses are forced. There are 2^5 = 2^(8 - 4 + 1) choices.
The extra factor of 2 comes from switching roles of U and D (i.e.
reflecting path over axis).

The term 2^(2*n-2*k+3)*binomial(n-1,k-1)*binomial(n-1,k-2) is similar
except you have compositions like (2,2) and (4) so a word like UUDDDDUU.

We also get two hypergeometric evaluations.

s(n) = 4^n 3F2(-n, 1+n, 1-n; 1, n; 1/4)
s(n) = (8n - 4)* 3F2(2-2n, 1-n, 1-n; 1-2n, 2; 4)

Best,
John Machacek

On Sun, May 31, 2020 at 12:10 PM John Machacek <jmachacek.math at gmail.com>
wrote:

> ...sorry typo in my previous email on the initial conditions. Of course
> a(2) = 1 since the empty walk is the unique walk of length zero.
>
> On Sun, May 31, 2020 at 12:08 PM John Machacek <jmachacek.math at gmail.com>
> wrote:
>
>> Hello,
>>
>> For A001630 the walks are "ternary" words in {-1, +1, +3}, but the
>> "length" is sum of the absolute values (as opposed to length as a word in
>> {-1, +1, +3}).
>>
>> So, a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) since
>>
>> a(n-1) accounts for walks ending with (+1)
>> a(n-2) accounts for walks ending with (+1, -1)
>> a(n-3) accounts for walks ending with (+3)
>> a(n-4) accounts for walks ending with (+3, -1).
>>
>> Then we check the initial conditions also work
>>
>> a(2) = 0: (empty)
>> a(3) = 2: (+1), (-1)
>> a(4) = 3: (+1,+1), (+1,-1), (-1,+1)
>> a(5) = 6: (+1,+1,+1), (+1,+1,-1), (+1,-1,+1), (-1,+1,+1), (-1,+1,-1), (+3)
>>
>> I don't currently have anything to say about the 2-D walks. But I'll try
>> to think about them...
>>
>> Best,
>> John Machacek
>>
>>
>> On Sun, May 31, 2020 at 3:25 AM Nacin, David <NACIND at wpunj.edu> wrote:
>>
>>> Though the last three questions are clear, I'm confused on the first.
>>> If we are talking one-D walks using +1,-1, +3 with no consecutive -1's then
>>> there must be some other restriction as well, otherwise the sequence would
>>> just contain A028859<https://oeis.org/A028859>
>>> 1,3,8,22,60,164,448,1224,... .  (It also wouldn't matter what the numbers
>>> themselves were, only that one of the numbers can't be repeated
>>> consecutively.)  What am I missing?  Does the walk have to end at a certain
>>> value?
>>>
>>> -David
>>>
>>> ________________________________
>>> From: SeqFan <seqfan-bounces at list.seqfan.eu> on behalf of Neil Sloane <
>>> njasloane at gmail.com>
>>> Sent: Thursday, May 28, 2020 12:26 PM
>>> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
>>> Subject: [seqfan] questions about walks in the plane
>>>
>>> An old friend (Kees Immink) asked me about the conjecture of David
>>> Scambler
>>> in A085363.  In fact there are 4 assertions/conjectures in the OEIS of
>>> this
>>> type: (the first is only a one-D walk)
>>>
>>> %C A001630 Apparently for n>=2 the number of 1-D walks of length n-2
>>> using
>>> steps +1, +3 and -1, avoiding consecutive -1 steps. - _David Scambler_,
>>> Jul
>>> 15 2013
>>>
>>> %C A084768 Number of directed 2-D walks of length 2n starting at (0,0)
>>> and
>>> ending on the X-axis using steps NE, SE, NE, SW and avoiding NE followed
>>> by
>>> SE. - _David Scambler_, Jun 24 2013
>>>
>>> %C A085363 Apparently, the number of 2-D directed walks of semilength n
>>> starting at (0,0) and ending on the X-axis using steps NE, SE, NW and SW
>>> avoiding adjacent NW/SE and adjacent NE/SW. - _David Scambler_, Jun 20
>>> 2013
>>>
>>> %C A101500 Directed 2-D walks with n steps starting at (0,0) and ending
>>> on
>>> the X-axis using steps N,S,E,W and avoiding N followed by S. - _David
>>> Scambler_, Jun 24 2013
>>>
>>> I know we have several experts here - could someone help and provide
>>> proofs?
>>>
>>> The third question is the following:
>>> Let a(n) = the number of 2-D directed walks of semilength n starting at
>>> (0,0) and ending on the X-axis using steps NE, SE, NW and SW avoiding
>>> adjacent NW/SE and adjacent NE/SW
>>> Show that this satisfies the recurrence
>>> a(0)=1; for n>0: a(n) = 4*9^(n-1) - (1/2)*Sum_{i=1..n-1} a(i)*a(n-i).
>>>
>>> (The second and fourth questions are stated as if they are theorems, but
>>> no
>>> proof is given.)
>>>
>>> Neil
>>>
>>> --
>>> Seqfan Mailing list -
>>> https://nam11.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=01%7C01%7C%7Ce198304f85fa4fff06d108d804520b8a%7C74540637643546cc87a46d38efb78538%7C0&sdata=DzmnJsOnapeI6w15s1%2FMrnFBFPcQvW%2FCkFOw6mLibDY%3D&reserved=0
>>>
>>> --
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>