Error in A115866

[Nick Hobson]

On Sat, 03 Mar 2007 07:50:30 -0000, David W. Cantrell  
<DWCantrell at sigmaxi.net> wrote:

> On Saturday, March 03, 2007, "Nick Hobson" <nickh at qbyte.org> wrote:
>> I believe there is an error in sequence A115866: "Number of paths
>> from  (0,0,0) to (n,n,n) such that at each step (i) at least one
>> coordinate  increases, (ii) no coordinate decreases, (iii) no
>> coordinate increases by  more than 1, and (iv) all coordinates are
>> integers. This is a  3-dimensional extension to A001850."
>
> For months, I had been planning to submit that very sequence! Already
> typed in a draft of an email to have been sent to Neil, my (shorter)
> title was to have been
>

I only found A115866 by accident.  Having found A001850, I initially hit  
upon the erroneous extension to three dimensions mentioned below, and  
hence A115866.  Then I realised that the boundary cases should be handled  
as per the 2-D rather than the 1-D problem.

Why not submit the 4-D version?!

The Duchi and Sulanke reference is very interesting.

Thanks also to Max and Alec for the recurrences, and Brendan for the  
binomial sum.

Nick



> Number of paths from (0,0,0) to (n,n,n) using nonzero steps
> of the form (x(1),x(2),x(3)) where x(k) is in {0,1} for 1<=k<=3
>
> and my first comment was to have been
>
> A 3-D generalization of the central Delannoy numbers A001850.
>
> [snip]
>> I believe the sequence should begin: 1, 13, 409, 16081, 699121,
>> 32193253.   If someone can confirm these terms, I will submit a
>> correction.
>
> I confirm not only those, but also all those given by Max in his
> earlier response to you. (Of course, I had _thought_ that that
> sequence did not exist in OEIS because I had been searching for
> it _correctly_, using 13,409,16081,699121 .)
>
>> Is there  a recurrence equation for this sequence, analogous to
>> a(-1) = a(0) = 1;  n*a(n) = 3*(2*n-1)*a(n-1) - (n-1)*a(n-2), for
>> A001850 (the 2-dimensional  equivalent sequence)?
>
> Good question. I don't know. The recurrence I had used is the same as
> yours at the end below.
>
> While you're correcting the present sequence, you might also go ahead
> and give the reference
>
> E. Duchi and R. A. Sulanke, The 2^{n-1} Factor for
> Multi-Dimensional Lattice Paths with Diagonal Steps, Seminaire
> Lotharingien de Combinatoire, B51c (2004)
> http://math.boisestate.edu/~sulanke/PAPERS/DuchiSulanke.pdf
>
> which I had been planning to give.
>
> David W. Cantrell
>
>
>> Long version:
>>
>> A straightforward (though inefficient) Python function for A001850
>> (the  2-dimensional equivalent sequence) is:
>>
>> def f(a, b):
>>     if a == 0 or b == 0: return 1
>>     return f(a, b-1) + f(a-1, b) + f(a-1, b-1)
>>
>> Then...
>>
>> for n in xrange(7):
>>     print f(n, n),
>>
>> ... correctly produces:
>>
>> 1 3 13 63 321 1683 8989
>>
>> A generalisation to three dimensions of the above function is:
>>
>> def g(a, b, c):
>>     if a == 0 or b == 0 or c == 0: return 1
>>     return g(a, b, c-1) + g(a, b-1, c) + g(a-1, b, c) + g(a, b-1,
>> c-1)  + g(a-1, b, c-1) + g(a-1, b-1, c) + g(a-1, b-1, c-1)
>>
>> This function produces the sequence currently listed under A115866:
>> 1, 7,  157, 5419, 220561, 9763807, ... .  However, this
>> generalisation does not  match the description of A115866; it
>> incorrectly assumes that as soon as  one coordinate reaches n, there
>> is only one possible continuation.  I  think a correct
>> generalisation is:
>>
>> def f(a, b):
>>     if a == 0 or b == 0: return 1
>>     return f(a, b-1) + f(a-1, b) + f(a-1, b-1)
>>
>> def g(a, b, c):
>> if a == 0: return f(b, c)
>> if b == 0: return f(c, a)
>> if c == 0: return f(a, b)
>> return g(a, b, c-1) + g(a, b-1, c) + g(a-1, b, c) + g(a, b-1, c-1)
>> + g(a-1, b, c-1) + g(a-1, b-1, c) + g(a-1, b-1, c-1)
>>
>> Then...
>>
>> for n in xrange(6):
>>     print g(n, n, n),
>>
>> ... produces:1 13 409 16081 699121 32193253
>
>





About A115866:  I will keep the old terms but change the
description to what Nick found; the corrected analogue of A001850
will be a new sequence A126086.

Thanks to Nick for finding this error,
and thanks also to everyone who contributed

Neil




Dear Seqfans,  A friend in the math. dept. at Rutgers, Chuck Weibel
(not a member of this list) asks:


...
Back in February 2004 we had a discussion which led to your online
GCD(n,N(n))=1). I just noticed that its PIN plot is close to linear.
Althought there are only 17 entries, it is close to a(n) ~ n/50.

This led me to consider sequence A073277 (irregular primes with
irregularity index 2), whose graph is more complete and also very
close to linear: a(n) ~ n/100.

Similarly, the sequence A060975 of irregular primes with irregularity 
index=3 are close to the linear graph a(n) ~ a/1000.


Of course these are generated as unions of sequences of arithmetic
progressions, multiples of 228, 284 and 914 accounting for a small
piece of the n/50 in A090943: the 284 & 228 give approximately the linear
first gives about half the points plotted and the second gives only one.
The next sequence is roughly 914+(10^6)*n and gives one more point.
This does not really answer the question, just shows that the answer is
nuanced.
...

Can anyone on this list suggest an explanation?

Neil