keyword:walk - cp's OEIS frontend

A151281 Number of walks within N^2 (the first quadrant of Z^2) starting at (0,0) and consisting of n steps taken from {(-1, 0), (1, 0), (1, 1)}.

1, 2, 6, 16, 48, 136, 408, 1184, 3552, 10432, 31296, 92544, 277632, 824448, 2473344, 7365120, 22095360, 65920000, 197760000, 590790656, 1772371968, 5299916800, 15899750400, 47578857472, 142736572416, 427357700096, 1282073100288, 3840133464064, 11520400392192, 34517383151616, 103552149454848

Offset: 0

Manuel Kauers, Nov 18 2008

From Paul Barry, Jan 26 2009: (Start)
Image of 2^n under A155761. Binomial transform is A129637. Hankel transform is 2^C(n+1,2).
In general, the g.f. of the reversion of x*(1+c*x)/(1+a*x+b*x^2) is given by the continued fraction x/(1 -(a-c)*x -(b-a*c+c^2)*x^2/(1 -(a-2*c)*x -(b-a*c+c^2)*x^2/(1 -(a-2*c)*x -(b-a*c+c^2)*x^2/(1 - .... (End)
a(n) is the number of nondeterministic Dyck meanders of length n. See A368164 or the de Panafieu-Wallner article for the definiton of nondeterministc walks. A nondeterministic meander contains at least one classical meander, i.e., a walk never crossing the x-axis. - Michael Wallner, Dec 18 2023

Robert Israel, Table of n, a(n) for n = 0..2000
Paul Barry, A Note on a One-Parameter Family of Catalan-Like Numbers, JIS 12 (2009) 09.5.4
A. Bostan, Computer Algebra for Lattice Path Combinatorics, Seminaire de Combinatoire Ph. Flajolet, March 28 2013.
A. Bostan and M. Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2008-2009.
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.
M. Bousquet-Mélou and M. Mishna, 2008. Walks with small steps in the quarter plane, ArXiv 0810.4387.
Elie De Panafieu, Mohamed Lamine Lamali, and Michael Wallner, Combinatorics of nondeterministic walks of the Dyck and Motzkin type, arXiv:1812.06650 [math.CO], 2018.
Élie de Panafieu and Michael Wallner, Combinatorics of nondeterministic walks, arXiv:2311.03234 [math.CO], 2023.

Cf. A000108, A120730, A129637, A151374, A155761.

Cf. A368164 (nondeterministic Dyck bridges), A368234 (nondeterministic Dyck excursions).

[n le 3 select Factorial(n) else (3*n*Self(n-1) + 8*(n-3)*Self(n-2) - 24*(n-3)*Self(n-3))/n: n in [1..41]]; // G. C. Greubel, Nov 09 2022

N:= 1000: # to get terms up to a(N)
S:= series((sqrt(1-8*x^2)+4*x-1)/(4*x*(1-3*x)),x,N+1):
seq(coeff(S,x,j),j=0..N); # Robert Israel, Feb 18 2013

aux[i_, j_, n_] := Which[Min[i, j, n]<0 || Max[i, j]>n, 0, n==0, KroneckerDelta[i, j, n], True, aux[i, j, n]= aux[-1+i, -1+j, -1+n] +aux[-1+i, j, -1+n] +aux[1+i, j, -1+n]]; Table[Sum[aux[i,j,n], {i,0,n}, {j,0,n}], {n,0,25}]
a[n_]:= a[n]= If[n<3, (n+1)!, (3*(n+1)*a[n-1] +8*(n-2)*a[n-2] -24*(n-2)*a[n-3])/(n+1)]; Table[a[n], {n, 0, 30}] (* G. C. Greubel, Nov 09 2022 *)

def a(n): # a = A151281
    if (n==0): return 1
    elif (n%2==1): return 3*a(n-1) - 2^((n-1)/2)*catalan_number((n-1)/2)
    else: return 3*a(n-1)
[a(n) for n in (0..40)] # G. C. Greubel, Nov 09 2022

From Paul Barry, Jan 26 2009: (Start)
G.f.: 1/(1 -2*x -2*x^2/(1 -2*x^2/(1 -2*x^2/(1 -2*x^2/(1 -2*x^2/(1 - .... (continued fraction).
G.f.: c(2*x^2)/(1-2*x*c(2*x^2)) = (sqrt(1-8*x^2) + 4*x - 1)/(4*x*(1-3*x)).
a(n) = Sum_{k=0..n} ((k+1)/(n+k+1))*C(n, (n-k)/2)*(1 +(-1)^(n-k))*2^((n-k)/2)*2^k.
Reversion of x*(1 + 2*x)/(1 + 4*x + 6*x^2). (End)
From Philippe Deléham, Feb 01 2009: (Start)
a(n) = Sum_{k=0..n} A120730(n,k)*2^k.
a(2*n+2) = 3*a(2*n+1), a(2*n+1) = 3*a(2*n) - 2^n*A000108(n).
a(2*n+1) = 3*a(2*n) - A151374(n). (End)
(n+1)*a(n) = 3*(n+1)*a(n-1) + 8*(n-2)*a(n-2) - 24*(n-2)*a(n-3). - R. J. Mathar, Nov 26 2012
a(n) ~ 3^n/2. - Vaclav Kotesovec, Feb 13 2014

A192364 Number of lattice paths from (0,0) to (n,n) using steps (0,1),(0,2),(1,0),(2,0),(1,1).

Original entry on oeis.org

1, 3, 21, 157, 1239, 10047, 82951, 693603, 5854581, 49778997, 425712429, 3657968097, 31555053921, 273109567797, 2370474720369, 20625186298269, 179841473895447, 1571088267426447, 13747953837604959, 120482775658910763, 1057293764707074027, 9289536349244758791, 81709329486947791419

Offset: 0

Eric Werley, Jun 29 2011

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A091533.

FullSimplify[CoefficientList[Series[(3-6*x+Sqrt[-1+4*x*(9*x-11)+4*Sqrt[1-x]*Sqrt[5+4*x]*Sqrt[9*x-1]])/(Sqrt[10+8*x]*Sqrt[(1-x)*(1-9*x)]*(4*x*(9*x-11)-1+4*Sqrt[1-x]*Sqrt[5+4*x]*Sqrt[9*x-1])^(1/4)), {x, 0, 10}], x]]

/* same as in A092566 but use */
steps=[[0,1], [0,2], [1,0], [2,0], [1,1]];
/* Joerg Arndt, Jun 30 2011 */

From Vaclav Kotesovec, Oct 24 2012: (Start)
G.f.: (3 - 6*x + sqrt(-1 + 4*x*(9*x-11) + 4*sqrt(1-x)*sqrt(5+4*x)*sqrt(9*x-1))) / (sqrt(10+8*x)*sqrt((1-x)*(1-9*x))*(4*x*(9*x-11)-1+4*sqrt(1-x)*sqrt(5+4*x)*sqrt(9*x-1))^(1/4))
D-finite with recurrence: 15*(n-1)*n*a(n) = (n-1)*(133*n-54)*a(n-1) + (31*n^2 - 177*n + 224)*a(n-2) - (113*n^2 - 295*n + 144)*a(n-3) - 18*(n-3)*(2*n-5)*a(n-4)
a(n) ~ 3^(2*n+3/2)/(2*sqrt(14*Pi*n))
(End)
a(n) = A091533(2*n,n) for n >= 0. - Paul D. Hanna, Dec 11 2018
a(n) = [x^n*y^n] 1/(1 - x - y - x^2 - x*y - y^2) for n >= 0. - Paul D. Hanna, Dec 11 2018

Terms > 425712429 by Joerg Arndt, Jun 30 2011

A229644 Cogrowth function of the group Baumslag-Solitar(2,2).

Original entry on oeis.org

1, 4, 28, 244, 2396, 25324, 281140, 3232352, 38151196, 459594316, 5628197948, 69859456440, 876985904276, 11115789165888, 142066687799680, 1828884017527504, 23694360858872604, 308714491495346028, 4042605442981407388, 53178663502737007352

Offset: 0

Murray Elder, Sep 27 2013

a(n) is the number of words of length 2n in the letters a,a^{-1},t,t^{-1} that equal the identity of the group BS(2,2)=.

			For n=1 there are 4 words of length 2 equal to the identity: aa^{-1}, a^{-1}a, tt^{-1}, t^{-1}t.

Murray Elder, Table of n, a(n) for n = 0..50
M. Elder, A. Rechnitzer, E. J. Janse van Rensburg, T. Wong, The cogrowth series for BS(N,N) is D-finite
Wikipedia, Baumslag-Solitar group
Index entries for sequences related to groups

The cogrowth sequences for BS(N,N) for N = 1..10 are A002894, A229644, A229645, A229646, A229647, A229648, A229649, A229650, A229651, A229652.

A229645 Cogrowth function of the group Baumslag-Solitar(3,3).

Original entry on oeis.org

1, 4, 28, 232, 2108, 20364, 205696, 2149956, 23087260, 253400200, 2831688428, 32121034928, 368996930720, 4284878088040, 50221403053556, 593400572917032, 7061298334083484, 84555438345880932, 1018170456984477856, 12321676227943830972

Offset: 0

Murray Elder, Sep 27 2013

a(n) is the number of words of length 2n in the letters a,a^{-1},t,t^{-1} that equal the identity of the group BS(3,3)=.

			For n=1 there are 4 words of length 2 equal to the identity: aa^{-1}, a^{-1}a, tt^{-1}, t^{-1}t.

Murray Elder, Table of n, a(n) for n = 0..49
M. Elder, A. Rechnitzer, E. J. Janse van Rensburg, T. Wong, The cogrowth series for BS(N,N) is D-finite
Index entries for sequences related to groups

The cogrowth sequences for BS(N,N) for N = 1..10 are A002894, A229644, A229645, A229646, A229647, A229648, A229649, A229650, A229651, A229652.

A229646 Cogrowth function of the group Baumslag-Solitar(4,4).

Original entry on oeis.org

1, 4, 28, 232, 2092, 19884, 196096, 1988424, 20611116, 217526524, 2330681348, 25296553088, 277653104800, 3077568629256, 34410056828392, 387725845018512, 4399241841920428, 50228061806093020, 576729989899675348

Offset: 0

Murray Elder, Sep 27 2013

a(n) is the number of words of length 2n in the letters a,a^{-1},t,t^{-1} that equal the identity of the group BS(4,4)=.

			For n=1 there are 4 words of length 2 equal to the identity: aa^{-1}, a^{-1}a, tt^{-1}, t^{-1}t.

Murray Elder, Table of n, a(n) for n = 0..50
M. Elder, A. Rechnitzer, E. J. Janse van Rensburg, T. Wong, The cogrowth series for BS(N,N) is D-finite
Index entries for sequences related to groups

The cogrowth sequences for BS(N,N) for N = 1..10 are A002894, A229644, A229645, A229646, A229647, A229648, A229649, A229650, A229651, A229652.

A229647 Cogrowth function of the group Baumslag-Solitar(5,5).

Original entry on oeis.org

1, 4, 28, 232, 2092, 19864, 195376, 1971932, 20303084, 212400232, 2251379688, 24129199208, 261067326544, 2848016992032, 31295785633532, 346126420439512, 3850363854970476, 43057199315715676, 483795646775017312, 5459770924922887392

Offset: 0

Murray Elder, Sep 27 2013

a(n) is the number of words of length 2n in the letters a,a^{-1},t,t^{-1} that equal the identity of the group BS(5,5)=.

			For n=1 there are 4 words of length 2 equal to the identity: aa^{-1}, a^{-1}a, tt^{-1}, t^{-1}t.

Murray Elder, Table of n, a(n) for n = 0..50
M. Elder, A. Rechnitzer, E. J. Janse van Rensburg, T. Wong, The cogrowth series for BS(N,N) is D-finite
Index entries for sequences related to groups

The cogrowth sequences for BS(N,N) for N = 1..10 are A002894, A229644, A229645, A229646, A229647, A229648, A229649, A229650, A229651, A229652.

A229648 Cogrowth function of the group Baumslag-Solitar(6,6).

Original entry on oeis.org

1, 4, 28, 232, 2092, 19864, 195352, 1970924, 20277036, 211864264, 2241723728, 23969620844, 258583473640, 2811005437348, 30762114003572, 338624821158892, 3747021722921964, 41656518905688504, 465062224305678280, 5211973807553021868

Offset: 0

Murray Elder, Sep 27 2013

a(n) is the number of words of length 2n in the letters a,a^{-1},t,t^{-1} that equal the identity of the group BS(6,6)=.

			For n=1 there are 4 words of length 2 equal to the identity: aa^{-1}, a^{-1}a, tt^{-1}, t^{-1}t.

Murray Elder, Table of n, a(n) for n = 0..50
M. Elder, A. Rechnitzer, E. J. Janse van Rensburg, T. Wong, The cogrowth series for BS(N,N) is D-finite
Index entries for sequences related to groups

The cogrowth sequences for BS(N,N) for N = 1..10 are A002894, A229644, A229645, A229646, A229647, A229648, A229649, A229650, A229651, A229652.

A229649 Cogrowth function of the group Baumslag-Solitar(7,7).

Original entry on oeis.org

1, 4, 28, 232, 2092, 19864, 195352, 1970896, 20275692, 211825564, 2240852928, 23952708696, 258285519688, 2806105225928, 30685515254240, 337472968923532, 3730218568024236, 41417273400310152, 461722437389957236, 5166105817092273412

Offset: 0

Murray Elder, Sep 27 2013

a(n) is the number of words of length 2n in the letters a,a^{-1},t,t^{-1} that equal the identity of the group BS(7,7)=.

			For n=1 there are 4 words of length 2 equal to the identity: aa^{-1}, a^{-1}a, tt^{-1}, t^{-1}t.

Murray Elder, Table of n, a(n) for n = 0..50
M. Elder, A. Rechnitzer, E. J. Janse van Rensburg, T. Wong, The cogrowth series for BS(N,N) is D-finite
Index entries for sequences related to groups

The cogrowth sequences for BS(N,N) for N = 1..10 are A002894, A229644, A229645, A229646, A229647, A229648, A229649, A229650, A229651, A229652.

A229650 Cogrowth function of the group Baumslag-Solitar(8,8).

Original entry on oeis.org

1, 4, 28, 232, 2092, 19864, 195352, 1970896, 20275660, 211823836, 2240798048, 23951367224, 258257552968, 2805581350056, 30676425237024, 337324008602512, 3727882769574860, 41381900166952348, 461201577710442388, 5158610797198820800

Offset: 0

Murray Elder, Sep 27 2013

a(n) is the number of words of length 2n in the letters a,a^{-1},t,t^{-1} that equal the identity of the group BS(8,8)=.

			For n=1 there are 4 words of length 2 equal to the identity: aa^{-1}, a^{-1}a, tt^{-1}, t^{-1}t.

Murray Elder, Table of n, a(n) for n = 0..50
M. Elder, A. Rechnitzer, E. J. Janse van Rensburg, T. Wong, The cogrowth series for BS(N,N) is D-finite
Index entries for sequences related to groups

The cogrowth sequences for BS(N,N) for N = 1..10 are A002894, A229644, A229645, A229646, A229647, A229648, A229649, A229650, A229651, A229652.

A229651 Cogrowth function of the group Baumslag-Solitar(9,9).

Original entry on oeis.org

1, 4, 28, 232, 2092, 19864, 195352, 1970896, 20275660, 211823800, 2240795888, 23951292204, 258255572584, 2805537209648, 30675548482880, 337307986673572, 3727607821613388, 41377406950962504, 461130952671387592, 5157535231753964268

Offset: 0

Murray Elder, Sep 28 2013

a(n) is the number of words of length 2n in the letters a,a^{-1},t,t^{-1} that equal the identity of the group BS(9,9)=.

			For n=1 there are 4 words of length 2 equal to the identity: aa^{-1}, a^{-1}a, tt^{-1}, t^{-1}t.

Murray Elder, Table of n, a(n) for n = 0..49
M. Elder, A. Rechnitzer, E. J. Janse van Rensburg, T. Wong, The cogrowth series for BS(N,N) is D-finite
Index entries for sequences related to groups

The cogrowth sequences for BS(N,N) for N = 1..10 are A002894, A229644, A229645, A229646, A229647, A229648, A229649, A229650, A229651, A229652.

cp's OEIS Frontend

A151281 Number of walks within N^2 (the first quadrant of Z^2) starting at (0,0) and consisting of n steps taken from {(-1, 0), (1, 0), (1, 1)}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A192364 Number of lattice paths from (0,0) to (n,n) using steps (0,1),(0,2),(1,0),(2,0),(1,1).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A229644 Cogrowth function of the group Baumslag-Solitar(2,2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A229645 Cogrowth function of the group Baumslag-Solitar(3,3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A229646 Cogrowth function of the group Baumslag-Solitar(4,4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A229647 Cogrowth function of the group Baumslag-Solitar(5,5).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A229648 Cogrowth function of the group Baumslag-Solitar(6,6).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A229649 Cogrowth function of the group Baumslag-Solitar(7,7).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A229650 Cogrowth function of the group Baumslag-Solitar(8,8).

Views

Author

Keywords

Comments

Examples

Links