login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A193580 Triangle read by rows: T(n,k) = number of ways to place k nonattacking kings on an n X n board. 13
1, 1, 1, 1, 4, 1, 9, 16, 8, 1, 1, 16, 78, 140, 79, 1, 25, 228, 964, 1987, 1974, 978, 242, 27, 1, 1, 36, 520, 3920, 16834, 42368, 62266, 51504, 21792, 3600, 1, 49, 1020, 11860, 85275, 397014, 1220298, 2484382, 3324193, 2882737, 1601292, 569818, 129657, 18389, 1520, 64, 1 (list; graph; refs; listen; history; text; internal format)
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

Columns 2 to 10: A061995, A061996, A061997, A061998, A172158, A194788, A201369, A201771, A220467.

Diagonal: A201513.

Cf. A179403, etc., for extension to toroidal boards.

Cf. A166540, etc., for extension into three dimensions.

Cf. A098487 for a clipped version.

Row n sums to A063443(n+1).

Sequence in context: A158199 A091885 A069606 * A244761 A075150 A001254

Adjacent sequences:  A193577 A193578 A193579 * A193581 A193582 A193583

KEYWORD

nonn,tabf

AUTHOR

Andrew Woods, Aug 27 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 16 17:03 EST 2019. Contains 329201 sequences. (Running on oeis4.)