login
Number of 3D n-step walks of type acc.
0

%I #24 Jan 28 2025 07:47:59

%S 1,2,7,24,98,400,1785,7980,37674,178164,874146,4294752,21667932,

%T 109436184,563910633,2908233900,15235550330,79870553620,424021948350,

%U 2252356700880,12088746573540,64913104882080,351594254659830,1905139854213960,10399223643879420,56783986550235000

%N Number of 3D n-step walks of type acc.

%C See Dershowitz (2017) for precise definition.

%H Nachum Dershowitz, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Dershowitz/dersh3.html">Touchard’s Drunkard</a>, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.

%F From _Mélika Tebni_, Dec 06 2024: (Start)

%F E.g.f.: (BesselI(0, 2*x) + BesselI(1, 2*x))^2*BesselI(1, 2*x) / x.

%F a(n) = Sum_{k=0..n} binomial(n, k)*A005558(k)*A001405(n-k).

%F a(2*n+1) = 2*A302182(2*n+1) = A135394(n) / (n+1).

%F For n > 0, a(A000918(n)) is odd. (End)

%p b:= n-> binomial(n, floor(n/2))*binomial(n+1, floor((n+1)/2)):

%p C:= n-> binomial(2*n, n)/(n+1):

%p a:= n-> add(binomial(n, 2*k)*C(k)*b(n-2*k), k=0..n/2):

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Dec 06 2024

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n<4, [1, 2, 7, 24][n+1],

%p (8*(14*n^4+85*n^3+190*n^2+188*n+63)*a(n-1)+4*(n-1)*

%p (80*n^4+418*n^3+676*n^2+269*n-108)*a(n-2)-96*(n-1)*(n-2)*

%p (10*n^2+31*n+27)*a(n-3)-144*(n-1)*(n-2)*(n-3)*(8*n^2+33*n+36)*

%p a(n-4))/((n+4)*(n+3)*(n+2)*(8*n^2+17*n+11)))

%p end:

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Dec 06 2024

%t b[n_] := Binomial[n, Floor[n/2]]*Binomial[n+1, Floor[(n+1)/2]];

%t c[n_] := Binomial[2*n, n]/(n+1);

%t a[n_] := Sum[Binomial[n, 2*k]*c[k]*b[n - 2*k], {k, 0, n/2}];

%t Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Jan 28 2025, after _Alois P. Heinz_ *)

%o (Python)

%o from math import comb as binomial

%o def C(n): return (binomial(2*n, n)//(n+1)) # Catalan numbers

%o def a(n):

%o return sum(binomial(n, k)*C((k+1)//2)*C(k//2)*(2*(k//2)+1)*binomial(n-k, (n-k)//2) for k in range(n+1))

%o print([a(n) for n in range(26)]) # _Mélika Tebni_, Dec 06 2024

%Y Cf. A000108, A000984, A002212, A002896, A005572, A026375, A064037, A081671, A138547, A145847, A145867, A150500, A202814.

%Y Cf. A000918, A001405, A005558, A005566, A135394, A302182.

%K nonn,walk

%O 0,2

%A _N. J. A. Sloane_, Apr 09 2018

%E a(13)-a(25) from _Mélika Tebni_, Dec 06 2024