A220638 -id:A220638 - cp's OEIS frontend

A140518 Number of simple paths from corner to corner of an n X n grid with king-moves allowed.

1, 5, 235, 96371, 447544629, 22132498074021, 10621309947362277575, 50819542770311581606906543, 2460791237088492025876789478191411, 1207644919895971862319430895789323709778193, 5996262208084349429209429097224046573095272337986011

Offset: 1

Don Knuth, Jul 26 2008

This graph is the "strong product" of P_n with P_n, where P_n is a path of length n. Sequence A007764 is what we get when we restrict ourselves to rook moves of unit length.

Computed using ZDDs (ZDD = "reduced, order, zero-suppressed binary decision diagram").

			For example, when n=8 this is the number of ways to move a king from a1 to h8 without occupying any cell twice.

Donald E. Knuth, The Art of Computer Programming, Vol. 4, fascicle 1, section 7.1.4, p. 117, Addison-Wesley, 2009.

Jens Weise, Evolutionary Many-Objective Optimisation for Pathfinding Problems, Ph. D. Dissertation, Otto von Guercke Univ., Magdeburg (Germany, 2022), see p. 53.

Main diagonal of A329118.
Cf. A140519, A158651, A234622, A007764, A038496.
Cf. A220638 (Hosoya index).

a(9)-a(11) from Andrew Howroyd, Apr 07 2016

A220644 T(n,k) = number of ways to reciprocally link elements of an n X k array either to themselves or to exactly one king-move neighbor.

Original entry on oeis.org

1, 2, 2, 3, 10, 3, 5, 40, 40, 5, 8, 172, 369, 172, 8, 13, 728, 3755, 3755, 728, 13, 21, 3096, 37320, 92801, 37320, 3096, 21, 34, 13152, 373177, 2226936, 2226936, 373177, 13152, 34, 55, 55888, 3725843, 53841725, 128171936, 53841725, 3725843, 55888, 55, 89

Offset: 1

R. H. Hardin, Dec 17 2012

Table starts
...1........2............3.................5.....................8
...2.......10...........40...............172...................728
...3.......40..........369..............3755.................37320
...5......172.........3755.............92801...............2226936
...8......728........37320...........2226936.............128171936
..13.....3096.......373177..........53841725............7444342896
..21....13152......3725843........1299348473..........431408410784
..34....55888.....37213728.......31371388772........25014514225856
..55...237472....371654153......757341382671......1450226501771584
..89..1009056...3711809483....18283618480037.....84080327982982848
.144..4287616..37070598992...441397115736816...4874715696405194752
.233.18218688.370232236753.10656083384666537.282621433306639435392

			Some solutions for n=3 k=4 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..8....6..4..0..0....8..0..0..0....9..6..4..8....6..4..0..0
..0..7..7..2....8..0..9..7....2..8..8..0....8..1..9..2....0..0..8..8
..3..3..6..4....2..0..3..1....0..2..2..0....2..6..4..1....0..0..2..2

Alois P. Heinz, Table of n, a(n) for n = 1..528 (antidiagonals 1..32) (terms n = 1..180 from R. H. Hardin)

Columns k=1-10 give: A000045(n+1), A052978, A220639, A220640, A220641, A220642, A220643, A243314, A243315, A243316.
Main diagonal is A220638.
Cf. A239264.

A243424 Triangle T(n,k) read by rows of number of ways k domicules can be placed on an n X n square (n >= 0, 0 <= k <= floor(n^2/2)).

Original entry on oeis.org

1, 1, 1, 6, 3, 1, 20, 110, 180, 58, 1, 42, 657, 4890, 18343, 33792, 27380, 7416, 280, 1, 72, 2172, 36028, 362643, 2307376, 9382388, 24121696, 37965171, 34431880, 16172160, 3219364, 170985, 1, 110, 5375, 154434, 2911226, 38049764, 355340561, 2408715568

Offset: 0

Alois P. Heinz, Jun 04 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.

The n-th row gives the coefficients of the matching-generating polynomial of the n X n king graph. - Eric W. Weisstein, Jun 20 2017

			T(2,1) = 6:
  +---+  +---+  +---+  +---+  +---+  +---+
  |o-o|  |   |  |o  |  |  o|  |o  |  |  o|
  |   |  |   |  ||  |  |  ||  | \ |  | / |
  |   |  |o-o|  |o  |  |  o|  |  o|  |o  |
  +---+  +---+  +---+  +---+  +---+  +---+
T(2,2) = 3:
  +---+  +---+  +---+
  |o-o|  |o o|  |o o|
  |   |  || ||  | X |
  |o-o|  |o o|  |o o|
  +---+  +---+  +---+
Triangle T(n,k) begins:
  1;
  1;
  1,  6,    3;
  1, 20,  110,   180,     58;
  1, 42,  657,  4890,  18343,   33792,   27380,     7416,      280;
  1, 72, 2172, 36028, 362643, 2307376, 9382388, 24121696, 37965171, ...
  ...

Alois P. Heinz, Rows n = 0..13, flattened
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial

Columns k=0-5 give: A000012, A002943(n-1) for n>0, A243464, A243465, A243466, A243467.
Row sums give A220638.
T(n,floor(n^2/2)) gives A243510.
T(n,floor(n^2/4)) gives A243511.
Cf. A242861 (the same for dominoes), A239264.

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;
         expand(b(n, subsop(k=f, l))+
         `if`(k1 and l[k+d+1],
                            x*b(n, subsop(k=f, k+d+1=f, l)), 0)+
         `if`(k>1 and n>1 and l[k+d-1],
                            x*b(n, subsop(k=f, k+d-1=f, l)), 0)+
         `if`(n>1 and l[k+d], x*b(n, subsop(k=f, k+d=f, l)), 0)+
         `if`(k (p-> seq(coeff(p,x,i), i=0..degree(p)))(b(n, [true$(n*2)])):
seq(T(n), n=0..7);

b[n_, l_] := b[n, l] = Module[{d, f, k}, d = Length[l]/2; f = False; Which[ n == 0, 1, l[[1 ;; d]] == Table[f, d], b[n-1, Join[l[[d+1 ;; 2d]], Table[ True, d]]], True, For[k = 1, !l[[k]], k++]; Expand[b[n, ReplacePart[l, k -> f]] + If[k1 && l[[k+d+1]], x*b[n, ReplacePart[l, {k -> f, k + d + 1 -> f}]], 0] + If[k>1 && n>1 && l[[k + d - 1]], x*b[n, ReplacePart[ l, {k -> f, k + d - 1 -> f}]], 0] + If[n>1 && l[[k + d]], x*b[n, ReplacePart[l, {k -> f, k+d -> f}]], 0] + If[k f, k+1 -> f}]], 0]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][
  b[n, Table[True, 2n]]];
Table[T[n], {n, 0, 7}] // Flatten (* Jean-François Alcover, Jun 09 2018, after Alois P. Heinz *)

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

cp's OEIS Frontend

A140518 Number of simple paths from corner to corner of an n X n grid with king-moves allowed.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A220644 T(n,k) = number of ways to reciprocally link elements of an n X k array either to themselves or to exactly one king-move neighbor.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A243424 Triangle T(n,k) read by rows of number of ways k domicules can be placed on an n X n square (n >= 0, 0 <= k <= floor(n^2/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions