A243424 -id:A243424 - cp's OEIS frontend

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

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

A239273 Number of domicule tilings of a 2n X 2n square grid.

Original entry on oeis.org

1, 3, 280, 3037561, 3263262629905, 326207195516663381931, 3011882198082438957330143630563, 2565014347691062208319404612723752103028288, 201442620359313683494245316355883565275531844406384955392, 1458834332808489549111708247664894524221330758005874053074138540424018259

Offset: 0

Alois P. Heinz, Mar 13 2014

nonn

A domicule is either a domino or it is formed by the union of two neighboring unit squares connected via their corners. In a tiling the connections of two domicules are allowed to cross each other.

Number of perfect matchings in the 2n X 2n kings graph. - Andrew Howroyd, Apr 07 2016

			a(1) = 3:
  +---+   +---+   +---+
  |o o|   |o o|   |o-o|
  || ||   | X |   |   |
  |o o|   |o o|   |o-o|
  +---+   +---+   +---+.
a(2) = 280:
  +-------+ +-------+ +-------+ +-------+ +-------+
  |o o o-o| |o o o-o| |o-o o-o| |o o o o| |o o-o o|
  | X     | | X     | |       | | X  | || | \   / |
  |o o o o| |o o o o| |o o o o| |o o o o| |o o o o|
  |   /  || |   / / | ||  X  || |       | ||     ||
  |o o o o| |o o o o| |o o o o| |o-o o o| |o o o o|
  ||    \ | ||     || |       | |     X | | / /   |
  |o o-o o| |o o-o o| |o-o o-o| |o-o o o| |o o o-o|
  +-------+ +-------+ +-------+ +-------+ +-------+ ...

Eric Weisstein's World of Mathematics, King Graph
Wikipedia, King's graph

Even bisection of main diagonal of A239264.

Cf. A004003, A243510, A243424, A220638.

b[n_, l_List] := b[n, l] = Module[{d = Length[l]/2, f = False, k}, Which[n == 0, 1, l[[1 ;; d]] == Array[f &, d], b[n - 1, Join[l[[d + 1 ;; 2*d]], Array[True &, d]]], True, For[k = 1, ! l[[k]], k++]; If[k < d && n > 1 && l[[k + d + 1]], b[n, ReplacePart[l, {k -> f, k + d + 1 -> f}]], 0] + If[k > 1 && n > 1 && l[[k + d - 1]], b[n, ReplacePart[l, {k -> f, k + d - 1 -> f}]], 0] + If[n > 1 && l[[k + d]], b[n, ReplacePart[l, {k -> f, k + d -> f}]], 0] + If[k < d && l[[k + 1]], b[n, ReplacePart[l, {k -> f, k + 1 -> f}]], 0]]];
A[n_, k_] := If[Mod[n*k, 2]>0, 0, If[k>n, A[k, n], b[n, Array[True&, k*2]]]];
a[n_] := A[2n, 2n];
Table[Print[n]; a[n], {n, 0, 7}] (* Jean-François Alcover, Sep 16 2019, after Alois P. Heinz in A239264 *)

a(n) = A239264(2n,2n).

a(8) from Alois P. Heinz, Sep 30 2014

a(9) from Alois P. Heinz, Nov 23 2018

A243510 Number of ways the maximal number of domicules can be placed on an n X n square.

Original entry on oeis.org

1, 1, 3, 58, 280, 170985, 3037561, 35203565096, 3263262629905, 580992839261272720, 326207195516663381931, 811740344447523575023878026, 3011882198082438957330143630563, 98662906581850761030365769529236858241, 2565014347691062208319404612723752103028288

Offset: 0

Alois P. Heinz, Jun 05 2014

nonn

Number of maximum matchings in the n X n king graph. - Eric W. Weisstein, Jun 20 2017

			a(2) = 3:
  +---+  +---+  +---+
  |o-o|  |o o|  |o o|
  |   |  || ||  | X |
  |o-o|  |o o|  |o o|
  +---+  +---+  +---+.
a(3) = 58:
  +-----+  +-----+  +-----+
  |o-o o|  |o o o|  |o o-o|
  |    ||  | X  ||  | \   |
  |o   o|  |o o o|  |o o o|
  ||    |  |     |  ||  / |
  |o o-o|  |o-o  |  |o o  |
  +-----+  +-----+  +-----+  ... .

Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set
Wikipedia, King's graph

Cf. A243511.

Even bisection gives A239273.

a(n) = A243424(n,floor(n^2/2)).

A243464 Number of ways 2 domicules can be placed on an n X n square.

Original entry on oeis.org

0, 0, 3, 110, 657, 2172, 5375, 11178, 20685, 35192, 56187, 85350, 124553, 175860, 241527, 324002, 425925, 550128, 699635, 877662, 1087617, 1333100, 1617903, 1946010, 2321597, 2749032, 3232875, 3777878, 4388985, 5071332, 5830247, 6671250, 7600053, 8622560

Offset: 0

Alois P. Heinz, Jun 05 2014

			a(2) = 3:
+---+  +---+  +---+
|o-o|  |o o|  |o o|
|   |  || ||  | X |
|o-o|  |o o|  |o o|
+---+  +---+  +---+.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=2 of A243424.

a:= n-> `if`(n=0, 0, (((8*n-24)*n-4)*n+63)*n-43):
seq(a(n), n=0..50);

G.f.: x^2*(43*x^3-137*x^2-95*x-3)/(x-1)^5.

a(n) = -43+63*n-4*n^2-24*n^3+8*n^4 for n>0, a(0) = 0.

A243465 Number of ways 3 domicules can be placed on an n X n square.

Original entry on oeis.org

0, 0, 0, 180, 4890, 36028, 154434, 488660, 1271450, 2883900, 5907298, 11182644, 19877850, 33562620, 54291010, 84691668, 128065754, 188492540, 270942690, 381399220, 526986138, 716104764, 958577730, 1265800660, 1650901530, 2128907708, 2716920674, 3434298420

Offset: 0

Alois P. Heinz, Jun 05 2014

			a(3) = 180:
+-----+  +-----+  +-----+  +-----+
|o-o  |  |  o  |  |  o  |  |  o  |
|     |  |   \ |  | /   |  | /   |
|o-o  |  |o o o|  |o o  |  |o o o|
|     |  || |  |  | /   |  |   X |
|  o-o|  |o o  |  |o o-o|  |  o o|
+-----+  +-----+  +-----+  +-----+  ... .

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=3 of A243424.

a:= n-> `if`(n<3, 0, ((((((32*n-144)*n-96)*n+1188)*n-854)
         *n-2328)*n+2574)/3):
seq(a(n), n=0..50);

G.f.: 2*x^3*(15*x^6-167*x^5+320*x^4+686*x^3-2789*x^2-1815*x-90)/(x-1)^7.

a(n) = (2574-2328*n-144*n^5-96*n^4+1188*n^3-854*n^2+32*n^6)/3 for n>=3, a(n) = 0 for n<3.

A243466 Number of ways 4 domicules can be placed on an n X n square.

Original entry on oeis.org

0, 0, 0, 58, 18343, 362643, 2911226, 14601844, 54738489, 168157793, 446728228, 1062085146, 2312934779, 4690690399, 8967633918, 16312226288, 28436620141, 47781858189, 77746670984, 122966217718, 189647543823, 285968959211, 422550971074, 613006835244

Offset: 0

Alois P. Heinz, Jun 05 2014

			a(3) = 58:
+-----+  +-----+  +-----+  +-----+
|o-o o|  |o o  |  |o-o o|  |o-o  |
|   / |  | \ \ |  |    ||  |     |
|o o  |  |o o o|  |o   o|  |o o o|
||    |  ||    |  ||    |  ||  X |
|o o-o|  |o o-o|  |o o-o|  |o o o|
+-----+  +-----+  +-----+  +-----+  ... .

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=4 of A243424.

a:= n-> `if`(n<4, [0$3, 58][n+1], ((((((((64*n-384)*n-448)*n
        +6480)*n-4984)*n-35304)*n+50017)*n+61647)*n-104802)/6):
seq(a(n), n=0..50);

G.f.: -x^3*(196*x^9 -1380*x^8 -1019*x^7 +21464*x^6 -32073*x^5 -77546*x^4 +302915*x^3 +199644*x^2 +17821*x +58) / (x-1)^9.

a(n) = (-104802 +61647*n +50017*n^2 -35304*n^3 -4984*n^4 +6480*n^5 -448*n^6 -384*n^7 +64*n^8)/6 for n>=4, a(3) = 58, a(n) = 0 for n<3.

A243467 Number of ways 5 domicules can be placed on an n X n square.

Original entry on oeis.org

0, 0, 0, 0, 33792, 2307376, 38049764, 316687056, 1756247962, 7430841848, 25895095920, 77947547416, 209206118486, 511919916960, 1160763672124, 2468985096704, 4973232330258, 9557709330856, 17631022607048, 31372223986440, 54066152166478, 90552261553040

Offset: 0

Alois P. Heinz, Jun 05 2014

			a(4) = 33792:
+-------+  +-------+
|o-o o  |  |  o   o|
|     \ |  | /    ||
|  o   o|  |o o o o|
|   \   |  |   X   |
|o   o o|  |  o o  |
||    / |  |       |
|o   o  |  |  o-o  |
+-------+  +-------+   ... .

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=5 of A243424.

a:= n-> `if`(n<5, [0$4, 33792][n+1],((((((((((128*n-960)*n-1600)*n
         +27360)*n-22560)*n-285192)*n+493090)*n+1279635)*n-2896628)
         *n-2069823)*n+5464830)/15):
seq(a(n), n=0..30);

G.f.: 2*x^4*(465*x^11 -2767*x^10 -1161*x^9 -3873*x^8 +262965*x^7 -1067787*x^6 +1243269*x^5 +2069157*x^4 -9734826*x^3 -7263594*x^2 -967832*x -16896) / (x-1)^11.

a(n) = (5464830 -2069823*n -2896628*n^2 +1279635*n^3 +493090*n^4 -285192*n^5 -22560*n^6 +27360*n^7 -1600*n^8 -960*n^9 +128*n^10)/15 for n>=5, a(4) = 33792, a(n) = 0 for n<=3.

A243511 Number of ways half the maximal number of domicules can be placed on an n X n square.

Original entry on oeis.org

1, 1, 6, 110, 18343, 9382388, 43019044258, 558605693874364, 66236678406528448449, 21324218858696872235790649, 63694548993039561351614359349824, 503614181552476916158019971522161589536, 37393123107750749849065997795023579513072683993, 7226766277015485498828489748946241590630740791829515424

Offset: 0

Alois P. Heinz, Jun 05 2014

nonn

			a(2) = 6:
+---+  +---+  +---+  +---+  +---+  +---+
|o-o|  |   |  |o  |  |  o|  |o  |  |  o|
|   |  |   |  ||  |  |  ||  | \ |  | / |
|   |  |o-o|  |o  |  |  o|  |  o|  |o  |
+---+  +---+  +---+  +---+  +---+  +---+.

Cf. A243510.

a(n) = A243424(n,floor(n^2/4)).

cp's OEIS Frontend

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

A239273 Number of domicule tilings of a 2n X 2n square grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A243510 Number of ways the maximal number of domicules can be placed on an n X n square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A243464 Number of ways 2 domicules can be placed on an n X n square.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A243465 Number of ways 3 domicules can be placed on an n X n square.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A243466 Number of ways 4 domicules can be placed on an n X n square.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A243467 Number of ways 5 domicules can be placed on an n X n square.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A243511 Number of ways half the maximal number of domicules can be placed on an n X n square.

Views

Author

Keywords

Examples

Crossrefs