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

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.

Links

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

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

Example

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

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 *)

Crossrefs

Sequence in context: A207170 A207069 A207436 * A005722 A372635 A075408

Adjacent sequences: A189142 A189143 A189144 * A189146 A189147 A189148

Keyword

nonn

Author

R. H. Hardin, Apr 17 2011

Status

approved