login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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. 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 xrange(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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 22 20:03 EST 2019. Contains 320403 sequences. (Running on oeis4.)