|
| |
|
|
A086346
|
|
On a 3 X 3 board, the number of n-move paths for a chess king ending in a given corner square.
|
|
9
| |
|
|
1, 3, 18, 80, 400, 1904, 9248, 44544, 215296, 1039104, 5018112, 24227840, 116985856, 564850688, 2727354368, 13168803840, 63584665600, 307013812224, 1482394042368, 7157631156224
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| 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 corner square m (m = 1, 3, 7, 9). To determine the a(n) we can either sum the components of the column vector A^n[k,m], with A the adjacency matrix of the king's graph, or we can sum the components of the row vector A^n[m,k], see the Maple program.
Inverse binomial transform of A079291 (without the leading 0).
(End)
Contribution from R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Oct 12 2010: (Start)
The row n=3 of an array counting king walks on an n-by-n board with k steps, starting from a corner:
1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,
1,3,18,80,400,1904,9248,44544,215296,1039104,5018112,24227840,
1,3,18,105,615,3600,21075,123375,722250,4228125,24751875,144900000,
1,3,18,105,684,4359,28278,182349,1179792,7622667,49283802,318543921,
1,3,18,105,684,4550,30807,209867,1434279,9815190,67209723,460343730,
1,3,18,105,684,4550,31340,218056,1533712,10829360,76720288,544266448,
1,3,18,105,684,4550,31340,219555,1559835,11177190,80573373,583082082,
1,3,18,105,684,4550,31340,219555,1564080,11259785,81765550,597274600,
1,3,18,105,684,4550,31340,219555,1564080,11271876,82025163,601303692,
1,3,18,105,684,4550,31340,219555,1564080,11271876,82059768,602116173,
1,3,18,105,684,4550,31340,219555,1564080,11271876,82059768,602215614,
The partial sums along the rows are documented in A123109 (king walks with between 1 and k steps). (End)
|
|
|
REFERENCES
| Gary Chartrand, Introductory Graph Theory, pp. 217-221, 1984. [From Johannes W. Meijer (meijgia(AT)hotmail.com), Aug 01 2010]
|
|
|
LINKS
| Mike Oakes, KingMovesForPrimes.
Zak Seidov, KingMovesForPrimes.
Sleephound, KingMovesForPrimes.
Index to sequences with linear recurrences with constant coefficients, signature (2,12,8). [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Jul 22 2010]
|
|
|
FORMULA
| a(n)=(1/32)(2(-2)^(n+2)+(2+Sqrt[8])^(n+2)+(2-Sqrt[8])^(n+2))
a(n) = +2*a(n-1) +12*a(n-2) +8*a(n-3). G.f.: ( -1-x ) / ( (2*x+1)*(4*x^2+4*x-1) ). a(n) = A057087(n-1)/2+3*A057087(n)/4+(-2)^n/4. [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Jul 22 2010]
Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), Aug 01 2010: (Start)
GF(x) = (1+x)/(1-2*x-12*x^2-8*x^3)
a(n) = 2*a(n-1)+12*a(n-2)+8*a(n-3) with a(0)=1, a(1)=3 and a(2)=18.
Limit(a(n+k)/a(k), k=infinity) = A084128(n) + 2*A057087(n-1)*sqrt(2)
(End)
|
|
|
MAPLE
| Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), Aug 01 2010: (Start)
with(LinearAlgebra): nmax:=19; m:=1; 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);
(End)
|
|
|
MATHEMATICA
| Table[(1/32)(2(-2)^(n+2)+(2+Sqrt[8])^(n+2)+(2-Sqrt[8])^(n+2)), {n, 0, 19}]
|
|
|
CROSSREFS
| Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), Aug 01 2010: (Start)
Cf. A086347, A086348, A086349; Cf. A179596.
(End)
Sequence in context: A056319 A056310 A135371 * A036290 A078904 A099012
Adjacent sequences: A086343 A086344 A086345 * A086347 A086348 A086349
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Zak Seidov (zakseidov(AT)yahoo.com), Jul 17 2003
|
|
|
EXTENSIONS
| Offset changed and edited by Johannes W. Meijer (meijgia(AT)hotmail.com), Jul 15 2010
|
| |
|
|
