A115866 -id:A115866 - cp's OEIS frontend

A263159 Number A(n,k) of lattice paths starting at {n}^k and ending when k or any component equals 0, using steps that decrement one or more components by one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 7, 13, 1, 1, 1, 15, 157, 63, 1, 1, 1, 31, 2101, 5419, 321, 1, 1, 1, 63, 32461, 717795, 220561, 1683, 1, 1, 1, 127, 580693, 142090291, 328504401, 9763807, 8989, 1, 1, 1, 255, 11917837, 39991899123, 944362553521, 172924236255, 454635973, 48639, 1, 1

Offset: 0

Alois P. Heinz, Oct 11 2015

			Square array A(n,k) begins:
  1, 1,    1,       1,            1,                1, ...
  1, 1,    3,       7,           15,               31, ...
  1, 1,   13,     157,         2101,            32461, ...
  1, 1,   63,    5419,       717795,        142090291, ...
  1, 1,  321,  220561,    328504401,     944362553521, ...
  1, 1, 1683, 9763807, 172924236255, 7622403922836151, ...

Alois P. Heinz, Antidiagonals n = 0..20, flattened

Columns k=0+1, 2-10 give: A000012, A001850, A115866, A263162, A263163, A263164, A263165, A263166, A263167, A263168.
Rows n=0-1 give: A000012, A255047.
Main diagonal gives A263160.
Cf. A210472, A225094, A227578, A227655, A229142, A229345, A262809.

s:= proc(n) option remember; `if`(n=0, {[]},
      map(x-> [[x[], 0], [x[], 1]][], s(n-1)))
    end:
b:= proc(l) option remember; `if`(l=[] or l[1]=0, 1,
       add((p-> `if`(p[1]<0, 0, `if`(p[1]=0, 1, b(p)))
       )(sort(l-x)), x=s(nops(l)) minus {[0$nops(l)]}))
    end:
A:= (n, k)-> b([n$k]):
seq(seq(A(n,d-n), n=0..d), d=0..10);

g[k_] := Table[Reverse[IntegerDigits[n, 2]][[;;k]], {n, 2^k+1, 2^(k+1)-1}];
b[l_] := b[l] = If[l[[1]] == 0, 1, Sum[b[Sort[l - h]], {h, g[k]}]];
a[n_, k_] := If[n == 0 || k == 0 || k == 1, 1, b[Table[n, {k}]]];
Table[a[n-k, k], {n, 0, 10}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Apr 25 2020, after Alois P. Heinz in A115866 *)

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.

Original entry on oeis.org

1, 13, 409, 16081, 699121, 32193253, 1538743249, 75494983297, 3776339263873, 191731486403293, 9850349744182729, 510958871182549297, 26716694098174738321, 1406361374518034383189, 74456543501901550262689, 3961518532003397434536961, 211689479080817606497324033

Offset: 0

Nick Hobson, Mar 03 2007

nonn

Also, the number of alignments for 3 sequences of length n each (Slowinski 1998).

This is a 3-dimensional generalization of A001850.

			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

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

Cf. A001850, A115866, A263064, A263065, A181544.

Column k=3 of A262809.

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

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 *)

# 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=", ")

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 nAlso 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} C(n,k)*C(n,j)*C(n+k,k)*C(n+k+j,k+j). Cf. A001850 and A274668.
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)

More terms from Max Alekseyev, Mar 03 2007

Showing 1-2 of 2 results.

cp's OEIS Frontend

A263159 Number A(n,k) of lattice paths starting at {n}^k and ending when k or any component equals 0, using steps that decrement one or more components by one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica