Error in A115866
Nick Hobson
nickh at qbyte.org
Sat Mar 3 05:57:26 CET 2007
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
More information about the SeqFan
mailing list