A265132 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.

1, 2, 12, 108, 1180, 15300, 234374, 4190872, 86080572, 1999951380, 51874664446, 1486016035944, 46596167540806, 1587429536107688, 58385852010664650, 2305843009058576432, 97322383750732656572, 4371823119475059457716, 208254700595813407930382

Offset: 1

Author

Theodore M. Mishura, Dec 02 2015

Keywords

• nonn
• walk

Comments

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.

Crossrefs

Cf. A007764.

Programs

Magma

[2*(n+1)^n-Binomial(2*n,n): n in [0..20]]; // Vincenzo Librandi, Dec 03 2015

Mathematica

Table[2 (n + 1)^n - Binomial[2 n, n], {n, 0, 18}] (* Michael De Vlieger, Dec 02 2015 *)

PARI

a(n) = 2*(n+1)^n - binomial(2*n,n); \\ Altug Alkan, Dec 03 2015

Formula

a(n) = 2*(n+1)^n - C(2*n,n).