A060898 -id:A060898 - cp's OEIS frontend

A060900 Number of walks of length n on square lattice, starting at origin, staying on points with x >= 0, y <= x.

1, 2, 7, 21, 78, 260, 988, 3458, 13300, 47880, 185535, 680295, 2649570, 9841260, 38470380, 144263925, 565514586, 2136388436, 8392954570, 31893227366, 125515281892, 479240167224, 1888770070824, 7240285271492, 28569774314536, 109883747363600, 434040802086220

Offset: 0

David W. Wilson, May 05 2001

nonn

Alin Bostan, Calcul Formel pour la Combinatoire des Marches [The text is in English], Habilitation à Diriger des Recherches, Laboratoire d'Informatique de Paris Nord, Université Paris 13, December 2017; https://specfun.inria.fr/bostan/HDR.pdf

Alois P. Heinz, Table of n, a(n) for n = 0..500
A. Bostan, Computer Algebra for Lattice Path Combinatorics, Séminaire de Combinatoire Ph. Flajolet, March 28 2013.
A. Bostan, Computer Algebra for Lattice Path Combinatorics, 7th Séminaire Lotharingien de Combinatoire, Ellwangen, March 23-25, 2015.

Cf. A005566, A001700, A060897, A060898, A060899.

b:= proc(n, x, y) option remember;
      `if`(x<0 or y>x, 0, `if`(n=0, 1, add(add(
       b(n-1, x+i, y+j), j=[-1, 1]), i=[-1, 1])))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 30 2015

(* Conjectural *) a[0]=1; a[n_] := a[n] = If[EvenQ[n], (4*(3*n+1)*a[n-1])/ (3*n+2), (4*n*a[n-1])/(n+1)]; Table[a[n], {n, 0, 26}]
(* or, from 1st g.f. *) s = (HypergeometricPFQ[{-1/12, 1/4}, {2/3}, -64*x* (4*x+1)^2/(4*x-1)^4]-1)/(2*x) + O[x]^27; CoefficientList[s, x](* Jean-François Alcover, Nov 30 2015 *)

The following conjectural formula for this sequence is apparently due to Ira M. Gessel: a(0) = 1, a(2n) = a(2n-1)*(12n+2)/(3n+1), a(2n+1) = a(2n)*(4n+2)/(n+1).
G.f.: (hypergeom([ -1/12, 1/4],[2/3],-64*x*(4*x+1)^2/(4*x-1)^4)-1)/(2*x). - Mark van Hoeij, Nov 02 2009
G.f.: (T(x)-1)/(2*x) where T(x) satisfies 27*(4*x-1)^2*T^8 - 18*(4*x-1)^2*T^4 - (128*x^2+192*x+8)*T^2 - (4*x-1)^2 = 0. - Mark van Hoeij, Nov 02 2009
a(n) ~ 4^(n+1) / (sqrt(3) * Gamma(1/3) * n^(2/3)). - Vaclav Kotesovec, Sep 17 2017

Entry revised by N. J. A. Sloane at the suggestion of Doron Zeilberger, Sep 13 2007

A060897 Number of walks of length n on square lattice, starting at origin, staying in first and third quadrants.

Original entry on oeis.org

1, 4, 12, 44, 144, 528, 1808, 6676, 23536, 87568, 315136, 1180680, 4314560, 16263896, 60138816, 227899484, 850600944, 3238194560, 12177384544, 46542879384, 176110444736, 675431779856, 2568878867200, 9882068082112, 37747540858240, 145593279888736, 558190182662144

Offset: 0

David W. Wilson, May 05 2001

nonn

Is there a formula analogous to the (conjectured) formula for A060900?

Could be broken into the number of walks that are constrained to a quadrant and the number that cross the origin. (I.e., 2*A005566(n) + 2*A005566(n-2)*A005568(1) + 2*A005566(n-4)*A005568(2) + ... + All terms that cross the origin twice + three times + ... + Cross floor(n/2) times.) - Benjamin Phillabaum, Mar 13 2011

Alois P. Heinz, Table of n, a(n) for n = 0..750 (first 251 terms from Sean A. Irvine)

Cf. A005566, A005568, A001700, A060898, A060899, A060900.

\\ here B is A005566 and C is aerated A005568 as g.f.'s.
B(n)={sum(n=0, n, x^n*binomial(n, n\2)*binomial(n+1, (n+1)\2), O(x*x^n))}
C(n)={sum(n=0, (n+1)\2, x^(2*n)*binomial(2*n,n)*binomial(2*n+2,n+1)/((n+1)*(n+2)), O(x*x^n))}
seq(n) = {Vec( 1 + 2*(B(n)-1)/(2-C(n)) )} \\ Andrew Howroyd, Jan 05 2023

G.f.: 1 + 2*(B(x)-1)/(2 - C(x^2)) where B(x) is the g.f. of A005566 and C(x) is the g.f. of A005568. - Andrew Howroyd, Jan 05 2023

A060899 Number of walks of length n on square lattice, starting at origin, staying on points with x+y >= 0.

Original entry on oeis.org

1, 2, 8, 24, 96, 320, 1280, 4480, 17920, 64512, 258048, 946176, 3784704, 14057472, 56229888, 210862080, 843448320, 3186360320, 12745441280, 48432676864, 193730707456, 739699064832, 2958796259328, 11342052327424

Offset: 0

David W. Wilson, May 05 2001

The number of lattice paths consisting of 2*n steps either (1,1) or (1,-1) that return to the x-axis only at times that are a multiple of 4. - Peter Bala, Jan 02 2020

Harry J. Smith, Table of n, a(n) for n=0..200
Paul Barry, The Central Coefficients of a Family of Pascal-like Triangles and Colored Lattice Paths, J. Int. Seq., Vol. 22 (2019), Article 19.1.3.
Alin Bostan, Computer Algebra for Lattice Path Combinatorics, Séminaire de Combinatoire Ph. Flajolet, March 28 2013.
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.
Math Overflow, Combinatorial proof for the number of lattice paths that return to the axis only at times that are a multiple of 4, 2012.

Cf. A005566, A001700, A060897, A060898, A060900.

Cf. A001405.

Table[2^n Binomial[n,Floor[n/2]],{n,0,30}] (* Harvey P. Dale, Oct 15 2017 *)

{ for (n=0, 200, write("b060899.txt", n, " ", 2^n*binomial(n, n\2)); ) } \\ Harry J. Smith, Jul 14 2009

a(n) = 2^n*binomial(n, [n/2]);
G.f.: (sqrt((1+4*x)/(1-4*x))-1)/4/x. - Vladeta Jovovic, Apr 28 2003
E.g.f.: BesselI(0, 4*x)+BesselI(1, 4*x). - Vladeta Jovovic, Apr 28 2003
a(n) = 4^n*sum{k=0..n, C(n,k)C(k)/(-2)^k}, with C(n)=A000108(n). - Paul Barry, Dec 28 2006
(n+1)*a(n) -4*a(n-1) +16*(-n+1)*a(n-2)=0. - R. J. Mathar, Nov 24 2012
a(n) = (-4)^n*hypergeom([3/2,-n],[2],2). - Peter Luschny, Apr 26 2016
Sum_{n>=0} a(n)/6^n = 3/phi = A134973. - Peter McNair, Apr 30 2022
In general, for k>4, Sum_{n>=0} a(n)/k^n = (sqrt((k+4)/(k-4)) - 1) * k/4. - Vaclav Kotesovec, May 13 2022
From Amiram Eldar, May 14 2022: (Start)
Sum_{n>=0} 1/a(n) = 16*asin(1/4)/(3*sqrt(15)) + 4/3.
Sum_{n>=0} (-1)^n/a(n) = 4/5 - 16*asin(1/4)/(5*sqrt(15)). (End)

A260153 Number of walks of length n on the square lattice (with steps N, E, S, W) that start at (0,0) and avoid the West quadrant {(i,j): i < -|j|}.

Original entry on oeis.org

1, 3, 12, 41, 164, 590, 2360, 8715, 34860, 130776, 523104, 1983212, 7932848, 30303416, 121213664, 465673065, 1862692260, 7187760140, 28751040560, 111338982436, 445355929744, 1729672999418, 6918691997672, 26936111629934, 107744446519736, 420338301077100

Offset: 0

Mireille Bousquet-Mélou, Nov 09 2015

nonn

			For n=1, the three possible walks are N, E, S.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
M. Bousquet-Mélou, Plane lattice walks avoiding a quadrant, arXiv:1511.02111 [math.CO], 2015.

Cf. A060898 for walks avoiding the negative quadrant rather than the West one, A260154.

b:= proc(n,i,j) option remember;
      if i < -abs(j) then 0
    elif n=0 then 1
    else b(n-1,i-1,j)+
         b(n-1,i+1,j)+
         b(n-1,i,j-1)+
         b(n-1,i,j+1)
      fi
    end:
a:= n-> b(n,0,0);
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 09 2015
# second Maple program:
a:= proc(n) option remember; `if`(n<4, [1, 3, 12, 41][n+1],
      ((4*(2*n-5))*(12*n^4-16*n^3-6*n^2+10*n+3) *a(n-1)
      +(16*(2*n-5))*(2*n+1)*(6*n^4-24*n^3+28*n^2-8*n-3) *a(n-2)
      -(64*(2*n+1))*(12*n^4-80*n^3+186*n^2-178*n+63) *a(n-3)
      -(256*(n-1))*(2*n+1)*(2*n-1)*(3*n-7)*(n-3)^2 *a(n-4))/
      ((2*n-3)*(2*n-5)*(n-1)*(3*n+1)*(n+1)^2))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 09 2015

b[n_, i_, j_] := b[n, i, j] = Which[i < -Abs[j], 0, n == 0, 1, True, b[n-1, i-1, j] + b[n-1, i+1, j] + b[n-1, i, j-1] + b[n-1, i, j+1]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 01 2016, after Alois P. Heinz *)
With[{n = 10}, CoefficientList[Series[
-1/(4*t) + (1+4*t)*((sc+Sqrt[1+sc^2])/Sqrt[3-48*t^2] - k/(2*Pi))/(3*t)
  /. sc -> Pi*Sqrt[3]*Normal[Sum[(-1)^p/(1 + q^(-2*p) + q^(2*p)), {p,-n,n}]  + O[q]^(2*n)]/(2*k*Sqrt[1-16*t^2])
  /. q -> EllipticNomeQ[16*t^2] /. k -> EllipticK[16*t^2],
{t,0,4*n}], t]] (* Timothy Budd, Oct 23 2016 *)

G.f.: -1/(4*t) + (1+4*t) * ((sc(K(4*t)/3;4*t)+nc(K(4*t)/3;4*t))/sqrt(3-48*t^2) - K(4*t)/(2*Pi)) / (3*t), where K(4*t) is the complete elliptic integral of modulus 4*t and sc(.;4*t), nc(.;4*t) are Jacobi elliptic functions again with modulus 4*t. - Timothy Budd, Oct 23 2016

a(n) ~ Gamma(1/3) * 2^(2*n+2) / (3*Pi*n^(1/3)). - Vaclav Kotesovec, Oct 06 2019

A260155 Number of walks of length 2n on the square lattice that start and end at (0,0) and avoid the negative quadrant.

Original entry on oeis.org

1, 4, 32, 318, 3530, 41944, 522010, 6719018, 88726840, 1195527822, 16373466714, 227280520316, 3190715296368, 45226324937400, 646392346047930, 9305481272839662, 134815491199174476, 1964195875748858812, 28761433275110249932, 423052415434610432816

Offset: 0

Mireille Bousquet-Mélou, Nov 09 2015

			When n=1 the four walks are NS, EW, SN, WE.

Alois P. Heinz, Table of n, a(n) for n = 0..800
M. Bousquet-Mélou, Plane lattice walks avoiding a quadrant, arXiv:1511.02111 [math.CO], 2015.

Cf. A060898 for walks starting from (0,0) but in which the final point is not prescribed.

f[x_, n_] := x Pochhammer[x+1, n-1];
a[n_] := 4 16^n/3^5 (3^4 f[1/2, n] f[1/2, n + 1]/(f[2, n] f[2, n + 1]) + 4 (24n^2 + 60n + 29) f[1/2, n] f[7/6, n]/(f[2, n + 1] f[4/3, n + 1]) - 2 (12n^2 + 30n + 5) f[1/2, n] f[5/6, n]/(f[2, n + 1] f[5/3, n + 1]));
Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Jul 25 2018 *)

a(n) = 4*16^n/ 3^5 * ( 3^4 *f(1/2,n)* f(1/2,n+1)/ (f(2,n) * f(2,n+1)) + 4 *(24*n^2+60*n +29)* f(1/2,n)* f(7/6,n) /(f(2,n+1) *f(4/3, n+1)) -2 *(12*n^2+30*n+5) * f(1/2,n)*f(5/6,n) /(f(2,n+1)*f(5/3,n+1)) ) where f(m,n) is the ascending factorial m*(m+1)*...*(m+n-1) (proved).

cp's OEIS Frontend

A060900 Number of walks of length n on square lattice, starting at origin, staying on points with x >= 0, y <= x.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A060897 Number of walks of length n on square lattice, starting at origin, staying in first and third quadrants.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A060899 Number of walks of length n on square lattice, starting at origin, staying on points with x+y >= 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A260153 Number of walks of length n on the square lattice (with steps N, E, S, W) that start at (0,0) and avoid the West quadrant {(i,j): i < -|j|}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A260155 Number of walks of length 2n on the square lattice that start and end at (0,0) and avoid the negative quadrant.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula