%I #21 Sep 08 2022 08:46:14
%S 1,2,12,108,1180,15300,234374,4190872,86080572,1999951380,51874664446,
%T 1486016035944,46596167540806,1587429536107688,58385852010664650,
%U 2305843009058576432,97322383750732656572,4371823119475059457716,208254700595813407930382
%N Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid that move in 3 or fewer cardinal directions.
%C This sequence counts all joining paths that move in one of the following ways: UP and RIGHT only; UP, RIGHT, and LEFT only; UP, RIGHT, and DOWN only.
%F a(n) = 2*(n+1)^n - C(2*n,n).
%t Table[2 (n + 1)^n - Binomial[2 n, n], {n, 0, 18}] (* _Michael De Vlieger_, Dec 02 2015 *)
%o (Magma) [2*(n+1)^n-Binomial(2*n,n): n in [0..20]]; // _Vincenzo Librandi_, Dec 03 2015
%o (PARI) a(n) = 2*(n+1)^n - binomial(2*n,n); \\ _Altug Alkan_, Dec 03 2015
%Y Cf. A007764.
%K nonn,walk
%O 1,2
%A _Theodore M. Mishura_, Dec 02 2015