A054474 -id:A054474 - cp's OEIS frontend

A098070 Consider a single king on an infinite chessboard. This sequence gives number of n-move paths when king starting at origin reaches the origin again for the first time at step n.

1, 0, 8, 24, 152, 816, 5320, 33840, 229144, 1560864, 10906576, 76962912, 550406472, 3969725856, 28875757200, 211436151456, 1557623566104, 11533972310976, 85802992349344, 640901090847360, 4804716170926672, 36138383022850368, 272621594933332000

Offset: 0

Sergey Perepechko, Sep 13 2004

nonn

Traditionally for the "first passage time" problems use initial condition Gf(0)=0, but here we define Gf(0)=1 to make this sequence consistent with similar sequences already present in the database.

			From _Jesiah Darnell_, Sep 22 2023: (Start)
A094061(4) - (a(1)a(3)*2 + a(2)*a(2)*1) = 216 - (0 + 64) = 152, so a(4) = 152.
A094061(7) - (a(1)a(6)*2 + a(2)*a(2)*a(3)*3 + a(2)*a(5)*2 + a(4)*a(3)*2) = 58800 - (0 + 4608 + 13056 + 7296) = 33840, so a(7) = 33840. (End)

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000 (terms 0..350 from Alois P. Heinz)

Cf. A094061, A054474.

G:=t->2-Pi*(1+4*t)/2/EllipticK(4*sqrt(t*(1+t))/(1+4*t)); Gf:=convert(series(G(t),t,30),polynom): seq(print(i,coeff(Gf,t,i)),i=0..degree(Gf));

CoefficientList[Series[2-Pi/2*(1+4*x)/EllipticK[16*x*(1+x)/(1+4*x)^2],{x,0,22}],x] (* Vaclav Kotesovec, Mar 10 2014 *)

G.f.: 2-Pi/2*(1+4*x)/EllipticK(4*sqrt(x*(1+x))/(1+4*x)), (Maple notation).
G.f.: 2 - AGM(sqrt(1 - 8*x), 1 + 4*x). - Vaclav Kotesovec, Sep 30 2019
a(n) ~ 3*Pi*2^(3*n-1) / (n*log(n)^2) * (1 - 2*(gamma + 2*log(2) + 2*log(3)) / log(n) + (3*gamma^2 + 12*log(2)*gamma + 12*gamma*log(3) + 24*log(2)*log(3) + 12*log(2)^2 + 12*log(3)^2 - Pi^2/2) / log(n)^2), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Sep 30 2019
G.f.: 2 - 1/B(x) where B(x) is the g.f. of A094061. - Jesiah Darnell, Sep 22 2023

A328127 G.f.: E(4sqrt(x)) / K(4sqrt(x)), where E(), K() are complete elliptic integrals.

Original entry on oeis.org

1, -8, -16, -128, -1312, -15104, -186112, -2398208, -31898176, -434421248, -6025687552, -84808699904, -1207939190272, -17375932633088, -252046328713216, -3682284573851648, -54130292542567552, -800036763837307904, -11880834659028677632, -177181827571092267008

Offset: 0

Vaclav Kotesovec, Oct 04 2019

sign

Vaclav Kotesovec, Table of n, a(n) for n = 0..825
Vaclav Kotesovec, Graph - the asymptotic ratio (30000 terms)
Eric Weisstein's MathWorld, Complete Elliptic Integral of the First Kind.
Eric Weisstein's MathWorld, Complete Elliptic Integral of the Second Kind.

Cf. A010370, A054474, A261975, A328128.

seq(coeff(series(EllipticE(4*sqrt(x))/EllipticK(4*sqrt(x)), x, 21), x, n), n = 0..20);

CoefficientList[Series[EllipticE[16*x]/EllipticK[16*x], {x, 0, 20}], x]

a(n) ~ -2^(4*n+1) / (n * log(n)^2) * (1 - (2*gamma + 8*log(2)) / log(n) + (3*gamma^2 + 24*log(2)*gamma + 48*log(2)^2 - Pi^2/2) / log(n)^2 + (-4*gamma^3 + 2*gamma*Pi^2 - 48*gamma^2*log(2) + 8*Pi^2*log(2) - 192*gamma*log(2)^2 - 256*log(2)^3 - 8*Zeta(3)) / log(n)^3 + (5*gamma^4 - 5*gamma^2*Pi^2 + Pi^4/12 + 80*gamma^3*log(2) - 40*gamma*Pi^2*log(2) + 480*gamma^2*log(2)^2 - 80*Pi^2*log(2)^2 + 1280*gamma*log(2)^3 + 1280*log(2)^4 + 40*gamma*Zeta(3) + 160*log(2)*Zeta(3)) / log(n)^4), where gamma is the Euler-Mascheroni constant A001620.

A361364 Number of 5-dimensional cubic lattice walks that start and end at origin after 2n steps, not touching origin at intermediate stages.

Original entry on oeis.org

1, 10, 170, 6500, 332050, 19784060, 1296395700, 90616189800, 6637652225250, 503852804991500, 39337349077483420, 3142010167321271000, 255747325678297576100, 21150729618673827139000, 1773152567858996728205000, 150409554094012703302602000, 12890454660664800562838261250

Offset: 0

Shel Kaphan, Mar 09 2023

In Novak's note it is mentioned that if P(z) and Q(z) are the g.f.s for the probabilities of indecomposable and decomposable loops, respectively, that P(z) = 1 - 1/Q(z). This works equally well using loop counts rather than probabilities. The g.f.s may be expressed by the series constructed from the sequences of counts of loops of length 2*n. Q(z) for the 5-d case is the series corresponding to A287317.
To satisfy this g.f. equation, a(0) should be 0, but we give it as 1 since there is one trivial loop of 0 steps, and for consistency with related sequences.
To obtain the probability of returning to the point of origin for the first time after 2*n steps, divide a(n) by the total number of walks of length 2*n in d dimensions: (2*d)^(2*n) = 100^n.

Alois P. Heinz, Table of n, a(n) for n = 0..503
Jonathan Novak, Pólya's Random Walk Theorem.

Cf. A287317, A039699 (number of walks that return to the origin in 2n steps).
Number of walks that return to the origin for the first time in 2n steps, in 1..4 dimensions: |A002420|, A054474, A049037, A359801.
Column k=5 of A361397.
Cf. A169714.

walk5d[n_] :=
 Sum[(2 n)!/(i! j! k! l! (n - i - j - k - l)!)^2, {i, 0, n}, {j, 0,
   n - i}, {k, 0, n - i - j}, {l, 0, n - i - j - k}]; invertSeq[seq_] :=
 CoefficientList[1 - 1/SeriesData[x, 0, seq, 0, Length[seq], 1], x]; invertSeq[Table[walk5d[n], {n, 0, 15}]]

G.f.: 2 - 1/Integral_{t=0..oo} exp(-t)*BesselI(0,2*t*sqrt(x))^5 dt.

INVERTi transform of A169714.

A227997 Triangular array read by rows. T(n,k) is the number of square lattice walks that start and end at the origin after 2n steps having k primitive loops; n>=1, 1<=k<=n.

Original entry on oeis.org

4, 20, 16, 176, 160, 64, 1876, 1808, 960, 256, 22064, 22048, 13248, 5120, 1024, 275568, 282528, 182528, 83456, 25600, 4096, 3584064, 3747456, 2542464, 1284096, 481280, 122880, 16384, 47995476, 50981136, 35851968, 19365120, 8186880, 2617344, 573440, 65536, 657037232, 707110432, 511288256, 290053120, 133084160, 48799744, 13647872, 2621440, 262144, 9150655216, 9958458656, 7363711104, 4338317824, 2113592320, 851398656, 276856832, 68943872, 11796480, 1048576

Offset: 1

Geoffrey Critzer, Oct 04 2013

The walk consists of steps in the four directions NW,NE,SW,SE. A primitive loop is a walk that starts and ends at the origin but does not otherwise touch the origin.
Row sums are A002894.
Column 1 is A054474

			4,
20, 16,
176, 160, 64,
1876, 1808, 960, 256,
22064, 22048, 13248, 5120, 1024,
275568, 282528, 182528, 83456, 25600, 4096

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 90.

nn=6;a=Sum[Binomial[2n,n]^2x^n,{n,0,nn}];Map[Select[#,#>0&]&,Drop[CoefficientList[Series[1/(1-y(1-1/a)),{x,0,nn}],{x,y}],1]]//Grid

G.f.: 1/( 1 - y*(1 - 1/A(x)) ) where A(x) is the o.g.f. for A002894.

A378026 Number of simple lattice paths, steps (-1,0,0),(0,-1,0),(0,0,-1), of length 3n from (n,n,n) to the origin, never returning to the diagonal x = y = z before the origin.

Original entry on oeis.org

1, 6, 54, 816, 14814, 295812, 6262488, 137929392, 3125822238, 72383434332, 1704669773652, 40693683620448, 982302086191752, 23933136140685648, 587728374471479952, 14530886841268923264, 361374588105759096606, 9033515437023805672044, 226844689948433272890396, 5719461854507320708714464

Offset: 0

Markus Kuba, Nov 14 2024

Inversion of A006480 de Bruijn's S(3,n): (3n)!/(n!)^3.

Alois P. Heinz, Table of n, a(n) for n = 0..701
Markus Kuba and Alois Panholzer, Lattice paths and the diagonal of the cube, arXiv:2411.03930 [math.CO], 2024.

Cf. A006480, A054474, A000984.

b:= proc(n) option remember; (3*n)!/(n!)^3 end:
a:= proc(n) option remember;
      b(n)-add(a(n-i)*b(i), i=1..n-1)
    end:
seq(a(n), n=0..22);  # Alois P. Heinz, Nov 15 2024

nmax = 20; CoefficientList[Series[2 - 1/Hypergeometric2F1[1/3, 2/3, 1, 27*x], {x, 0, nmax}], x] (* Vaclav Kotesovec, Nov 15 2024 *)

G.f.: 2 - 1/P(z) where P(z) = 2F1(1/3,2/3;1;27z).

INVERTi transform of A006480.

More terms from Vaclav Kotesovec, Nov 15 2024

A068218 Triangle of numbers of square lattice walks that start and end at origin after 2k steps and contain exactly r steps to the east, not touching origin at intermediate stages.

Original entry on oeis.org

1, 2, 2, 2, 16, 2, 4, 84, 84, 4, 10, 400, 1056, 400, 10, 28, 1820, 9184, 9184, 1820, 28, 84, 8064, 66276, 126720, 66276, 8064, 84, 264, 35112, 426888, 1329768, 1329768, 426888, 35112, 264, 858, 151008, 2546544, 11737440, 19123776, 11737440

Offset: 0

Martin Wohlgemuth, Mar 24 2002

The given recurrences do not provide a means to calculate T(2r,r). But T(2r,r) is computable by the formula relating T(k,r) to A069466(k,r).

			T(3,1)=84 because there are 84 distinct lattice walks of length 2*3=6 starting and ending at the origin and containing exactly 1 step to the east and not touching origin at intermediate steps. Let E, W, S, N denote the 4 possible directions, then NNEWSS and NWSSNE are examples of such walks.

T(k, 0) = A002420(k) = A069466(k)/(2k-1).

Cf. A054474 (row sums).

A069466[k_, r_] := Binomial[2 k, k]*Binomial[k, r]^2; t[k_, r_] := t[k, r] = A069466[k, r] - Sum[Sum[t[i, j]*A069466[k - i, r - j], {j, 0, r}], {i, 1, k - 1}]; Table[t[k, r], {k, 0, 8}, {r, 0, k}] // Flatten (* Jean-François Alcover, Nov 21 2012, from formula *)

T(k, r) = 2*(2k-3)/(k-2r) * ( T(k-1, r) - T(k-1, r-1) ), for k > 2r. T(1, 0)=2, T(1, 1)=2 Sum[T(k, r), r=0, ..., k] = A054474(k) T(k, r)=A069466(k, r) - Sum[ Sum[ T(i, j)*A069466(k-i, r-j), j=0...r], i=1, k-1]

A366924 Number of 2n-step walks on square lattice starting and ending at the origin with first step north and avoiding early returns.

Original entry on oeis.org

1, 5, 44, 469, 5516, 68892, 896016, 11998869, 164259308, 2287663804, 32303714576, 461352451292, 6651528522256, 96669999247184, 1414652852290752, 20825721430968213, 308191001159544876, 4581880220433822108, 68398967956430765712, 1024826569020715088508, 15405900278361291658896

Offset: 1

Hugo Pfoertner, Dec 05 2023

Cf. A054474.

b:= proc(n) b(n):= binomial(2*n, n)^2 end:
a:= proc(n) option remember;
      b(n)/4-add(a(n-i)*b(i), i=1..n-1)
    end:
seq(a(n), n=1..21);  # Alois P. Heinz, Dec 05 2023

b[n_] := b[n] = Binomial[2*n, n]^2;
a[n_] := a[n] = b[n]/4 - Sum[a[n-i]*b[i], {i, 1, n-1}];
Table[a[n], {n, 1, 21}] (* Jean-François Alcover, Jan 28 2025, after Alois P. Heinz *)

a(n) = A054474(n)/4.

cp's OEIS Frontend

A098070 Consider a single king on an infinite chessboard. This sequence gives number of n-move paths when king starting at origin reaches the origin again for the first time at step n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A328127 G.f.: E(4*sqrt(x)) / K(4*sqrt(x)), where E(), K() are complete elliptic integrals.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A361364 Number of 5-dimensional cubic lattice walks that start and end at origin after 2n steps, not touching origin at intermediate stages.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A227997 Triangular array read by rows. T(n,k) is the number of square lattice walks that start and end at the origin after 2n steps having k primitive loops; n>=1, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Formula

A378026 Number of simple lattice paths, steps (-1,0,0),(0,-1,0),(0,0,-1), of length 3n from (n,n,n) to the origin, never returning to the diagonal x = y = z before the origin.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A068218 Triangle of numbers of square lattice walks that start and end at origin after 2k steps and contain exactly r steps to the east, not touching origin at intermediate stages.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A366924 Number of 2n-step walks on square lattice starting and ending at the origin with first step north and avoiding early returns.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Formula

A328127 G.f.: E(4sqrt(x)) / K(4sqrt(x)), where E(), K() are complete elliptic integrals.