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

Author

Manuel Kauers, Nov 18 2008

Keywords

• nonn
• walk

Comments

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

Links

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

Crossrefs

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

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

Programs

Magma

[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

Maple

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

Mathematica

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

SageMath

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

Formula

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