A220644 -id:A220644 - cp's OEIS frontend

A239264 Number A(n,k) of domicule tilings of a k X n grid; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 3, 0, 1, 1, 1, 5, 5, 1, 1, 1, 0, 11, 0, 11, 0, 1, 1, 1, 21, 43, 43, 21, 1, 1, 1, 0, 43, 0, 280, 0, 43, 0, 1, 1, 1, 85, 451, 1563, 1563, 451, 85, 1, 1, 1, 0, 171, 0, 9415, 0, 9415, 0, 171, 0, 1, 1, 1, 341, 4945, 55553, 162409, 162409, 55553, 4945, 341, 1, 1

Offset: 0

Alois P. Heinz, Mar 13 2014

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.

			A(3,2) = 5:
  +-----+ +-----+ +-----+ +-----+ +-----+
  |o o-o| |o o o| |o o o| |o o o| |o-o o|
  ||    | ||  X | || | || | X  || |    ||
  |o o-o| |o o o| |o o o| |o o o| |o-o o|
  +-----+ +-----+ +-----+ +-----+ +-----+
A(4,3) = 43:
  +-------+ +-------+ +-------+ +-------+ +-------+
  |o o o o| |o o o-o| |o o-o o| |o o-o o| |o o-o o|
  ||  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|
  +-------+ +-------+ +-------+ +-------+ +-------+ ...
Square array A(n,k) begins:
  1, 1,  1,   1,    1,      1,       1, ...
  1, 0,  1,   0,    1,      0,       1, ...
  1, 1,  3,   5,   11,     21,      43, ...
  1, 0,  5,   0,   43,      0,     451, ...
  1, 1, 11,  43,  280,   1563,    9415, ...
  1, 0, 21,   0, 1563,      0,  162409, ...
  1, 1, 43, 451, 9415, 162409, 3037561, ...

Alois P. Heinz, Antidiagonals n = 0..36, flattened

Columns (or rows) k=0-10 give: A000012, A059841, A001045(n+1), A239265, A239266, A239267, A239268, A239269, A239270, A239271, A239272.
Bisection of main diagonal gives: A239273.
Cf. A099390, A187616, A187617, A187596, A220644.

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;
         `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 `if`(irem(n*k, 2)>0, 0,
    `if`(k>n, A(k, n), b(n, [true$(k*2)]))):
seq(seq(A(n, d-n), n=0..d), d=0..14);

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[k1 && 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 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]]]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Feb 02 2015, after Alois P. Heinz *)

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

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

Original entry on oeis.org

1, 3, 40, 369, 3755, 37320, 373177, 3725843, 37213728, 371654153, 3711809483, 37070598992, 370232236753, 3697589375491, 36928628181272, 368814220524417, 3683427651446923, 36787191180049816, 367401660507886793, 3669320102980547411, 36646296045314442000

Offset: 0

R. H. Hardin, Dec 17 2012

Column 3 of A220644.

			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)
..0..6..4....0..0..0....6..4..0....8..9..0....8..9..0....8..0..0....6..4..0
..9..0..8....9..0..0....8..6..4....2..9..1....2..0..1....2..0..0....0..0..0
..0..1..2....0..1..0....2..6..4....0..0..1....6..4..0....0..6..4....6..4..0

Alois P. Heinz, Table of n, a(n) for n = 0..500 (terms n = 1..210 from R. H. Hardin)
Index entries for linear recurrences with constant coefficients, signature (8,22,-20,-16,10,-3).

gf:= -(x^4-3*x^3+6*x^2+5*x-1)/((x-1)*(3*x^5-7*x^4+9*x^3+29*x^2+7*x-1)):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 03 2014

LinearRecurrence[{8,22,-20,-16,10,-3},{3,40,369,3755,37320,373177},30] (* Harvey P. Dale, Nov 17 2013 *)

Empirical: a(n) = 8*a(n-1) +22*a(n-2) -20*a(n-3) -16*a(n-4) +10*a(n-5) -3*a(n-6).

G.f.: -(x^4-3*x^3+6*x^2+5*x-1)/((x-1)*(3*x^5-7*x^4+9*x^3+29*x^2+7*x-1)). - Alois P. Heinz, Jun 03 2014

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

Original entry on oeis.org

1, 5, 172, 3755, 92801, 2226936, 53841725, 1299348473, 31371388772, 757341382671, 18283618480037, 441397115736816, 10656083384666537, 257256013409077661, 6210599281867691164, 149934463555725516099, 3619673802389322978937, 87385102146053809399912

Offset: 0

R. H. Hardin, Dec 17 2012

nonn

Column 4 of A220644.

			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)
..9..9..0..0....0..0..0..8....8..6..4..0....6..4..8..0....8..0..0..7
..8..1..1..0....9..7..0..2....2..0..8..8....0..0..2..0....2..8..3..0
..2..6..4..0....3..1..6..4....6..4..2..2....6..4..6..4....0..2..0..0

Alois P. Heinz, Table of n, a(n) for n = 0..300 (terms n = 1..210 from R. H. Hardin)

gf:= -(3*x^7 -x^6 +14*x^5 -58*x^4 -70*x^3 +42*x^2 +15*x-1) / (15*x^9 -2*x^8 +48*x^7 -245*x^6 -460*x^5 +340*x^4 +325*x^3 -114*x^2 -20*x+1):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 03 2014

Empirical: a(n) = 20*a(n-1) +114*a(n-2) -325*a(n-3) -340*a(n-4) +460*a(n-5) +245*a(n-6) -48*a(n-7) +2*a(n-8) -15*a(n-9).

G.f.: -(3*x^7 -x^6 +14*x^5 -58*x^4 -70*x^3 +42*x^2 +15*x-1) / (15*x^9 -2*x^8 +48*x^7 -245*x^6 -460*x^5 +340*x^4 +325*x^3 -114*x^2 -20*x+1). - Alois P. Heinz, Jun 03 2014

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

Original entry on oeis.org

1, 8, 728, 37320, 2226936, 128171936, 7444342896, 431408410784, 25014514225856, 1450226501771584, 84080327982982848, 4874715696405194752, 282621433306639435392, 16385536749696632356608, 949984033027704106955264, 55077209132605857634211328

Offset: 0

R. H. Hardin, Dec 17 2012

nonn

Column 5 of A220644.

			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)
..0..6..4..9..0....6..4..0..0..7....0..9..0..6..4....0..7..6..4..0
..6..4..0..8..1....0..7..7..3..0....0..7..1..0..0....3..9..0..9..0
..0..0..0..2..0....3..3..0..0..0....3..0..0..6..4....0..0..1..0..1

Alois P. Heinz, Table of n, a(n) for n = 0..300 (terms n = 1..210 from R. H. Hardin)

gf:= -(4096*x^15 -4096*x^14 +31232*x^13 +42240*x^12 +242304*x^11 -32896*x^10 -801152*x^9 -74640*x^8 +473568*x^7 -18040*x^6 -86144*x^5 +11752*x^4 +3056*x^3 -350*x^2 -40*x+1) / (32768*x^17 -16384*x^16 +192512*x^15 +237568*x^14 +1681408*x^13 -640000*x^12 -7223680*x^11 -38400*x^10 +6932672*x^9 +175600*x^8 -2270720*x^7 +127448*x^6 +254384*x^5 -31552*x^4 -6232*x^3 +694*x^2 +48*x-1):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..25);  # Alois P. Heinz, Jun 03 2014

Empirical: a(n) = 48*a(n-1) +694*a(n-2) -6232*a(n-3) -31552*a(n-4) +254384*a(n-5) +127448*a(n-6) -2270720*a(n-7) +175600*a(n-8) +6932672*a(n-9) -38400*a(n-10) -7223680*a(n-11) -640000*a(n-12) +1681408*a(n-13) +237568*a(n-14) +192512*a(n-15) -16384*a(n-16) +32768*a(n-17).

G.f.: see Maple program. - Alois P. Heinz, Jun 03 2014

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

Original entry on oeis.org

1, 13, 3096, 373177, 53841725, 7444342896, 1040315976961, 145000880411157, 20223491612180232, 2820152941289640505, 393283923444213896309, 54844809649495130675968, 7648317475647716579501281, 1066586359952790876210231837, 148739462164292054050115639320

Offset: 0

R. H. Hardin, Dec 17 2012

nonn

Column 6 of A220644.

			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)
..0..7..8..6..4..8....0..7..7..0..0..8....0..9..6..4..7..0....0..0..7..9..0..0
..3..9..2..0..0..2....3..3..0..6..4..2....8..9..1..3..0..8....0..3..0..0..1..8
..0..0..1..0..0..0....6..4..0..6..4..0....2..0..1..0..0..2....0..0..0..0..0..2

Alois P. Heinz, Table of n, a(n) for n = 0..300 (terms n = 1..210 from R. H. Hardin)

gf:= -(42525*x^34 +364905*x^33 +4427406*x^32 -69988761*x^31 +75088869*x^30 +126251376*x^29 +1409947907*x^28 -3807220353*x^27 +31562787626*x^26 -34451027911*x^25 -29205077493*x^24 +161219121840*x^23 -514135270654*x^22 +487268729962*x^21 +681687943708*x^20 -1511580215802*x^19 +660828588610*x^18
+669167562768*x^17 -1110589682746*x^16 +414093064814*x^15 +401344851300*x^14 -357570201838*x^13 -8972200506*x^12 +82109485328*x^11 -17558268975*x^10 -5482245411*x^9 +2504769654*x^8 -169204765*x^7 -66910711*x^6 +13483712*x^5 -491961*x^4 -56477*x^3 +2642*x^2 +101*x -1) / (552825*x^36 +4701240*x^35 +56415798*x^34 -921279564*x^33 +976631280*x^32 +2578302306*x^31
+17639703466*x^30 -53576735032*x^29 +387967483426*x^28 -353889755932*x^27 -703880375232*x^26 +2343244613126*x^25 -6009171204129*x^24 +4558878158992*x^23 +11778527057052*x^22 -21799390094104*x^21 +5141934133696*x^20 +16202802907924*x^19 -18333779754964*x^18
+2990479177712*x^17 +10475377691972*x^16 -7214129736088*x^15 -1546010691232*x^14 +2687705043916*x^13 -328038015993*x^12 -356958898120*x^11 +106454109710*x^10 +10363446884*x^9 -8116096176*x^8 +821286442*x^7 +130975946*x^6 -30456760*x^5 +1178554*x^4 +91572*x^3 -4256*x^2 -114*x +1):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..20);  # Alois P. Heinz, Jun 03 2014

Empirical: a(n) = 114*a(n-1) +4256*a(n-2) -91572*a(n-3) -1178554*a(n-4) +30456760*a(n-5) -130975946*a(n-6) -821286442*a(n-7) +8116096176*a(n-8) -10363446884*a(n-9) -106454109710*a(n-10) +356958898120*a(n-11) +328038015993*a(n-12) -2687705043916*a(n-13) +1546010691232*a(n-14) +7214129736088*a(n-15) -10475377691972*a(n-16) -2990479177712*a(n-17) +18333779754964*a(n-18) -16202802907924*a(n-19) -5141934133696*a(n-20) +21799390094104*a(n-21) -11778527057052*a(n-22) -4558878158992*a(n-23) +6009171204129*a(n-24) -2343244613126*a(n-25) +703880375232*a(n-26) +353889755932*a(n-27) -387967483426*a(n-28) +53576735032*a(n-29) -17639703466*a(n-30) -2578302306*a(n-31) -976631280*a(n-32) +921279564*a(n-33) -56415798*a(n-34) -4701240*a(n-35) -552825*a(n-36).

G.f.: see Maple program. - Alois P. Heinz, Jun 03 2014

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

Original entry on oeis.org

1, 21, 13152, 3725843, 1299348473, 431408410784, 145000880411157, 48590896359378961, 16295162098717276928, 5463664833842177843423, 1832013557267266441097285, 614283122531442244792501056, 205972692517470174457341794041, 69063792561944299889152684046621

Offset: 0

R. H. Hardin, Dec 17 2012

nonn

			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)
..0..0..0..0..0..7..0....0..0..9..6..4..0..0....0..6..4..0..0..7..0
..6..4..7..9..3..8..0....6..4..9..1..0..7..0....6..4..8..9..3..6..4
..0..3..0..0..1..2..0....0..0..0..1..3..6..4....0..0..2..0..1..0..0

Alois P. Heinz, Table of n, a(n) for n = 0..200 (terms n = 1..135 from R. H. Hardin)

Column 7 of A220644.

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

Original entry on oeis.org

1, 34, 55888, 37213728, 31371388772, 25014514225856, 20223491612180232, 16295162098717276928, 13140746227808545282304, 10594819370472223969569120, 8542571199105608333942735840, 6887766005343647823407800357376, 5553534245505786602829188504607680

Offset: 0

Alois P. Heinz, Jun 03 2014

nonn

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

Column k=8 of A220644.

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

Original entry on oeis.org

1, 55, 237472, 371654153, 757341382671, 1450226501771584, 2820152941289640505, 5463664833842177843423, 10594819370472223969569120, 20540255065209806005525289313, 39823725482559144291828665014967, 77209746313875957204633819730760448

Offset: 0

Alois P. Heinz, Jun 03 2014

nonn

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

Column k=9 of A220644.

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

Original entry on oeis.org

1, 89, 1009056, 3711809483, 18283618480037, 84080327982982848, 393283923444213896309, 1832013557267266441097285, 8542571199105608333942735840, 39823725482559144291828665014967, 185661218973084382181156348510614065, 865553976307450198923428125167024054656

Offset: 0

Alois P. Heinz, Jun 03 2014

nonn

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

Column k=10 of A220644.

cp's OEIS Frontend

A239264 Number A(n,k) of domicule tilings of a k X n grid; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

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

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

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

Views