login
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.
0

%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