A004003 -id:A004003 - cp's OEIS frontend

A216675 Number of ways one can draw arrows between adjacent nodes of an n X n grid such that each node has one outgoing and one incoming arrow.

0, 4, 0, 1296, 0, 45265984, 0, 168709341081856, 0, 66865709036047973991424, 0, 2815414274858422422282241600000000, 0, 12589335654221209921194197564847684000000000000, 0, 5977481098898922857923760209743284068237948337696882106105856, 0

Offset: 1

M. F. Hasler, Sep 13 2012

nonn

"Adjacent" is meant in the sense of von Neumann neighborhoods (4 neighbors for "interior" nodes, 3 resp. 2 for nodes on the borders resp. in the corners).
Alternate definition: Number of permutations of an n X n array with each element moving exactly one step horizontally or vertically. (Suggested by R. H. Hardin.)
From Adam P. Goucher, Aug 01 2013: (Start)
Also the permanent of the adjacency matrix of the n X n grid graph, which is the determinant of the modified adjacency matrix where vertical and horizontal edges have weights of 1 and i, respectively.
Also the square of the number of domino tilings of an n X n chessboard.
(End)

			For a 1 X 1 grid, there is no such possibility.
For a 2 X 2 grid, on can draw arrows between 2 pairs of nodes in horizontal or vertical sense, and the clockwise and counterclockwise cyclic "permutation" of the 4 nodes.
For a 3 X 3 grid, there is no possibility, neither for a 5 X 5 grid.

Alois P. Heinz, Table of n, a(n) for n = 1..50 (terms n = 1..30 from Adam P. Goucher)
Project Euler, Problem 393: Migrating ants.

See A216678 for the same problem with an additional constraint ("no 2-loops").

Cf. A216796-A216800 for more general n X k grids.

Table[If[Mod[n,2]==0,Det[MapIndexed[(#1 I^Mod[Total[#2],2])&, Normal[AdjacencyMatrix[GridGraph[{n,n}]]],{2}]],0],{n,1,20}] (* Adam P. Goucher, Aug 01 2013 *)

from sympy.abc import x
from sympy import resultant, chebyshevu, I
def A216675(n): return 0 if n&1 else resultant(chebyshevu(n,x/2),chebyshevu(n,I*x/2)) # Chai Wah Wu, Nov 07 2023

a(2n) = A004003(n)^2; a(2n + 1) = 0. - Adam P. Goucher, Aug 01 2013

Terms beyond a(5) from R. H. Hardin, Sep 15 2012

Terms beyond a(8) from Adam P. Goucher, Aug 01 2013

A304790 The maximal number of different domino tilings allowed by the Ferrers-Young diagram of a single partition of 2n.

Original entry on oeis.org

1, 1, 2, 3, 5, 8, 13, 21, 36, 55, 95, 149, 281, 430, 781, 1211, 2245, 3456, 6728, 10092, 18061, 31529, 51378, 85659, 167089, 252748, 431819, 817991, 1292697

Offset: 0

Alois P. Heinz, May 18 2018

nonn

			a(11) = 149 different domino tilings are possible for 444442 and 6655.
a(18) = 6728 different domino tilings are possible for 666666.

Eric Weisstein's World of Mathematics, Ferrers Diagram
Wikipedia, Domino
Wikipedia, Domino tiling
Wikipedia, Ferrers diagram
Wikipedia, Mutilated chessboard problem
Wikipedia, Partition (number theory)
Wikipedia, Young tableau, Diagrams
Index entries for sequences related to dominoes

Cf. A000045, A001105, A004003, A304789.

h:= proc(l, f) option remember; local k; if min(l[])>0 then
     `if`(nops(f)=0, 1, h(map(u-> u-1, l[1..f[1]]), subsop(1=[][], f)))
    else for k from nops(l) while l[k]>0 by -1 do od;
        `if`(nops(f)>0 and f[1]>=k, h(subsop(k=2, l), f), 0)+
        `if`(k>1 and l[k-1]=0, h(subsop(k=1, k-1=1, l), f), 0)
      fi
    end:
g:= l-> `if`(add(`if`(l[i]::odd, (-1)^i, 0), i=1..nops(l))=0,
        `if`(l=[], 1, h([0$l[1]], subsop(1=[][], l))), 0):
b:= (n, i, l)-> `if`(n=0 or i=1, g([l[], 1$n]), max(b(n, i-1, l),
                   b(n-i, min(n-i, i), [l[], i]))):
a:= n-> b(2*n$2, []):
seq(a(n), n=0..15);

h[l_, f_] := h[l, f] = Module[{k}, If[Min[l] > 0, If[Length[f] == 0, 1, h[Map[# - 1&, l[[1 ;; f[[1]]]]], ReplacePart[f, 1 -> Nothing]]], For[k = Length[l], l[[k]] > 0 , k--]; If[Length[f] > 0 && f[[1]] >= k, h[ReplacePart[l, k -> 2], f], 0] + If[k > 1 && l[[k - 1]] == 0, h[ReplacePart[l, {k -> 1, k - 1 -> 1}], f], 0]]];
g[l_] := If[Sum[If[OddQ@l[[i]], (-1)^i, 0], {i, 1, Length[l]}] == 0, If[l == {}, 1, h[Table[0, {l[[1]]}], ReplacePart[l, 1 -> Nothing]]], 0];
b[n_, i_, l_] := If[n == 0 || i == 1, g[Join[l, Table[1, {n}]]], Max[b[n, i - 1, l], b[n - i, Min[n - i, i], Append[l, i]]]];
a[n_] := b[2n, 2n, {}];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Aug 24 2021, after Alois P. Heinz *)

a(n) = max { k : A304789(n,k) > 0 }.
a(A001105(n)) = A004003(n).
a(n) = A000045(n+1) for n < 8.

A334124 a(n) = 2^n * sqrt(Resultant(U_{2n}(x/2), T_{2n}(i*x/2))), where T_n(x) is a Chebyshev polynomial of the first kind, U_n(x) is a Chebyshev polynomial of the second kind and i = sqrt(-1).

Original entry on oeis.org

1, 3, 71, 17753, 46069729, 1234496016491, 341133743251787719, 971684488369988888850993, 28523907708086181923163934073729, 8628515016553040037389969912341438652243, 26895841132028233579514694272575933932911355677831

Offset: 0

Seiichi Manyama, Apr 15 2020

nonn

Wikipedia, Chebyshev polynomials
Wikipedia, Resultant

Main diagonal of A103997.

Cf. A004003, A334088.

Table[2^n * Sqrt[Resultant[ChebyshevU[2*n, x/2], ChebyshevT[2*n, I*x/2], x]], {n, 0, 12}] (* Vaclav Kotesovec, Apr 16 2020 *)

{a(n) = sqrtint(4^n*polresultant(polchebyshev(2*n, 2, x/2), polchebyshev(2*n, 1, I*x/2)))}

from math import isqrt
from sympy import resultant, chebyshevt, chebyshevu, I
from sympy.abc import x
def A334124(n): return isqrt(resultant(chebyshevu(n<<1,x/2),chebyshevt(n<<1,I*x/2))*(1<<(n<<1))) if n else 1 # Chai Wah Wu, Nov 07 2023

a(n) = A103997(n,n).

a(n) ~ 2^(1/4) * exp(2*G*n*(2*n+1)/Pi) / (1 + sqrt(2))^n, where G is Catalan's constant A006752. - Vaclav Kotesovec, Apr 16 2020, updated Jan 03 2021

A340396 a(n) = 2^(n^2 - 1) * Product_{j=1..n, k=1..n} (1 + sin(Pij/n)^2 + sin(Pik/n)^2).

Original entry on oeis.org

0, 1, 96, 93789, 1244160000, 241885578271872, 700566272328037500000, 30323548995402141685610526683, 19627362048402730985830806120284160000, 189995156103157091521654945902925881881155376920, 27506190205802587152768139358989866456457087869970721213256

Offset: 0

Vaclav Kotesovec, Jan 06 2021

nonn

Cf. A004003, A007726, A065072, A067518, A127605, A340052, A340165, A340182, A340183, A340293.

Table[2^(n^2 - 1) * Product[1 + Sin[Pi*j/n]^2 + Sin[Pi*k/n]^2, {j, 1, n}, {k, 1, n}], {n, 0, 10}] // Round

a(n) = 2^(n^2-1) * Product_{j=1..n, k=1..n} (3 - cos(Pi*j/n)^2 - cos(Pi*k/n)^2).
a(n) = 2^(n^2-1) * Product_{j=1..n, k=1..n} (2-cos(2*Pi*j/n)/2-cos(2*Pi*k/n)/2).
a(n) ~ 2^(n^2-1) * exp(4*c*n^2/Pi^2), where c = Integral_{x=0..Pi/2, y=0..Pi/2} log(1 + sin(x)^2 + sin(y)^2) dy dx = -Pi^2*(log(2) + log(sqrt(2)-1)/2) + Pi * Integral_{x=0..Pi/2} log(1 + sqrt(1 + 1/(1 + sin(x)^2))) dx = A340421 = 1.627008991085721315763766677017604437985734719035793082916212355323520649...

A353934 Number of tilings of an n X n square using right trominoes, dominoes, and monominoes.

Original entry on oeis.org

1, 1, 11, 369, 83374, 90916452, 546063639624, 17259079054003609, 2916019543694306398589, 2620143594924539083433405392, 12541344781693990981151732534871036, 319608708168951734031266758322647453517098, 43373075269161087186367095378869660507262626652634

Offset: 0

Alois P. Heinz, May 11 2022

nonn

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

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

Main diagonal of A353877.

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

a(n) = A353877(n,n).

A360804 Number of ways to tile an n X n square using rectangles with distinct areas.

Original entry on oeis.org

1, 1, 21, 253, 2401, 36237, 815929, 18713197

Offset: 1

Scott R. Shannon, Feb 21 2023

All possible tilings are counted, including those identical by symmetry. Note that distinct areas means that, for example, only one of the two rectangles with area 4, a 2 X 2 or 1 X 4 rectangle, can be used in any tiling.

			a(1) = 1 as the only way to tile a 1 X 1 square is with a square with dimensions 1 X 1.
a(2) = 1 as the only way to tile a 2 X 2 square is with a square with dimensions 2 X 2.
a(3) = 21. The possible tilings are the same as those given in the examples of A360499(3).
a(4) = 253. And example tiling of the 4 X 4 square is:
.
  +---+---+---+---+
  |   |       |   |
  +---+---+---+   +
  |           |   |
  +           +   +
  |           |   |
  +---+---+---+---+
  |               |
  +---+---+---+---+
.
which contains rectangles with areas 1, 2, 3, 4, 6. The one tiling, excluding symmetrically equivalent arrangements, that is excluded here but allowed in A360499 is:
.
  +---+---+---+---+
  |       |       |
  +       +       +
  |       |       |
  +---+---+       +
  |       |       |
  +---+---+---+---+
  |               |
  +---+---+---+---+
.
as this contains two rectangles with area 4. This can occur in 16 different ways so a(4) = A360499(4) - 16 = 269 - 16 = 253.

Cf. A360499, A360498, A360725, A360256, A360773, A182275, A004003.

A260032 Number of perfect matchings in graph P_{2n} X P_{2n} with a monomer on each corner.

Original entry on oeis.org

1, 8, 784, 913952, 12119367744, 1773206059548800, 2808001509386950713600, 47534638766423741578738188800, 8530835766072904609739799813424153600, 16137081911409285302469685272022812457875802112, 320397648203287990193211938297925486964232264783587250176

Offset: 1

N. J. A. Sloane, Jul 19 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..40
N. Allegra, Exact solution of the 2d dimer model: Corner free energy, correlation functions and combinatorics, arXiv:1410.4131 [cond-mat.stat-mech], 2014, p.21.
Wikipedia, FKT algorithm
Wikipedia, Matching (graph theory)

Cf. A099390, A004003.

with(LinearAlgebra):
a:= proc(n) option remember; local d, i, j, t, m, M;
      d:= 2*n; m:= d^2-4;
      M:= Matrix(m, shape=skewsymmetric);
      for i to d-3 do M[i+1, i]:=1 od;
      for i to d-2 do M[i, i+d-1]:=1 od;
      for i from m-d+3 to m-1 do M[i, i+1]:=1 od;
      for i from m-d+3 to m do M[i-d+1, i]:=1 od;
      for i from d-1 to m-2*d+2 do M[i, i+d]:=1 od;
      for i to d-2 do for j to d-1 do
        t:=d*i+j-2; M[t, t+1]:= `if`(irem(i, 2)=1, 1, -1);
      od od;
      isqrt(Determinant(M))
    end:
seq(a(n), n=1..11);  # Alois P. Heinz, Mar 10 2016

a[1] = 1; a[n_] := a[n] = Module[{d, i, j, t, m, M}, d = 2*n; m = d^2 - 4; M = Array[0&, {m, m}];
   For[i = 1, i <= d - 3, i++, M[[i + 1, i]] = 1];
   For[i = 1, i <= d - 2, i++, M[[i, i + d - 1]] = 1];
   For[i = m - d + 3, i <= m - 1, i++, M[[i, i + 1]] = 1];
   For[i = m - d + 3, i <= m, i++, M[[i - d + 1, i]] = 1];
   For[i = d - 1, i <= m - 2*d + 2, i++, M[[i, i + d]] = 1];
   For[i = 1, i <= d - 2, i++,
    For[j = 1, j <= d - 1, j++, t = d*i + j - 2; M[[t, t + 1]] = If[Mod[i, 2] == 1, 1, -1]]]; M = M - Transpose[M]; Sqrt[Det[M]]];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 11}] (* Jean-François Alcover, Nov 11 2017, after Alois P. Heinz *)

a(6)-a(10) from Andrew Howroyd, Nov 15 2015

Typo in a(5) corrected and a(11) added by Alois P. Heinz, Mar 07 2016

A263425 Number of tilings of an 2n X 2n square using tetrominoes of any shape.

Original entry on oeis.org

1, 1, 117, 178939, 19077209438, 72713560548906621, 13664822582333502156627512

Offset: 0

Alois P. Heinz, Oct 17 2015

S. Butler, J. Ekstrand, S. Osborne, TETRIS Tiling, AMS Spring Central Sectional, Iowa State University, April 27-28 2013
R. S. Harris, Counting Polyomino Tilings
Wikipedia, Tetromino

Bisection (even part) of main diagonal of A230031.

Cf. A004003.

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

a(6) (using terms from A230031) from Alois P. Heinz, Mar 26 2025

A340535 Number of domino tilings (or dimer coverings) of the 2n X n grid.

Original entry on oeis.org

1, 1, 5, 41, 2245, 185921, 106912793, 90124167441, 540061286536921, 4652799879944138561, 289415868852204573601981, 25545661075321867247577262777, 16457725663617130715785831809325501, 14905470663149838513993965664256435411841, 99323759360556656337166635121447749135517599089

Offset: 0

Alois P. Heinz, Jan 10 2021

nonn

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

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

Cf. A004003, A099390, A187596, A187616.

b:= proc(m, n) option remember; local i, j, t, M;
       M:= Matrix(n*m, shape=skewsymmetric);
       for i to n do for j to m do t:= (i-1)*m+j;
          if j b(2*n, n):
seq(a(n), n=0..15);

T[?OddQ, ?OddQ] = 0;
T[m_, n_] := Product[2(2+Cos[2 j Pi/(m+1)]+Cos[2 k Pi/(n+1)]), {k, 1, n/2}, {j, 1, m/2}];
a[n_] := T[2n, n] // Round;
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, May 27 2022 *)

a(n) = A187596(2n,n) = A187596(n,2n) = A187616(2n,n).

a(n) = A099390(2n,n) = A099390(n,2n) for n >= 1.

A360943 Number of ways to tile an n X n square using rectangles with distinct dimensions where no rectangle has an edge length that divides n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 360, 0, 360, 360, 8547192, 0

Offset: 1

Scott R. Shannon, Mar 01 2023

All possible tilings are counted, including those identical by symmetry. Note that distinct dimensions means that, for example, a 2 x 3 rectangle can only be used once, regardless of if it lies horizontally or vertically.

Other known values are a(14) = 517344, a(15) = 6068760, a(16) = 339312. a(13) is greater than 800 million.

			a(1)..a(6),a(8),a(12) = 0 as these squares cannot be tiled with distinct rectangles with edge lengths that do not divide n. For example for the 8 x 8 square only three rectangles are available with dimensions 3 x 3, 3 x 5, and 5 x 5. All other rectangles have an edge length that divides 8 else leave a space of size 1 or 2 units between its edge and the edge of the square. These gaps cannot be filled as no rectangle can have an edge length of 1 or 2.
a(7) = 360. And example tiling is:
.
  +---+---+---+---+---+---+---+
  |       |           |       |
  +       +           +       +
  |       |           |       |
  +---+---+---+---+---+       +
  |                   |       |
  +                   +       +
  |                   |       |
  +---+---+---+---+---+---+---+
  |           |               |
  +           +               +
  |           |               |
  +           +               +
  |           |               |
  +---+---+---+---+---+---+---+
.

Cf. A360499, A360804, A360256, A360773, A182275, A004003.

cp's OEIS Frontend

A216675 Number of ways one can draw arrows between adjacent nodes of an n X n grid such that each node has one outgoing and one incoming arrow.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A304790 The maximal number of different domino tilings allowed by the Ferrers-Young diagram of a single partition of 2n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A334124 a(n) = 2^n * sqrt(Resultant(U_{2*n}(x/2), T_{2*n}(i*x/2))), where T_n(x) is a Chebyshev polynomial of the first kind, U_n(x) is a Chebyshev polynomial of the second kind and i = sqrt(-1).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A340396 a(n) = 2^(n^2 - 1) * Product_{j=1..n, k=1..n} (1 + sin(Pi*j/n)^2 + sin(Pi*k/n)^2).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A353934 Number of tilings of an n X n square using right trominoes, dominoes, and monominoes.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A360804 Number of ways to tile an n X n square using rectangles with distinct areas.

Views

Author

Keywords

Comments

Examples

Crossrefs

A260032 Number of perfect matchings in graph P_{2n} X P_{2n} with a monomer on each corner.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A263425 Number of tilings of an 2n X 2n square using tetrominoes of any shape.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A340535 Number of domino tilings (or dimer coverings) of the 2n X n grid.

Views

Author

A334124 a(n) = 2^n * sqrt(Resultant(U_{2n}(x/2), T_{2n}(i*x/2))), where T_n(x) is a Chebyshev polynomial of the first kind, U_n(x) is a Chebyshev polynomial of the second kind and i = sqrt(-1).

A340396 a(n) = 2^(n^2 - 1) * Product_{j=1..n, k=1..n} (1 + sin(Pij/n)^2 + sin(Pik/n)^2).