A364440 Triangle T(n,k) (n >= 1 and 1 <= k <= n) read by rows, arising from the Mosaic Problem.

0, 0, 1, 0, 73, 31998, 0, 3960, 10414981, 20334816290, 0, 190475

Offset: 1

Author

Douglas Boffey, Aug 02 2023

Keywords

• nonn
• tabl
• hard
• more

Comments

Fill an n X k array of cells with tiles taken from a set of six (each one connecting two sides of the cell). T(n,k) is the number of tilings containing at least one loop.

There are 6 tiles, all of size 1 X 1, one for each way of joining two sides of the cell.

Examples

			Triangle begins:
        k=1    k=2       k=3          k=4
  n=1:   0;
  n=2:   0,      1;
  n=3:   0,     73,    31998;
  n=4:   0,   3960, 10414981, 20334816290;
  n=5:   0, 190475, ...
  ...
For T(3, 2), there are 73 solutions (squares marked with an asterisk can take any of the six different tiles):
.
1. (36 tilings)   2. (36 tilings)   3. (1 tiling)
  +---+---+---+     +---+---+---+     +---+---+---+
  |   |   |   |     |   |   |   |     |   |   |   |
  |   |   | * |     | * |   |   |     |   |---|   |
  |  /|\  |   |     |   |  /|\  |     |  /|   |\  |
  +---+---+---+     +---+---+---+     +---+---+---+
  |  \|/  |   |     |   |  \|/  |     |  \|   |/  |
  |   |   | * |     | * |   |   |     |   |---|   |
  |   |   |   |     |   |   |   |     |   |   |   |
  +---+---+---+     +---+---+---+     +---+---+---+
		

Links

• Jack Hanke, The Mosaic Problem - How and Why to do Math for Fun, Youtube video.

Formula

T(n,1) = 0 for all n.

T(n,2) = 36^n - ((36*beta - 35)*beta^(1 - n) - (36*alpha - 35)*alpha^(1 - n))/(beta - alpha), where alpha = (1 + sqrt(33/37))/2 and beta = (1 - sqrt(33/37))/2.