OFFSET
0,2
COMMENTS
Also, the number of alignments for 3 sequences of length n each (Slowinski 1998).
This is a 3-dimensional generalization of A001850.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..500 (first 101 terms from Nick Hobson)
A. Bostan, S. Boukraa, J.-M. Maillard, and J.-A. Weil, Diagonals of rational functions and selected differential Galois groups, arXiv preprint arXiv:1507.03227 [math-ph], 2015.
E. Duchi and R. A. Sulanke, The 2^{n-1} Factor for Multi-Dimensional Lattice Paths with Diagonal Steps, Séminaire Lotharingien de Combinatoire, B51c (2004).
Steffen Eger, On the Number of Many-to-Many Alignments of N Sequences, arXiv:1511.00622 [math.CO], 2015.
Steffen Eger, The Combinatorics of Weighted Vector Compositions, arXiv:1704.04964 [math.CO], 2017.
Nick Hobson, Python program
L. Reid, Problem #8: How Many Paths from A to B?, Missouri State University's Challenge Problem Set from the 2005-2006 academic year.
J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:10.1006/mpev.1998.0522
FORMULA
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, Mar 03 2007
For Brendan McKay's explicit formula see the Maple code.
From Dan Dima, Mar 03 2007: (Start)
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)
G.f.: hypergeom([1/3,2/3],[1], 54*x/(1-x)^3)/(1-x). - Mark van Hoeij, Mar 25 2012.
Recurrence (of order 3): n^2*(3*n-4)*a(n) = (3*n-2)*(57*n^2 - 95*n + 25)*a(n-1) - (9*n^3 - 30*n^2 + 29*n - 6)*a(n-2) + (n-2)^2*(3*n-1)*a(n-3). - Vaclav Kotesovec, Mar 15 2014
a(n) ~ c * d^n / n, where d = 12*2^(2/3)+15*2^(1/3)+19 = 56.947628372041491... and c = 0.2805916350775843477992461458421909485724690193829181355064... = sqrt((6 + 5*2^(1/3) + 4*2^(2/3))/6)/(2*Pi). - Vaclav Kotesovec, Mar 15 2014, updated Mar 22 2016
From Peter Bala, Jan 16 2020: (Start)
a(n) = Sum_{0 <= j, k <= n} (-2)^(j+k)*C(n,k)*C(n,j)*C(n+k,k)*C(n+k+j,k+j). (End)
EXAMPLE
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
MAPLE
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, Mar 03 2007
seq(sum(binomial(k, n)^3/2^(k+1), k=n..infinity), n=0..10); # Vladeta Jovovic, Mar 01 2008
MATHEMATICA
m = 14; se = Series[1/(1 - x - y - z - x*y - x*z - y*z - x*y*z), {x, 0, m}, {y, 0, m}, {z, 0, m}]; a[n_] := Coefficient[se, (x*y*z)^n]; a[0] = 1; Table[a[n], {n, 0, m}] (* Jean-François Alcover, Sep 27 2011, after Max Alekseyev *)
Table[Sum[Sum[(-1)^k*Binomial[k, i]*(-1)^i*Binomial[i, n]^3, {i, n, k}], {k, n, 3*n}], {n, 0, 20}] (* Vaclav Kotesovec, Mar 15 2014, after Brendan McKay *)
PROG
(Python) # Naive version - see link for better version.
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 range(6):
print(g(n, n, n), end=", ")
CROSSREFS
KEYWORD
nonn
AUTHOR
Nick Hobson, Mar 03 2007
EXTENSIONS
More terms from Max Alekseyev, Mar 03 2007
STATUS
approved