The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 10
 1, 13, 409, 16081, 699121, 32193253, 1538743249, 75494983297, 3776339263873, 191731486403293, 9850349744182729, 510958871182549297, 26716694098174738321, 1406361374518034383189, 74456543501901550262689, 3961518532003397434536961, 211689479080817606497324033 (list; graph; refs; listen; history; text; internal format)
 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 Nick Hobson and 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, 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 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 = 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. Replace leading dots with 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 range(6): .... print g(n, n, n), .... CROSSREFS Cf. A001850, A115866, A263064, A263065. Column k=3 of A262809. Sequence in context: A284824 A075672 A069876 * A055203 A088919 A201537 Adjacent sequences:  A126083 A126084 A126085 * A126087 A126088 A126089 KEYWORD nonn AUTHOR Nick Hobson (nickh(AT)qbyte.org), Mar 03 2007 EXTENSIONS More terms and g.f. from Max Alekseyev, Mar 03 2007 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 8 01:25 EDT 2020. Contains 335502 sequences. (Running on oeis4.)