Error in A115866

[Nick Hobson]

Hi Seqfans,

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."  I think a(1) = 13.  Listing the  
paths (omitting commas and parentheses, for brevity):

000 -> 001 -> 011 -> 111
000 -> 001 -> 101 -> 111
000 -> 001 -> 111
000 -> 010 -> 011 -> 111
000 -> 010 -> 110 -> 111
000 -> 010 -> 111
000 -> 100 -> 101 -> 111
000 -> 100 -> 110 -> 111
000 -> 100 -> 111
000 -> 011 -> 111
000 -> 101 -> 111
000 -> 110 -> 111
000 -> 111

Short version:

I believe the sequence should begin: 1, 13, 409, 16081, 699121, 32193253.   
If someone can confirm these terms, I will submit a correction.  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)?

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

Nick