%I #81 Feb 11 2024 12:41:58
%S 1,13,409,16081,699121,32193253,1538743249,75494983297,3776339263873,
%T 191731486403293,9850349744182729,510958871182549297,
%U 26716694098174738321,1406361374518034383189,74456543501901550262689,3961518532003397434536961,211689479080817606497324033
%N 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.
%C Also, the number of alignments for 3 sequences of length n each (Slowinski 1998).
%C This is a 3-dimensional generalization of A001850.
%H Alois P. Heinz, <a href="/A126086/b126086.txt">Table of n, a(n) for n = 0..500</a> (first 101 terms from Nick Hobson)
%H A. Bostan, S. Boukraa, J.-M. Maillard, and J.-A. Weil, <a href="http://arxiv.org/abs/1507.03227">Diagonals of rational functions and selected differential Galois groups</a>, arXiv preprint arXiv:1507.03227 [math-ph], 2015.
%H E. Duchi and R. A. Sulanke, <a href="http://www.mat.univie.ac.at/~slc/s/s51duchisul.html">The 2^{n-1} Factor for Multi-Dimensional Lattice Paths with Diagonal Steps</a>, Séminaire Lotharingien de Combinatoire, B51c (2004).
%H Steffen Eger, <a href="http://arxiv.org/abs/1511.00622">On the Number of Many-to-Many Alignments of N Sequences</a>, arXiv:1511.00622 [math.CO], 2015.
%H Steffen Eger, <a href="https://arxiv.org/abs/1704.04964">The Combinatorics of Weighted Vector Compositions</a>, arXiv:1704.04964 [math.CO], 2017.
%H Nick Hobson, <a href="/A126086/a126086.py.txt">Python program</a>
%H L. Reid, <a href="http://people.missouristate.edu/lesreid/pow08_0506.html">Problem #8: How Many Paths from A to B?</a>, Missouri State University's Challenge Problem Set from the 2005-2006 academic year.
%H J. B. Slowinski, <a href="http://www.neurociencias.org.ve/cont-cursos-laboratorio-de-neurociencias-luz/Slowinski1998%20phylogenetics.pdf">The Number of Multiple Alignments</a>, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:<a href="http://dx.doi.org/10.1006/mpev.1998.0522">10.1006/mpev.1998.0522</a>
%F 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
%F For _Brendan McKay_'s explicit formula see the Maple code.
%F From _Dan Dima_, Mar 03 2007: (Start)
%F 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 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.
%F 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)
%F From David W. Cantrell (DWCantrell(AT)sigmaxi.net), Mar 03 2007: (Start)
%F 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]
%F 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.
%F For information about HypergeometricPFQRegularized, see http://functions.wolfram.com/HypergeometricFunctions/HypergeometricPFQRegularized/ . (End)
%F G.f.: hypergeom([1/3,2/3],[1], 54*x/(1-x)^3)/(1-x). - _Mark van Hoeij_, Mar 25 2012.
%F 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
%F 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
%F From _Peter Bala_, Jan 16 2020: (Start)
%F a(n) = Sum_{0 <= j, k <= n} C(n,k)*C(n,j)*C(n+k,k)*C(n+k+j,k+j). Cf. A001850 and A274668.
%F 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)
%e Illustrating a(1) = 13:
%e 000 -> 001 -> 011 -> 111
%e 000 -> 001 -> 101 -> 111
%e 000 -> 001 -> 111
%e 000 -> 010 -> 011 -> 111
%e 000 -> 010 -> 110 -> 111
%e 000 -> 010 -> 111
%e 000 -> 100 -> 101 -> 111
%e 000 -> 100 -> 110 -> 111
%e 000 -> 100 -> 111
%e 000 -> 011 -> 111
%e 000 -> 101 -> 111
%e 000 -> 110 -> 111
%e 000 -> 111
%p 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
%p seq(sum(binomial(k,n)^3/2^(k+1),k=n..infinity),n=0..10); # _Vladeta Jovovic_, Mar 01 2008
%t 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_ *)
%t 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_ *)
%o (Python) # Naive version - see link for better version.
%o def f(a, b):
%o if a == 0 or b == 0:
%o return 1
%o return f(a, b - 1) + f(a - 1, b) + f(a - 1, b - 1)
%o def g(a, b, c):
%o if a == 0:
%o return f(b, c)
%o if b == 0:
%o return f(c, a)
%o if c == 0:
%o return f(a, b)
%o return (
%o g(a, b, c - 1)
%o + g(a, b - 1, c)
%o + g(a - 1, b, c)
%o + g(a, b - 1, c - 1)
%o + g(a - 1, b, c - 1)
%o + g(a - 1, b - 1, c)
%o + g(a - 1, b - 1, c - 1)
%o )
%o for n in range(6):
%o print(g(n, n, n), end=", ")
%Y Cf. A001850, A115866, A263064, A263065.
%Y Column k=3 of A262809.
%K nonn
%O 0,2
%A _Nick Hobson_, Mar 03 2007
%E More terms from _Max Alekseyev_, Mar 03 2007