OFFSET
0,2
COMMENTS
From Paul Barry, Jan 26 2009: (Start)
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.
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
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 *)
PROG
(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
(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
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Manuel Kauers, Nov 18 2008
STATUS
approved