Error in A115866

[David W. Cantrell]

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

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