cp's OEIS Frontend

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

%I A126086 #88 Feb 20 2025 05:06:24
%S A126086 1,13,409,16081,699121,32193253,1538743249,75494983297,3776339263873,
%T A126086 191731486403293,9850349744182729,510958871182549297,
%U A126086 26716694098174738321,1406361374518034383189,74456543501901550262689,3961518532003397434536961,211689479080817606497324033
%N A126086 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 A126086 Also, the number of alignments for 3 sequences of length n each (Slowinski 1998).
%C A126086 This is a 3-dimensional generalization of A001850.
%H A126086 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 A126086 A. Bostan, S. Boukraa, J.-M. Maillard, and J.-A. Weil, <a href="https://arxiv.org/abs/1507.03227">Diagonals of rational functions and selected differential Galois groups</a>, arXiv preprint arXiv:1507.03227 [math-ph], 2015.
%H A126086 E. Duchi and R. A. Sulanke, <a href="https://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 A126086 Steffen Eger, <a href="https://arxiv.org/abs/1511.00622">On the Number of Many-to-Many Alignments of N Sequences</a>, arXiv:1511.00622 [math.CO], 2015.
%H A126086 Steffen Eger, <a href="https://arxiv.org/abs/1704.04964">The Combinatorics of Weighted Vector Compositions</a>, arXiv:1704.04964 [math.CO], 2017.
%H A126086 Nick Hobson, <a href="/A126086/a126086.py.txt">Python program</a>
%H A126086 L. Reid, <a href="https://problemcorner.missouristate.edu/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 A126086 J. B. Slowinski, <a href="https://web.archive.org/web/20190303041805/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 A126086 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 A126086 For _Brendan McKay_'s explicit formula see the Maple code.
%F A126086 From _Dan Dima_, Mar 03 2007: (Start)
%F A126086 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 A126086 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 A126086 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 A126086 From David W. Cantrell (DWCantrell(AT)sigmaxi.net), Mar 03 2007: (Start)
%F A126086 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 A126086 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 A126086 For information about HypergeometricPFQRegularized, see http://functions.wolfram.com/HypergeometricFunctions/HypergeometricPFQRegularized/ . (End)
%F A126086 G.f.: hypergeom([1/3,2/3],[1], 54*x/(1-x)^3)/(1-x). - _Mark van Hoeij_, Mar 25 2012.
%F A126086 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 A126086 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 A126086 From _Peter Bala_, Jan 16 2020: (Start)
%F A126086 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 A126086 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 A126086 Illustrating a(1) = 13:
%e A126086 000 -> 001 -> 011 -> 111
%e A126086 000 -> 001 -> 101 -> 111
%e A126086 000 -> 001 -> 111
%e A126086 000 -> 010 -> 011 -> 111
%e A126086 000 -> 010 -> 110 -> 111
%e A126086 000 -> 010 -> 111
%e A126086 000 -> 100 -> 101 -> 111
%e A126086 000 -> 100 -> 110 -> 111
%e A126086 000 -> 100 -> 111
%e A126086 000 -> 011 -> 111
%e A126086 000 -> 101 -> 111
%e A126086 000 -> 110 -> 111
%e A126086 000 -> 111
%p A126086 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 A126086 seq(sum(binomial(k,n)^3/2^(k+1),k=n..infinity),n=0..10); # _Vladeta Jovovic_, Mar 01 2008
%t A126086 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 A126086 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 A126086 (Python) # Naive version - see link for better version.
%o A126086 def f(a, b):
%o A126086     if a == 0 or b == 0:
%o A126086         return 1
%o A126086     return f(a, b - 1) + f(a - 1, b) + f(a - 1, b - 1)
%o A126086 def g(a, b, c):
%o A126086     if a == 0:
%o A126086         return f(b, c)
%o A126086     if b == 0:
%o A126086         return f(c, a)
%o A126086     if c == 0:
%o A126086         return f(a, b)
%o A126086     return (
%o A126086         g(a, b, c - 1)
%o A126086         + g(a, b - 1, c)
%o A126086         + g(a - 1, b, c)
%o A126086         + g(a, b - 1, c - 1)
%o A126086         + g(a - 1, b, c - 1)
%o A126086         + g(a - 1, b - 1, c)
%o A126086         + g(a - 1, b - 1, c - 1)
%o A126086     )
%o A126086 for n in range(6):
%o A126086     print(g(n, n, n), end=", ")
%Y A126086 Cf. A001850, A115866, A263064, A263065, A181544.
%Y A126086 Column k=3 of A262809.
%K A126086 nonn
%O A126086 0,2
%A A126086 _Nick Hobson_, Mar 03 2007
%E A126086 More terms from _Max Alekseyev_, Mar 03 2007