[seqfan] Re: questions about walks in the plane

Nacin, David NACIND at wpunj.edu
Sun May 31 04:57:03 CEST 2020


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



More information about the SeqFan mailing list