cp's OEIS Frontend

A193580 Triangle read by rows: T(n,k) = number of ways to place k nonattacking kings on an n X n board.

%I A193580 #65 May 29 2025 11:09:03
%S A193580 1,1,1,1,4,1,9,16,8,1,1,16,78,140,79,1,25,228,964,1987,1974,978,242,
%T A193580 27,1,1,36,520,3920,16834,42368,62266,51504,21792,3600,1,49,1020,
%U A193580 11860,85275,397014,1220298,2484382,3324193,2882737,1601292,569818,129657,18389,1520,64,1
%N A193580 Triangle read by rows: T(n,k) = number of ways to place k nonattacking kings on an n X n board.
%C A193580 Rows 2n and 2n-1 both contain 1 + n^2 entries. Cf. A008794.
%C A193580 Row n sums to A063443(n+1).
%C A193580 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.
%C A193580 Row n gives the coefficients of the independence polynomial of the n X n king graph. - _Eric W. Weisstein_, Jun 20 2017
%D A193580 Norman Biggs, Algebraic Graph Theory, Cambridge University Press, New York, NY, second edition, 1993.
%H A193580 Liang Kai, <a href="/A193580/b193580.txt">Rows n = 0..26, flattened</a> (Rows n = 0..20 from Andrew Woods, row n = 21 from Alois P. Heinz)
%H A193580 Kai Liang, <a href="https://arxiv.org/abs/2505.12776">Independent Set Enumeration in King Graphs by Tensor Network Contractions</a>, arXiv:2505.12776 [math.CO], 2025. See p. 1.
%H A193580 R. J. Mathar, <a href="http://arxiv.org/abs/1609.03964">Tiling n x m rectangles with 1 x 1 and s x s squares</a> arXiv:1609.03964 [math.CO], 2016, Section 4.1.
%H A193580 Johan Nilsson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Nilsson/nilsson15.html">On Counting the Number of Tilings of a Rectangle with Squares of Size 1 and 2</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.2.
%H A193580 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependencePolynomial.html">Independence Polynomial</a>
%H A193580 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KingGraph.html">King Graph</a>
%F A193580 T(n, 0) = 1;
%F A193580 T(n, 1) = n^2;
%F A193580 T(2n-1, n^2-1) = n^3;
%F A193580 T(2n-1, n^2) = 1.
%e A193580 The table begins with T(0,0):
%e A193580   1;
%e A193580   1,   1;
%e A193580   1,   4;
%e A193580   1,   9,  16,   8,   1;
%e A193580   1,  16,  78, 140,  79;
%e A193580   ...
%e A193580 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.
%Y A193580 Columns 2 to 10: A061995, A061996, A061997, A061998, A172158, A194788, A201369, A201771, A220467.
%Y A193580 Diagonal: A201513.
%Y A193580 Cf. A179403, etc., for extension to toroidal boards.
%Y A193580 Cf. A166540, etc., for extension into three dimensions.
%Y A193580 Cf. A098487 for a clipped version.
%Y A193580 Row n sums to A063443(n+1).
%K A193580 nonn,tabf
%O A193580 0,5
%A A193580 _Andrew Woods_, Aug 27 2011