# [seqfan] Re: questions about walks in the plane

John Machacek jmachacek.math at gmail.com
Sun May 31 18:10:51 CEST 2020

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