|
|
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)}.
|
|
10
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
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
|
M. Bousquet-Mélou and M. Mishna, 2008. Walks with small steps in the quarter plane, ArXiv 0810.4387.
|
|
FORMULA
|
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)
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
|
|
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):
|
|
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)
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)
|
|
CROSSREFS
|
Cf. A368164 (nondeterministic Dyck bridges), A368234 (nondeterministic Dyck excursions).
|
|
KEYWORD
|
nonn,walk
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|