|
| |
|
|
A095905
|
|
Sequence generated from Golomb's proof of de Bruijn's theorem on a torus considered as a matrix.
|
|
0
|
|
|
|
1, 21, 333, 5373, 86589, 1395549, 22491837, 362497437, 5842314621, 94159673181, 1517556760893, 24458225530653, 394189404655869, 6353089129389789, 102391746224652477, 1650231797698803357, 26596528397525794941
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Solomon W. Golomb's proof of de Bruijn's coloring theorem on a chessboard for 1 X 4 size pieces (that its impossible to color a 6 X 6 chessboard with pieces of size 1 X 4), is generalized for the torus by using M in a chessboard format. To quote Watkins, (p. 228): "However, Golomb was able to come up with a new coloring that, for example, shows that even on a torus you can't cover an m X n chessboard with 1 X 4 pieces unless 4 divides either m or n-that is, de Bruijn's theorem still holds, at least for 1 X 4 pieces." [p. 229]: And, "By the way, as de Bruijn himself originally proved, I should mention that de Bruijn's theorem holds in all higher dimensions; and so for example, an a X b X c solid block can be constructed out of 1 X 1 X k bricks only when k divides at least one of a,b, or c.".
|
|
|
REFERENCES
|
John J. Watkins, "Across the Board, the Mathematics of Chessboard Problems", Princeton University Press, 2004, p. 227-229.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(1) = 1, a(2) = 21, a(n+2) = 15*a(n+1) + 18*a(n), n>2. Matrix method: Let M = the 6 X 6 matrix [1 2 1 2 1 2 / 3 4 3 4 3 4 / 1 2 1 2 1 2 / 3 4 3 4 3 4 / 1 2 1 2 1 2 / 3 4 3 4 3 4]. Then M^n *[1 0 0 0 0 0] = [a(n) q a(n) q a(n) q a(n) q], where q = a term in another sequence with the same recursion rule.
G.f.: -x*(6*x+1) / (18*x^2+15*x-1). [Colin Barker, Dec 06 2012]
|
|
|
EXAMPLE
|
a(3) = 333 = 14*21 + 18
a(3) = 333 since M^3 * [1 0 0 0 0 0] = [333 729 333 729 333 729].
|
|
|
MATHEMATICA
|
a[n_] := (MatrixPower[{{1, 2, 1, 2, 1, 2}, {3, 4, 3, 4, 3, 4}, {1, 2, 1, 2, 1, 2}, {3, 4, 3, 4, 3, 4}, {1, 2, 1, 2, 1, 2}, {3, 4, 3, 4, 3, 4}}, n].{{1}, {0}, {0}, {0}, {0}, {0}})[[1, 1]]; Table[ a[n], {n, 17}] (* Robert G. Wilson v, Jun 16 2004 *)
LinearRecurrence[{15, 18}, {1, 21}, 30] (* Harvey P. Dale, Apr 07 2017 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
