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,2

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.

Links

Table of n, a(n) for n=1..19.

Formula

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

Mathematica

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

Prog

(Magma) [2*(n+1)^n-Binomial(2*n, n): n in [0..20]]; // Vincenzo Librandi, Dec 03 2015
(PARI) a(n) = 2*(n+1)^n - binomial(2*n, n); \\ Altug Alkan, Dec 03 2015

Crossrefs

Cf. A007764.

Sequence in context: A184975 A268538 A319291 * A080446 A301411 A217803

Adjacent sequences: A265129 A265130 A265131 * A265133 A265134 A265135

Keyword

nonn,walk

Author

Theodore M. Mishura, Dec 02 2015

Status

approved