A063443 -id:A063443 - cp's OEIS frontend

A067963 Number of binary arrangements without adjacent 1's on n X n array connected e-w ne-sw nw-se.

2, 7, 77, 1152, 56549, 3837761, 806190208, 251170142257, 223733272186825, 319544298135448960, 1210302996752248488817, 7876274672755293629849313, 127662922218147601317696761088, 3758866349549535184419575245899295

Offset: 1

R. H. Hardin, Feb 02 2002

			Neighbors for n=4 (dots represent spaces):
. o--o--o--o
...\/ \/ \/
.../\ /\ /\
. o--o--o--o
...\/ \/ \/
.../\ /\ /\
. o--o--o--o
...\/ \/ \/
.../\ /\ /\
. o--o--o--o

R. H. Hardin and Vaclav Kotesovec, Table of n, a(n) for n = 1..30
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 69-71.

Cf. circle A000204, line A000045, arrays: ne-sw nw-se A067965, n-s nw-se A067964, e-w n-s nw-se A066864, e-w ne-sw n-s nw-se A063443, n-s A067966, e-w n-s A006506, nw-se A067962, toruses: bare A002416, ne-sw nw-se A067960, ne-sw n-s nw-se A067959, e-w ne-sw n-s nw-se A067958, n-s A067961, e-w n-s A027683, e-w ne-sw n-s A066866.

Diagonal of A228683

Terms a(15)-a(19) from Vaclav Kotesovec, May 01 2012

A067964 Number of binary arrangements without adjacent 1's on n X n array connected n-s nw-se.

Original entry on oeis.org

2, 8, 90, 1876, 103484, 11462588, 3118943536, 1808994829500, 2465526600093372, 7394315828592829424, 50975951518289853305508, 784977037926751747674903856, 27509351187362150581313065415008, 2167705218542258344490649896364635660, 387057670485382113845659790427906287869964

Offset: 1

R. H. Hardin, Feb 02 2002

			Neighbors for n=4 (dots represent spaces):
. o..o..o..o
. |\ |\ |\ |
. | \| \| \|
. o..o..o..o
. |\ |\ |\ |
. | \| \| \|
. o..o..o..o
. |\ |\ |\ |
. | \| \| \|
. o..o..o..o

Vaclav Kotesovec, Table of n, a(n) for n = 1..21
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 69-71.

Cf. circle A000204, line A000045, arrays: ne-sw nw-se A067965, e-w ne-sw nw-se A067963, e-w n-s nw-se A066864, e-w ne-sw n-s nw-se A063443, n-s A067966, e-w n-s A006506, nw-se A067962, toruses: bare A002416, ne-sw nw-se A067960, ne-sw n-s nw-se A067959, e-w ne-sw n-s nw-se A067958, n-s A067961, e-w n-s A027683, e-w ne-sw n-s A066866.

Limit n->infinity (a(n))^(1/n^2) = 1.503048082... (see A085850)

Terms a(14)-a(18) from Vaclav Kotesovec, May 01 2012

A201513 Number of ways to place n nonattacking kings on an n X n board.

Original entry on oeis.org

1, 1, 0, 8, 79, 1974, 62266, 2484382, 119138166, 6655170642, 423677826986, 30242576462856, 2390359529372724, 207127434998494421, 19516867860507198208, 1986288643031862123264, 217094567491104327256049, 25357029929230564723578520, 3151672341378566296926684684

Offset: 0

Vaclav Kotesovec, Dec 02 2011

Alois P. Heinz, Table of n, a(n) for n = 0..21 (terms n=1..20 from Andrew Woods)
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 77.

Cf. A061995, A061996, A061997, A061998, A172158, A194788, A201369.
Cf. A063443.
Main diagonal of A098487, A193580.

Asymptotics (Vaclav Kotesovec, Nov 29 2011): n^(2n)/n!*exp(-9/2).

a(0)=1 prepended by Alois P. Heinz, May 11 2017

A133791 Number of n X n binary matrices with every 1 adjacent to some 0 horizontally, vertically, diagonally or antidiagonally.

Original entry on oeis.org

1, 15, 417, 50625, 24879489, 48231228511, 373654052856545, 11546079143118274625, 1422756868491071266637985, 699232611373976058162941025423, 1370556061582419558173913152072112161, 10714096395475651010921722651799661109404545

Offset: 1

R. H. Hardin, Jan 05 2008

nonn

Number of dominating sets in the n X n king graph. - Andrew Howroyd, May 10 2017

Stephan Mertens, Table of n, a(n) for n = 1..22 (first 18 terms from Christian Sievers)
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, King Graph
Wikipedia, Dominating set

Main diagonal of A218663.

Cf. A133515, A133556, A063443 (independent vertex sets).

A218663 = Import["https://oeis.org/A218663/b218663.txt", "Table"][[All, 2]];
a[n_] := A218663[[2 n^2 - 2 n + 1]];
Table[a[n], {n, 1, 11}] (* Jean-François Alcover, Sep 23 2019 *)

a(12) and beyond from Christian Sievers, Dec 03 2023

A067959 Number of binary arrangements without adjacent 1's on n X n torus connected ne-sw n-s nw-se.

Original entry on oeis.org

1, 7, 22, 547, 9021, 812830, 70046159, 24082448515, 10363980496342, 14228018243052057, 29400555005986658803, 166705587265151114516638, 1606507128309318588452521527, 38505096862341023166325442747581, 1696028983502674228038462924646464012

Offset: 1

R. H. Hardin, Feb 02 2002

			Neighbors for n=4 (dots represent spaces):
.\|/\|/\|/\|/
. o..o..o..o
./|\/|\/|\/|\
.\|/\|/\|/\|/
. o..o..o..o
./|\/|\/|\/|\
.\|/\|/\|/\|/
. o..o..o..o
./|\/|\/|\/|\
.\|/\|/\|/\|/
. o..o..o..o
./|\/|\/|\/|\

Sean A. Irvine, Table of n, a(n) for n = 1..17
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 73.

Cf. circle A000204, line A000045, arrays: ne-sw nw-se A067965, e-w ne-sw nw-se A067963, n-s nw-se A067964, e-w n-s nw-se A066864, e-w ne-sw n-s nw-se A063443, n-s A067966, e-w n-s A006506, nw-se A067962, toruses: bare A002416, ne-sw nw-se A067960, e-w ne-sw n-s nw-se A067958, n-s A067961, e-w n-s A027683, e-w ne-sw n-s A066866.

a(13) from Vaclav Kotesovec, Aug 22 2016
a(14) from Vaclav Kotesovec, May 24 2021
a(15) from Sean A. Irvine, Jan 14 2024

A212269 Number of ways to place k non-attacking kings on an n X n cylindrical chessboard, summed over all k >= 0.

Original entry on oeis.org

2, 5, 19, 205, 3011, 92875, 4763459, 459630701, 78223965193, 24270274906085, 13497818986883771, 13571363009654254429, 24562890586806439035377, 80199120146273882569630015, 471874707649862024071657639861, 5005895207027974222377733802848093

Offset: 1

Vaclav Kotesovec, May 12 2012

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 343.

Vaclav Kotesovec, Table of n, a(n) for n = 1..27
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p.165

Cf. A063443 (n+1), A067958, A194650-A194654, A182407, A247413, A212269.

Limit n ->infinity (a(n))^(1/n^2) = 1.342643951124... (see A247413).

A220638 Number of ways to reciprocally link elements of an n X n array either to themselves or to exactly one king-move neighbor.

Original entry on oeis.org

1, 1, 10, 369, 92801, 128171936, 1040315976961, 48590896359378961, 13140746227808545282304, 20540255065209806005525289313, 185661218973084382181156348510614065, 9703072851259276652446200332793680010752000, 2932144456272256572796083896528773941130429279461761

Offset: 0

R. H. Hardin, Dec 17 2012

nonn

Main diagonal of A220644.
Row sums of A243424. - Alois P. Heinz, Jun 04 2014
Number of matchings (i.e., Hosoya index) in the n X n kings graph. - Andrew Howroyd, Apr 07 2016

			Some solutions for n=3 0=self 1=nw 2=n 3=ne 4=w 6=e 7=sw 8=s 9=se (reciprocal directions total 10)
..8..6..4....0..9..7....6..4..0....0..6..4....9..0..8....6..4..0....8..0..0
..2..7..0....9..3..1....8..6..4....6..4..7....0..1..2....0..0..8....2..6..4
..3..6..4....0..1..0....2..0..0....0..3..0....0..0..0....0..0..2....6..4..0

Alois P. Heinz, Table of n, a(n) for n = 0..16
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Matching

Cf. A239273 (perfect matchings), A063443 (independent vertex sets), A234622 (cycles).

b:= proc(n, l) option remember; local d, f, k;
      d:= nops(l)/2; f:=false;
      if n=0 then 1
    elif l[1..d]=[f$d] then b(n-1, [l[d+1..2*d][], true$d])
    else for k to d while not l[k] do od; b(n, subsop(k=f, l))+
         `if`(k1 and l[k+d+1],
                            b(n, subsop(k=f, k+d+1=f, l)), 0)+
         `if`(k>1 and n>1 and l[k+d-1],
                            b(n, subsop(k=f, k+d-1=f, l)), 0)+
         `if`(n>1 and l[k+d], b(n, subsop(k=f, k+d=f, l)), 0)+
         `if`(k b(n, [true$(n*2)]):
seq(a(n), n=0..10);  # Alois P. Heinz, Jun 03 2014

b[n_, l_] := b[n, l] = Module[{d, f, k}, d = Length[l]/2; f = False; Which[ n == 0, 1, l[[1 ;; d]] == Array[f&, d], b[n - 1, Join [l[[d+1 ;; 2d]], Array[True&, d]]], True, For[k = 1, !l[[k]], k++]; b[n, ReplacePart[l, k -> f]] + If[k < d && n > 1 && l[[k + d + 1]], b[n, ReplacePart[l, k | k + d + 1 -> f]], 0] + If[k > 1 && n > 1 && l[[k + d - 1]], b[n, ReplacePart[l, k | k + d - 1 -> f]], 0] + If[n > 1 && l[[k + d]], b[n, ReplacePart[l, k | k + d -> f]], 0] + If[k < d && l[[k + 1]], b[n, ReplacePart[l, k | k + 1 -> f]], 0]]]; a[n_] := b[n, Array[True&, 2n]]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 12}] (* Jean-François Alcover, Feb 01 2017, after Alois P. Heinz *)

a(10)-a(12) from Alois P. Heinz, Jun 03 2014

A211348 Number of ways to tile an n X n square with 1 X 1, 2 X 2 and 3 X 3 tiles.

Original entry on oeis.org

1, 1, 2, 6, 39, 467, 10290, 431842, 33702357, 4933399675, 1353257600290, 694985665826606, 668743276018647665, 1205268925168096642391, 4069023157203412697840109, 25732126785058509461002703360, 304814553338563601845965453449729

Offset: 0

Geoffrey H. Morley, Feb 05 2013

nonn

Cf. A045846, A063443.

b:= proc(n, l) option remember; local i, k, s, t;
      if max(l[])>n then 0 elif n=0 then 1
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
    else for k do if l[k]=0 then break fi od; s:=0;
         for i from k to min(k+2, nops(l)) while l[i]=0 do s:=s+
           b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)])
         od; s
      fi
    end:
a:= n-> b(n, [0$n]):
seq(a(n), n=0..10);  # Alois P. Heinz, Feb 05 2013

a(7)-a(16) from Alois P. Heinz, Feb 05 2013

A228267 Number T(n,k,r) of dissections of an n X k X r rectangular cuboid into integer-sided cubes including rotations and reflections; irregular triangle T(n,k,r), n >= k >= r >= 1 read by rows.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 3, 1, 5, 10, 1, 1, 5, 1, 11, 31, 1, 35, 167, 2098, 1, 1, 8, 1, 21, 76, 1, 93, 635, 15511, 1, 314, 3354, 185473, 4006722, 1, 1, 13, 1, 43, 210, 1, 269, 2887, 151378, 1, 1213, 22478, 3243515, 143662050, 1, 6427, 235150, 112411358

Offset: 1

Christopher Hunt Gribble, Aug 19 2013

The main diagonal T(n,n,n) is 1, 2, 10, 2098, 4006722, .... - R. J. Mathar and Rob Pratt, Nov 27 2017

			The irregular triangle begins:
.   r 1      2      3      4 ...
n,k
1,1   1
2,1   1
2,2   1      2
3,1   1
3,2   1      3
3,3   1      5     10
4,1   1
4,2   1      5
4,3   1     11     31
4,4   1     35    167   2098
5,1   1
5,2   1      8
5,3   1     21     76
5,4   1     93    635  15511
5,5   1    314   3354 185473 ...
...
T(3,2,2) = 3 because there are 3 distinct dissections of a 3 X 2 X 2 rectangular cuboid into integer-sided cubes. The dissections expanded into 2 dimensions are:
  ._____.    ._____.    ._____.
  |_|_|_|    |_|_|_|    |_|_|_|
  |_|_|_|    |_|_|_|    |_|_|_|
  ._____.    ._____.    ._____.
  |   |_|    |   |_|    |   |_|
  |___|_|    |___|_|    |___|_|
  ._____.    ._____.    ._____.
  |_|   |    |_|   |    |_|   |
  |_|___|    |_|___|    |_|___|

Christopher Hunt Gribble, C++ program

Cf. A219924.

T(1,1,r) = T(n,n,1) = 1. - R. J. Mathar, Dec 03 2017
T(2,2,r) = A000045(r+1). - R. J. Mathar, Dec 03 2017
T(3,3,r>=1) = 1, 5, 10, 31, ... with g.f. 1/(1-x-4*x^2-x^3). - R. J. Mathar, Dec 03 2017
T(4,4,r>=1) = 1, 35, 167, 2098, 15511, 151378, 1272179, 11574563, 100928230, 900224006, ... with TBD rational g.f. - R. J. Mathar, Dec 03 2017
T(n,n,2) = A063443(n). - R. J. Mathar, Dec 03 2017

20 more terms from R. J. Mathar, Dec 03 2017

A353777 Number of tilings of an n X n square using dominoes, monominoes and 2 X 2 tiles.

Original entry on oeis.org

1, 1, 8, 163, 15623, 5684228, 8459468955, 50280716999785, 1202536689448371122, 115462301811597894998929, 44537596159273736617786474211, 69003082378039459280864860681919942, 429429579883061866326542598342441907826951, 10734684843612889640707750537898705644071715970757

Offset: 0

Alois P. Heinz, May 07 2022

nonn

			a(2) = 8:
  .___.  .___.  .___.  .___.  .___.  .___.  .___.  .___.
  |   |  |_|_|  |___|  | | |  |_|_|  |___|  |_| |  | |_|
  |___|  |_|_|  |___|  |_|_|  |___|  |_|_|  |_|_|  |_|_| .

Alois P. Heinz, Table of n, a(n) for n = 0..17
Wikipedia, Polyomino

Main diagonal of A352589.

Cf. A004003, A028420, A063443, A219874, A219952, A219994, A220061, A220778, A233807, A270071.

a(n) = A352589(n,n).

cp's OEIS Frontend

A067963 Number of binary arrangements without adjacent 1's on n X n array connected e-w ne-sw nw-se.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A067964 Number of binary arrangements without adjacent 1's on n X n array connected n-s nw-se.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A201513 Number of ways to place n nonattacking kings on an n X n board.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A133791 Number of n X n binary matrices with every 1 adjacent to some 0 horizontally, vertically, diagonally or antidiagonally.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A067959 Number of binary arrangements without adjacent 1's on n X n torus connected ne-sw n-s nw-se.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A212269 Number of ways to place k non-attacking kings on an n X n cylindrical chessboard, summed over all k >= 0.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A220638 Number of ways to reciprocally link elements of an n X n array either to themselves or to exactly one king-move neighbor.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A211348 Number of ways to tile an n X n square with 1 X 1, 2 X 2 and 3 X 3 tiles.

Views

Author

Keywords

Crossrefs

Programs

Maple

Extensions

A228267 Number T(n,k,r) of dissections of an n X k X r rectangular cuboid into integer-sided cubes including rotations and reflections; irregular triangle T(n,k,r), n >= k >= r >= 1 read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs