OFFSET
0,5
COMMENTS
Rows 2n and 2n-1 both contain 1 + n^2 entries. Cf. A008794.
Row n sums to A063443(n+1).
Number of walks of length n-1 on a graph in which each node represents a 11-avoiding n-bit binary sequence B and adjacency of B and B' is determined by B'&(B|(B<<1)|(B>>1))=0 and the total number of nonzero bits in the walk is k.
Row n gives the coefficients of the independence polynomial of the n X n king graph. - Eric W. Weisstein, Jun 20 2017
REFERENCES
Norman Biggs, Algebraic Graph Theory, Cambridge University Press, New York, NY, second edition, 1993.
LINKS
Alois P. Heinz, Rows n = 0..21, flattened (Rows n = 0..20 from Andrew Woods)
R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares arXiv:1609.03964 [math.CO], 2016, Section 4.1.
J. Nilsson, On Counting the Number of Tilings of a Rectangle with Squares of Size 1 and 2, Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.2.
Eric Weisstein's World of Mathematics, Independence Polynomial
Eric Weisstein's World of Mathematics, King Graph
FORMULA
T(n, 0) = 1;
T(n, 1) = n^2;
T(2n-1, n^2-1) = n^3;
T(2n-1, n^2) = 1.
EXAMPLE
The table begins with T(0,0):
1;
1, 1;
1, 4;
1, 9, 16, 8, 1;
1, 16, 78, 140, 79;
...
T(4,3) = 140 because there are 140 ways to place 3 kings on a 4 X 4 chessboard so that no king threatens any other.
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Andrew Woods, Aug 27 2011
STATUS
approved