A151281 - OEIS

%I #51 Aug 06 2024 04:46:54

%S 1,2,6,16,48,136,408,1184,3552,10432,31296,92544,277632,824448,

%T 2473344,7365120,22095360,65920000,197760000,590790656,1772371968,

%U 5299916800,15899750400,47578857472,142736572416,427357700096,1282073100288,3840133464064,11520400392192,34517383151616,103552149454848

%N 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)}.

%C From _Paul Barry_, Jan 26 2009: (Start)

%C Image of 2^n under A155761. Binomial transform is A129637. Hankel transform is 2^C(n+1,2).

%C 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)

%C 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

%H Robert Israel, <a href="/A151281/b151281.txt">Table of n, a(n) for n = 0..2000</a>

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Barry2/barry73.html">A Note on a One-Parameter Family of Catalan-Like Numbers</a>, JIS 12 (2009) 09.5.4

%H A. Bostan, <a href="https://citeseerx.ist.psu.edu/pdf/749aef4c6f3668e652b5074e5268346ccecc88c9">Computer Algebra for Lattice Path Combinatorics</a>, Seminaire de Combinatoire Ph. Flajolet, March 28 2013.

%H A. Bostan and M. Kauers, <a href="http://arxiv.org/abs/0811.2899">Automatic Classification of Restricted Lattice Walks</a>, arXiv:0811.2899 [math.CO], 2008-2009.

%H Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, <a href="https://arxiv.org/abs/2001.00393">Stieltjes moment sequences for pattern-avoiding permutations</a>, arXiv:2001.00393 [math.CO], 2020.

%H M. Bousquet-Mélou and M. Mishna, 2008. Walks with small steps in the quarter plane, <a href="http://arxiv.org/abs/0810.4387">ArXiv 0810.4387</a>.

%H Elie De Panafieu, Mohamed Lamine Lamali, and Michael Wallner, <a href="https://arxiv.org/abs/1812.06650">Combinatorics of nondeterministic walks of the Dyck and Motzkin type</a>, arXiv:1812.06650 [math.CO], 2018.

%H Élie de Panafieu and Michael Wallner, <a href="https://arxiv.org/abs/2311.03234">Combinatorics of nondeterministic walks</a>, arXiv:2311.03234 [math.CO], 2023.

%F From _Paul Barry_, Jan 26 2009: (Start)

%F 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).

%F 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)).

%F 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.

%F Reversion of x*(1 + 2*x)/(1 + 4*x + 6*x^2). (End)

%F From _Philippe Deléham_, Feb 01 2009: (Start)

%F a(n) = Sum_{k=0..n} A120730(n,k)*2^k.

%F a(2*n+2) = 3*a(2*n+1), a(2*n+1) = 3*a(2*n) - 2^n*A000108(n).

%F a(2*n+1) = 3*a(2*n) - A151374(n). (End)

%F (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

%F a(n) ~ 3^n/2. - _Vaclav Kotesovec_, Feb 13 2014

%p N:= 1000: # to get terms up to a(N)

%p S:= series((sqrt(1-8*x^2)+4*x-1)/(4*x*(1-3*x)),x,N+1):

%p seq(coeff(S,x,j),j=0..N); # _Robert Israel_, Feb 18 2013

%t 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}]

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

%o (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

%o (SageMath)

%o def a(n): # a = A151281

%o     if (n==0): return 1

%o     elif (n%2==1): return 3*a(n-1) - 2^((n-1)/2)*catalan_number((n-1)/2)

%o     else: return 3*a(n-1)

%o [a(n) for n in (0..40)] # _G. C. Greubel_, Nov 09 2022

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

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

%K nonn,walk

%O 0,2

%A _Manuel Kauers_, Nov 18 2008