OFFSET
0,3
COMMENTS
From Natalia L. Skirrow, May 30 2026: (Start)
In the formula "Sum_{i,j=0..floor(n/2), i+j>=n/2} ...", i counts move-pairs on the horizontal axis while j counts vertical move-pairs.
The C(n,n-2*i,n-2*j) = n! / ((n-2*i)! * (n-2*j)! * (2*(i+j)-n)!) puts the n-2*i moves with no horizontal part and n-2*j with no vertical part on distinct turns, and A000108(i) * A000108(j) counts the directions (Dyck paths in the x and y axis).
a(p) is divisible by p if p is an odd prime; the horizontal and vertical parts' timings can be cyclically shifted while leaving the paths (in this example, ++-- on the x axis, +-+- on the y) invariant to form equivalence classes of p each.
(+,+),(+, ),(-,-),(-,+),( ,-)
( ,+),(+,-),(+, ),(-,+),(-,-)
(+,+),( ,-),(+,+),(-, ),(-,-)
(+,+),(+,-),( ,+),(-,-),(-, )
(+, ),(+,+),(-,-),( ,+),(-,-)
(End)
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008-2009.
Natalia L. Skirrow, chessboards.
FORMULA
G.f.: (1-2*t)*Integral(hypergeom([1/2, 1/2], [2], 16*t*(t+1)/(1+4*t)^2)/(1-2*t)^2, t)/t^2 - 1/t. - Mark van Hoeij, Oct 31 2012
D-finite with (n+1)*(n+2)^2*(3*n-1)*a(n) = (n-1)*(n+1)*(9*n*(n+1)+4)*a(n-1) + 4*(n-1)*(3*n-2)*(9*n^2+5*n-1)*a(n-2) + 32*n*(n-1)*(n-2)*(3*n+2)*a(n-3). - Alois P. Heinz, Oct 31 2012
From Natalia L. Skirrow, May 30 2026: (Start)
a(n) = 4*Integral_{u,v=0..1} (sin(Pi*u)*sin(Pi*v))^2 * ((1+2*cos(Pi*u))*(1+2*cos(Pi*v))-1)^n du dv.
a(n) = Sum_{i,j=0..floor(n/2), i+j>=n/2} C(n,n-2*i,n-2*j) * A000108(i) * A000108(j), where C(n,k,j-k) = C(n,j)*C(j,k) is a trinomial coefficient.
G.f.: Integral_{t=0..1} sin(Pi*t)^2*( 1+x*(1-u)-sqrt((1+x-3*x*u)*(1+x+x*u)) )/(x*u)^2 dt, where u=1+2*cos(Pi*t).
a(n) ~ 2^(3*n+7)/(27*Pi*n^3) * (1 - 5/n + 307/(18*n^2) - 12020/(243*n^3) + ...).
a(n) = Sum_{k=0..n} (-1)^(n-k) * C(n,k) * A001006(k)^2.
That is, this sequence is A133053's inverse binomial transform.
(End)
MAPLE
b:= proc(n, l) option remember; `if`(min(l[])<0 or n<max(l[]), 0,
`if`(n=0, 1, add(b(n-1, l-d), d=[[-1, -1], [-1, 0], [-1, 1],
[0, -1], [0, 1], [1, -1], [1, 0], [1, 1]])))
end:
a:= n-> b(n, [0$2]):
seq(a(n), n=0..30); # Alois P. Heinz, Jul 22 2012
# Alternative:
a:= proc(n) option remember; `if`(n<4, [1, 0, 3, 6][n+1],
((9*n^2+9*n+4) *a(n-1)
+ ((3*n-2)*(9*n^2+5*n-1) *a(n-2)
+ 8*n*(n-2)*(3*n+2) *a(n-3))*4/(n+1)
)*(n-1)/ ((3*n-1)*(n+2)^2))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Oct 31 2012
MATHEMATICA
aux[i_Integer, j_Integer, n_Integer] := 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, 1 + j, -1 + n] + aux[i, -1 + j, -1 + n] + aux[i, 1 + j, -1 + n] + aux[1 + i, -1 + j, -1 + n] + aux[1 + i, j, -1 + n] + aux[1 + i, 1 + j, -1 + n]]; Table[aux[0, 0, n], {n, 0, 25}]
(* Alternative: *)
RecurrenceTable[{(n+1)*(n+2)^2*(3*n-1)*a[n] == (n-1)*(n+1)*(9*n*(n+1)+4)*a[n-1] + 4*(n-1)*(3*n-2)*(9*n^2+5*n-1)*a[n-2] + 32*n*(n-1)*(n-2)*(3*n+2)*a[n-3], a[0]==1, a[1]==0, a[2]==3}, a, {n, 0, 25}] (* Vaclav Kotesovec, Jun 02 2026, after _Alois Heinz_ *)
PROG
(Python)
a = lru_cache(None)(lambda n: (1, 0, 3)[n] if n < 3 else (n-1)*( (9*n*(n+1)+4)*a(n-1) + 4*( (3*n-2)*(9*n**2+5*n-1)*a(n-2) + 8*n*(n-2)*(3*n+2)*a(n-3) )//(n+1) )//(n+2)**2//(3*n-1))
# Natalia L. Skirrow, May 30 2026; after Alois P. Heinz
CROSSREFS
KEYWORD
nonn,easy,changed
AUTHOR
Manuel Kauers, Feb 01 2010
STATUS
approved