0,2

This is a 3-dimensional generalization of A001850.

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).

Joseph B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution, Volume 10, Issue 2, October 1998, Pages 264-266.

Nick Hobson, Table on n, a(n) for n = 0..100

Nick Hobson, Python program

L. Reid, Missouri State University's Challenge Problem Page

a(n) can be computed as the coefficient of (xyz)^n in the expansion of 1 / (1-x-y-z-xy-xz-yz-xyz). Also - 2*(n+1)^2 * a(n) + (n+1)*(5n+8) * a(n+1) - 3*(37*n^2 + 146*n + 139) * a(n+2) - (55*n^2 + 389*n + 685) * a(n+3) + (n+4)^2 * a(n+4) = 0. - Max Alekseyev.

For Brendan McKay's explicit formula see the Maple code.

From Dan Dima (dimad72(AT)gmail.com), Mar 03 2007: (Start) I found the following more than a year ago when I tried to solve the puzzle at http://faculty.missouristate.edu/l/lesreid/POW08_0506.html:

I found a very simple (although infinite) sum for the number of paths from (0,0,...,0) to (a(1),a(2),...,a(k)) using "nonzero" (2^k-1) steps of the form (x(1),x(2),...,x(k)) where x(i) is in {0,1} for 1<=i<=k, k-dimensions.

f(a(1),a(2),...,a(k)) = Sum( (C(n;a(1)) * C(n;a(2)) * ... C(n;a(k))) / 2^{n+1}, {n, max(a(1),a(2),...,a(k)), infinity}), Sum( (C(n;a(1)) * C(n;a(2)) * ... C(n;a(k))) / 2^{n+1}, {n, 0, infinity}), C(n;a)=n!/a!(n-a)! & we assumed C(n;a)=0 if n<a.

Also f(a(1),a(2),...,a(k)) can be computed as the coefficient of x(1)^a(1)...x(k)^a(k) in the expansion: 1/2 * 1/(1 - (1+x(1))*...*(1+x(k))/2). (End)

From David W. Cantrell (DWCantrell(AT)sigmaxi.net), Mar 03 2007: (Start) Using pseudo-Mathematica-style notation, f(a(1),a(2),...,a(k)) is 2^(-1 - a(1)) (a(1)!)^(k-1)/(a(2)! a(3)! ... a(k)!) * HypergeometricPFQRegularized[{1, 1 + a(1), 1 + a(1),..., 1 + a(1)}, {1, 1 + a(1) - a(2), 1 + a(1) - a(3),..., 1 + a(1) - a(k)}, 1/2]

Although it should be obvious from the above that there are k denominatorial parameters, it is not obvious that there are to be (k+1) numeratorial parameters [one of which is 1 and the other k of them are 1 + a(1)]. In other words, we have P = k + 1 and Q = k.

For information about HypergeometricPFQRegularized, see http://functions.wolfram.com/HypergeometricFunctions/HypergeometricPFQRegularized/. (End)

Illustrating a(1) = 13:

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

f := proc(n) local i, k; add(add((-1)^k*binomial(k, i)*(-1)^i*binomial(i, n)^3, i=n..k), k=n..3*n) end: - Brendan McKay (bdm(AT)cs.anu.edu.au), Mar 03 2007

seq(sum(binomial(k, n)^3/2^(k+1), k=n..infinity), n=0..10); - Vladeta Jovovic (vladeta(AT)eunet.rs), Mar 01 2008

(Python. Naive version - see link for better version. Replace leading dots by spaces)

.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)

.......

.for n in xrange(6):

.... print g(n, n, n),

....

Cf. A001850. A corrected version of a sequence (A115866) submitted by Al Zimmermann (alzimmerma(AT)aol.com), Apr 02 2006

Sequence in context: A162446 A075672 A069876 this_sequence A055203 A088919 A142484

Adjacent sequences: A126083 A126084 A126085 this_sequence A126087 A126088 A126089

nonn

Nick Hobson (nickh(AT)qbyte.org), Mar 03 2007

More terms and g.f. from Max Alekseyev (maxale(AT)gmail.com), Mar 03 2007

Duchi-Sulanke reference from David W. Cantrell (DWCantrell(AT)sigmaxi.net), Mar 03 2007