A086347 - OEIS

This site is supported by donations to The OEIS Foundation.

A086347

On a 3 X 3 board, number of n-move routes of chess king ending in a given side square.

1, 5, 24, 116, 560, 2704, 13056, 63040, 304384, 1469696, 7096320, 34264064, 165441536, 798822400, 3857055744, 18623512576, 89922273280, 434183143424, 2096421666816, 10122419240960 (list; graph; refs; listen; history; internal format)

	OFFSET	`0,2`
	COMMENTS	`Number of aa-avoiding words of length n on alphabet {a,b,c,d,e}. - Tanya Khovanova (tanyakh(AT)yahoo.com), Jan 11 2007` `Binomial transform of A164589 and second binomial transform of A096886. [From Al Hakanson (hawkuu(AT)gmail.com), Aug 17 2009]` `Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), Aug 01 2010: (Start)` `The a(n) represent the number of n-move paths of a chess king on a 3 X 3 board that end or start in a given side square m (m = 2, 4, 6, 8).` `Inverse binomial transform of A001109 (without the leading 0).` `(End)`
	LINKS	`Index entries for sequences related to linear recurrences with constant coefficients` `Joerg Arndt, Fxtbook` `Tanya Khovanova, Recursive Sequences` `Mike Oakes, KingMovesForPrimes.` `Zak Seidov, KingMovesForPrimes.` `Sleephound, KingMovesForPrimes.`
	FORMULA	`a(n) = (Sqrt[2]/32)((2+Sqrt[8])^(n+2)-(2-Sqrt[8])^(n+2))` `G.f.: (1+x)/(1-4x-4x^2). a(n) = A057087(n) + A057087(n-1). - R. Stephan, Feb 01 2004` `a(n) = 4a(n-1) + 4a(n-2). - Tanya Khovanova (tanyakh(AT)yahoo.com), Jan 11 2007` `Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), Aug 01 2010: (Start)` `Limit(a(n+k)/a(k),k=infinity) = A084128(n) + 2A057087(n-1)sqrt(2)` `(End)`
	EXAMPLE	`a(3) = 116 = 5^3 - 9 (aaa, aab, aac, aad, aae, baa, caa, daa, eaa). [From Al Hakanson (hawkuu(AT)gmail.com), Aug 17 2009]`
	MAPLE	`with(LinearAlgebra): nmax:=19; m:=2; A[5]:= [1, 1, 1, 1, 0, 1, 1, 1, 1]: A:=Matrix([[0, 1, 0, 1, 1, 0, 0, 0, 0], [1, 0, 1, 1, 1, 1, 0, 0, 0], [0, 1, 0, 0, 1, 1, 0, 0, 0], [1, 1, 0, 0, 1, 0, 1, 1, 0], A[5], [0, 1, 1, 0, 1, 0, 0, 1, 1], [0, 0, 0, 1, 1, 0, 0, 1, 0], [0, 0, 0, 1, 1, 1, 1, 0, 1], [0, 0, 0, 0, 1, 1, 0, 1, 0]]): for n from 0 to nmax do B(n):=A^n: a(n):= add(B(n)[m, k], k=1..9): od: seq(a(n), n=0..nmax); [From Johannes W. Meijer (meijgia(AT)hotmail.com), Aug 01 2010]`
	MATHEMATICA	`Table[(Sqrt[2]/32)((2+Sqrt[8])^(n+2)-(2-Sqrt[8])^(n+2)), {n, 0, 19}]`
	CROSSREFS	`Cf. A086346, A086348.` `Cf. A028859 a(n+2) = 2 a(n+1) + 2 a(n).` `Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), Aug 01 2010: (Start)` `Cf. A126473.` `(End)` `Sequence in context: A026388 A057969 A004254 * A200739 A026707 A110190` `Adjacent sequences: A086344 A086345 A086346 * A086348 A086349 A086350`
	KEYWORD	`nonn`
	AUTHOR	`Zak Seidov (zakseidov(AT)yahoo.com), Jul 17 2003`
	EXTENSIONS	`More terms from Tanya Khovanova (tanyakh(AT)yahoo.com), Jan 11 2007` `Offset changed and edited by Johannes W. Meijer (meijgia(AT)hotmail.com), Jul 15 2010`

Content is available under The OEIS End-User License Agreement .

Last modified February 16 12:15 EST 2012. Contains 205909 sequences.