A189145 Number of n X 2 array permutations with each element making zero or one knight moves.

1, 1, 4, 16, 36, 81, 225, 625, 1600, 4096, 10816, 28561, 74529, 194481, 509796, 1336336, 3496900, 9150625, 23961025, 62742241, 164249856, 429981696, 1125736704, 2947295521, 7716041281, 20200652641, 52886200900, 138458410000

Offset: 1

Author

R. H. Hardin, Apr 17 2011

Keywords

• nonn

Comments

Column 2 of A189150.

a(n+2) is number of ways to place k non-attacking knights on a 2 x n board, sum over all k>=0.

Examples

			All solutions for 3X2
..0..1....0..4....5..1....5..4
..2..3....2..3....2..3....2..3
..4..5....1..5....4..0....1..0
		

Links

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

Programs

Mathematica

Table[FullSimplify[LucasL[2n+4]/25 + (3*Fibonacci[n+1] + Fibonacci[n]) * (2*Cos[(Pi*n)/2] + Sin[(Pi*n)/2])*2/25 + 7*(-1)^n/50 + 1/10], {n,1,20}] (* Vaclav Kotesovec, Nov 07 2011 *)

Formula

Empirical: a(n) = 3*a(n-1) -3*a(n-2) +6*a(n-3) -6*a(n-5) +3*a(n-6) -3*a(n-7) +a(n-8).

Empirical: G.f. -x*(1-2*x+4*x^2+x^3+3*x^5+x^7-6*x^4-3*x^6) / ( (x-1)*(1+x)*(x^2-3*x+1)*(x^4+3*x^2+1) ). - R. J. Mathar, Oct 15 2011

Explicit formula: ((3+sqrt(5))/2)^(n+2)/25 + ((3-sqrt(5))/2)^(n+2)/25 + (((sqrt(5)+1)/2)^(n+2) + ((sqrt(5)-1)/2)^(n+2))*4*cos((Pi*n)/2)/25 + (((sqrt(5)+1)/2)^(n+2) - ((sqrt(5)-1)/2)^(n+2))*2*sin((Pi*n)/2)/25 + 1/10 + 7/50*(-1)^n. - Vaclav Kotesovec, Nov 07 2011