A189604 Number of n X 3 array permutations with each element not moving, or moving one space E, S or NW.

1, 6, 20, 72, 256, 912, 3248, 11568, 41200, 146736, 522608, 1861296, 6629104, 23609904, 84087920, 299483568, 1066626544, 3798846768, 13529793392, 48187073712, 171620807920, 611236571184, 2176951329392, 7753327130544

Offset: 1

Author

R. H. Hardin, Apr 24 2011

Keywords

• nonn

Comments

Column 3 of A189610.

Binomial transform of A006131 starting (1, 5, 9, 29, 65, ...). - Gary W. Adamson, Feb 19 2014

Examples

			Some solutions for 4 X 3:
.
   4  5  1    0  5  1    0  1  2    0  1  2
   0  3  2    7  4  2    3  4  5    3  4  5
   6  7  8    3  6  8    6 11  8   10  7  8
   9 10 11    9 10 11    9  7 10    6  9 11
.
   4  0  1    0  1  2    4  1  2
   7  3  2    3  8  5    0  3  5
  10 11  5    6  4  7    6  7  8
   6  9  8    9 10 11    9 10 11
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..200

Crossrefs

Cf. A006131.

Programs

Mathematica

a[n_] := Sum[Sum[4^j Binomial[k-j+1, j], {j, 0, Quotient[k+1, 2]}]* Binomial[n-1, k], {k, 0, n-1}];
a /@ Range[1, 24] (* Jean-François Alcover, Sep 24 2019, after Gary W. Adamson *)

Formula

Empirical: a(n) = 3*a(n-1) + 2*a(n-2).

G.f.: (x+3*x^2)/(1-3*x-2*x^2). - Vladimir Kruchinin, May 13 2011