A361216 -id:A361216 - cp's OEIS frontend

A361221 Triangle read by rows: T(n,k) is the maximum number of ways in which a set of integer-sided rectangular pieces can tile an n X k rectangle, up to rotations and reflections.

1, 1, 1, 1, 5, 8, 2, 12, 95, 719, 2, 31, 682, 20600, 315107

Offset: 1

Pontus von Brömssen, Mar 05 2023

			Triangle begins:
  n\k|  1  2    3     4      5
  ---+------------------------
  1  |  1
  2  |  1  1
  3  |  1  5    8
  4  |  2 12   95   719
  5  |  2 31  682 20600 315107
A 3 X 3 square can be tiled by one 1 X 3 piece, two 1 X 2 pieces and two 1 X 1 pieces in the following 8 ways:
  +---+---+---+   +---+---+---+   +---+---+---+
  |   |   |   |   |       |   |   |   |       |
  +---+---+   +   +---+---+---+   +---+---+---+
  |       |   |   |       |   |   |       |   |
  +---+---+---+   +---+---+---+   +---+---+---+
  |           |   |           |   |           |
  +---+---+---+   +---+---+---+   +---+---+---+
.
  +---+---+---+   +---+---+---+   +---+---+---+
  |   |   |   |   |   |   |   |   |   |       |
  +   +   +---+   +   +---+   +   +   +---+---+
  |   |   |   |   |   |   |   |   |   |   |   |
  +---+---+---+   +---+---+---+   +---+---+---+
  |           |   |           |   |           |
  +---+---+---+   +---+---+---+   +---+---+---+
.
  +---+---+---+   +---+---+---+
  |       |   |   |   |       |
  +---+---+---+   +---+---+---+
  |           |   |           |
  +---+---+---+   +---+---+---+
  |       |   |   |       |   |
  +---+---+---+   +---+---+---+
This is the maximum for a 3 X 3 square, so T(3,3) = 8. There is one other set of pieces that also can tile the 3 X 3 square in 8 ways: three 1 X 2 pieces and three 1 X 1 pieces (see illustration in A361216).
The following table shows all sets of pieces that give the maximum number of tilings for 1 <= k <= n <= 5:
      \     Number of pieces of size
  (n,k)\  1 X 1 | 1 X 2 | 1 X 3 | 2 X 2
  ------+-------+-------+-------+------
  (1,1) |   1   |   0   |   0   |   0
  (2,1) |   2   |   0   |   0   |   0
  (2,1) |   0   |   1   |   0   |   0
  (2,2) |   4   |   0   |   0   |   0
  (2,2) |   2   |   1   |   0   |   0
  (2,2) |   0   |   2   |   0   |   0
  (2,2) |   0   |   0   |   0   |   1
  (3,1) |   3   |   0   |   0   |   0
  (3,1) |   1   |   1   |   0   |   0
  (3,1) |   0   |   0   |   1   |   0
  (3,2) |   2   |   2   |   0   |   0
  (3,3) |   3   |   3   |   0   |   0
  (3,3) |   2   |   2   |   1   |   0
  (4,1) |   2   |   1   |   0   |   0
  (4,2) |   4   |   2   |   0   |   0
  (4,3) |   3   |   3   |   1   |   0
  (4,4) |   5   |   4   |   1   |   0
  (5,1) |   3   |   1   |   0   |   0
  (5,1) |   2   |   0   |   1   |   0
  (5,1) |   1   |   2   |   0   |   0
  (5,2) |   4   |   3   |   0   |   0
  (5,3) |   4   |   4   |   1   |   0
  (5,4) |   7   |   5   |   1   |   0
  (5,5) |   7   |   6   |   2   |   0
It seems that all optimal solutions for A361216 are also optimal here, but occasionally there are other optimal solutions, e.g. for n = k = 3.

Main diagonal: A361222.
Columns: A361223 (k = 1), A361224 (k = 2), A361225 (k = 3).
Cf. A360629, A361216.

A362142 Triangle read by rows: T(n,k) is the maximum number of ways in which a set of integer-sided squares can tile an n X k rectangle, 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 1, 1, 3, 6, 16, 1, 1, 4, 12, 37, 140, 1, 1, 6, 24, 105, 454, 1987, 1, 1, 10, 40, 250, 1566, 9856, 62266, 1, 1, 15, 80, 726, 5670, 47394, 406168, 3899340, 1, 1, 21, 160, 1824, 18738, 223696, 2916492, 38322758, 508317004

Offset: 0

Pontus von Brömssen, Apr 10 2023

			Triangle begins:
  n\k| 0  1  2  3   4    5     6      7       8
  ---+-----------------------------------------
  0  | 1
  1  | 1  1
  2  | 1  1  1
  3  | 1  1  2  4
  4  | 1  1  3  6  16
  5  | 1  1  4 12  37  140
  6  | 1  1  6 24 105  454  1987
  7  | 1  1 10 40 250 1566  9856  62266
  8  | 1  1 15 80 726 5670 47394 406168 3899340
A 5 X 4 rectangle can be tiled by 12 unit squares and 2 squares of side 2 in the following ways:
  +---+---+---+---+   +---+---+---+---+   +---+---+---+---+   +---+---+---+---+
  |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
  +---+---+---+---+   +---+---+---+---+   +---+---+---+---+   +---+---+---+---+
  |   |   |   |   |   |       |   |   |   |   |       |   |   |   |   |       |
  +---+---+---+---+   +       +---+---+   +---+       +---+   +---+---+       +
  |   |   |       |   |       |   |   |   |   |       |   |   |   |   |       |
  +---+---+       +   +---+---+---+---+   +---+---+---+---+   +---+---+---+---+
  |       |       |   |       |   |   |   |       |   |   |   |       |   |   |
  +       +---+---+   +       +---+---+   +       +---+---+   +       +---+---+
  |       |   |   |   |       |   |   |   |       |   |   |   |       |   |   |
  +---+---+---+---+   +---+---+---+---+   +---+---+---+---+   +---+---+---+---+
.
  +---+---+---+---+   +---+---+---+---+   +---+---+---+---+   +---+---+---+---+
  |   |       |   |   |   |   |   |   |   |   |   |   |   |   |       |   |   |
  +---+       +---+   +---+---+---+---+   +---+---+---+---+   +       +---+---+
  |   |       |   |   |       |   |   |   |   |   |   |   |   |       |   |   |
  +---+---+---+---+   +       +---+---+   +---+---+---+---+   +---+---+---+---+
  |   |   |   |   |   |       |   |   |   |   |   |   |   |   |   |   |   |   |
  +---+---+---+---+   +---+---+---+---+   +---+---+---+---+   +---+---+---+---+
  |       |   |   |   |   |       |   |   |       |       |   |       |   |   |
  +       +---+---+   +---+       +---+   +       +       +   +       +---+---+
  |       |   |   |   |   |       |   |   |       |       |   |       |   |   |
  +---+---+---+---+   +---+---+---+---+   +---+---+---+---+   +---+---+---+---+
.
  +---+---+---+---+   +---+---+---+---+   +---+---+---+---+   +---+---+---+---+
  |   |   |       |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
  +---+---+       +   +---+---+---+---+   +---+---+---+---+   +---+---+---+---+
  |   |   |       |   |   |       |   |   |   |   |   |   |   |   |   |       |
  +---+---+---+---+   +---+       +---+   +---+---+---+---+   +---+---+       +
  |   |   |   |   |   |   |       |   |   |       |       |   |       |       |
  +---+---+---+---+   +---+---+---+---+   +       +       +   +       +---+---+
  |       |   |   |   |   |       |   |   |       |       |   |       |   |   |
  +       +---+---+   +---+       +---+   +---+---+---+---+   +---+---+---+---+
  |       |   |   |   |   |       |   |   |   |   |   |   |   |   |   |   |   |
  +---+---+---+---+   +---+---+---+---+   +---+---+---+---+   +---+---+---+---+
.
  +---+---+---+---+
  |   |       |   |
  +---+       +---+
  |   |       |   |
  +---+---+---+---+
  |   |   |   |   |
  +---+---+---+---+
  |   |       |   |
  +---+       +---+
  |   |       |   |
  +---+---+---+---+
The first six of these have no symmetries, so they account for 4 tilings each. The next six have either a mirror symmetry or a rotational symmetry and account for 2 tilings each. The last has full symmetry and accounts for 1 tiling. In total there are 6*4+6*2+1 = 37 tilings. This is the maximum for a 5 X 4 rectangle, so T(5,4) = 37.

Pontus von Brömssen, Table of n, a(n) for n = 0..90 (rows 0..12)

Main diagonal: A362143.
Columns: A000012 (k = 0,1), A073028 (k = 2), A362144 (k = 3), A362145 (k = 4), A362146 (k = 5).
Cf. A219924, A224697, A361216 (rectangular pieces).

A361217 Maximum number of ways in which a set of integer-sided rectangular pieces can tile an n X n square.

Original entry on oeis.org

1, 4, 56, 5752, 2519124, 6126859968

Offset: 1

Pontus von Brömssen, Mar 05 2023

Tilings that are rotations or reflections of each other are considered distinct.

Main diagonal of A361216.

Cf. A360630, A361222.

A361219 Maximum number of ways in which a set of integer-sided rectangular pieces can tile an n X 3 rectangle.

Original entry on oeis.org

2, 11, 56, 370, 2666, 19126, 134902, 1026667, 8049132, 60996816, 450456500, 3427769018, 27127841200, 211563038980, 1837421211974, 15474223886906

Offset: 1

Pontus von Brömssen, Mar 05 2023

Tilings that are rotations or reflections of each other are considered distinct.

			The following table shows the sets of pieces that give the maximum number of tilings for n <= 16. All these sets are unique.
    \     Number of pieces of size
   n \  1 X 1 | 1 X 2 | 1 X 3 | 1 X 4
  ----+-------+-------+-------+------
   1  |   1   |   1   |   0   |   0
   2  |   2   |   2   |   0   |   0
   3  |   3   |   3   |   0   |   0
   4  |   3   |   3   |   1   |   0
   5  |   4   |   4   |   1   |   0
   6  |   7   |   4   |   1   |   0
   7  |   8   |   5   |   1   |   0
   8  |   8   |   5   |   2   |   0
   9  |   9   |   6   |   2   |   0
  10  |  10   |   7   |   2   |   0
  11  |  11   |   8   |   2   |   0
  12  |  11   |   8   |   3   |   0
  13  |  12   |   9   |   3   |   0
  14  |  13   |   8   |   3   |   1
  15  |  14   |   9   |   3   |   1
  16  |  15   |  10   |   3   |   1

Third column of A361216.

Cf. A360632, A361225.

A361424 Triangle read by rows: T(n,k) is the maximum of a certain measure of the difficulty level (see comments) for tiling an n X k rectangle with a set of integer-sided rectangular pieces, rounded down to the nearest integer.

Original entry on oeis.org

1, 2, 2, 2, 6, 8, 4, 12, 48, 80, 4, 16, 80, 480, 1152, 8, 48, 480, 2880, 20160, 53760, 8, 53, 960, 13440, 107520

Offset: 1

Pontus von Brömssen, Mar 11 2023

The (n,k)-tiling difficulty level of a set of integer-sided rectangular pieces is defined as follows. Pieces are free to rotate, so an s X t piece and a t X s piece are equivalent. Consider a random permutation of the pieces together with a random choice of orientation of each nonsquare piece. Take one piece at a time, in the chosen order and with the chosen orientation, and try to put it with its lower left corner in the leftmost free cell in the lowest currently incomplete row of the n X k rectangle. The (n,k)-tiling difficulty level of the set of pieces is the inverse of the probability that this process results in a complete tiling of the n X k rectangle. It equals C(m; m_1, ..., m_j)*2^r/x, where m_1, ..., m_j are the number of pieces of different shapes, m is the total number of pieces, C(m; m_1, ..., m_j) is the multinomial coefficient, r is the number of nonsquare pieces, and x is the number of ways in which an n X k rectangle can be tiled with the set of pieces (where rotations and reflections are considered distinct).
The minimum possible difficulty level is 1, for example for tiling the n X k rectangle with 1 X 1 pieces only.
The difficulty level as defined here is a very crude measure of the perceived difficulty of a tiling puzzle. For example, it does not take into consideration whether a certain piece can fit in the rectangle in only one orientation. This means that the "puzzle" to put a 2 X 1 piece in a 2 X 1 rectangle, for example, has difficulty level 2, the "difficulty" being to orient the piece in the right way.
The only rectangle sizes, currently known to the author, for which the maximum difficulty level is not an integer, are 7 X 2 (difficulty level 160/3) and 13 X 2 (difficulty level 8960/3).

			Triangle begins:
  n\k|  1   2    3     4      5      6  7  8
  ---+--------------------------------------
  1  |  1
  2  |  2   2
  3  |  2   6    8
  4  |  4  12   48    80
  5  |  4  16   80   480   1152
  6  |  8  48  480  2880  20160  53760
  7  |  8  53  960 13440 107520      ?  ?
  8  | 16 120 1920 53760 483840      ?  ?  ?
For (n,k) = (7,3), the set consisting of three 1 X 2 pieces, one 1 X 5 piece, one 1 X 6 piece, and one 2 X 2 piece gives the maximum difficulty level, which equals C(6;3,1,1,1)*2^5/4 = 120*32/4 = 960 = T(7,3). The 4 in the denominator is the number of ways in which this set of pieces can tile the 7 X 3 rectangle (all 4 are equivalent under rotations and reflections).
The following table shows all sets of pieces that give the maximum (n,k)-tiling difficulty level up to (n,k) = (7,5).
      \               Number of pieces of size
  (n,k)\  1X1 | 1X2 | 1X3 | 1X4 | 1X5 | 1X6 | 1X7 | 2X2 | 2X3
  ------+-----+-----+-----+-----+-----+-----+-----+-----+----
  (1,1) |  1  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |  0
  (2,1) |  0  |  1  |  0  |  0  |  0  |  0  |  0  |  0  |  0
  (2,2) |  0  |  2  |  0  |  0  |  0  |  0  |  0  |  0  |  0
  (3,1) |  1  |  1  |  0  |  0  |  0  |  0  |  0  |  0  |  0
  (3,1) |  0  |  0  |  1  |  0  |  0  |  0  |  0  |  0  |  0
  (3,2) |  1  |  1  |  1  |  0  |  0  |  0  |  0  |  0  |  0
  (3,3) |  1  |  1  |  2  |  0  |  0  |  0  |  0  |  0  |  0
  (4,1) |  0  |  2  |  0  |  0  |  0  |  0  |  0  |  0  |  0
  (4,2) |  0  |  2  |  0  |  1  |  0  |  0  |  0  |  0  |  0
  (4,2) |  0  |  1  |  2  |  0  |  0  |  0  |  0  |  0  |  0
  (4,3) |  0  |  1  |  2  |  1  |  0  |  0  |  0  |  0  |  0
  (4,4) |  0  |  1  |  2  |  2  |  0  |  0  |  0  |  0  |  0
  (5,1) |  1  |  2  |  0  |  0  |  0  |  0  |  0  |  0  |  0
  (5,1) |  0  |  1  |  1  |  0  |  0  |  0  |  0  |  0  |  0
  (5,2) |  1  |  2  |  0  |  0  |  1  |  0  |  0  |  0  |  0
  (5,2) |  0  |  3  |  0  |  1  |  0  |  0  |  0  |  0  |  0
  (5,3) |  0  |  3  |  0  |  1  |  1  |  0  |  0  |  0  |  0
  (5,3) |  0  |  1  |  3  |  1  |  0  |  0  |  0  |  0  |  0
  (5,4) |  0  |  1  |  3  |  1  |  1  |  0  |  0  |  0  |  0
  (5,5) |  1  |  0  |  8  |  0  |  0  |  0  |  0  |  0  |  0
  (6,1) |  0  |  3  |  0  |  0  |  0  |  0  |  0  |  0  |  0
  (6,2) |  0  |  1  |  2  |  1  |  0  |  0  |  0  |  0  |  0
  (6,3) |  0  |  1  |  1  |  1  |  1  |  0  |  0  |  1  |  0
  (6,4) |  0  |  1  |  1  |  1  |  1  |  1  |  0  |  1  |  0
  (6,4) |  0  |  0  |  2  |  2  |  2  |  0  |  0  |  0  |  0
  (6,5) |  0  |  0  |  2  |  2  |  2  |  1  |  0  |  0  |  0
  (6,6) |  0  |  0  |  2  |  2  |  2  |  2  |  0  |  0  |  0
  (7,1) |  1  |  3  |  0  |  0  |  0  |  0  |  0  |  0  |  0
  (7,1) |  0  |  2  |  1  |  0  |  0  |  0  |  0  |  0  |  0
  (7,2) |  0  |  1  |  4  |  0  |  0  |  0  |  0  |  0  |  0
  (7,3) |  0  |  3  |  0  |  0  |  1  |  1  |  0  |  1  |  0
  (7,3) |  0  |  1  |  1  |  1  |  0  |  1  |  0  |  0  |  1
  (7,4) |  0  |  3  |  0  |  0  |  2  |  1  |  0  |  0  |  1
  (7,4) |  0  |  0  |  3  |  2  |  1  |  1  |  0  |  0  |  0
  (7,5) |  0  |  3  |  0  |  0  |  2  |  1  |  1  |  0  |  1
  (7,5) |  0  |  0  |  3  |  2  |  1  |  1  |  1  |  0  |  0

Main diagonal: A361425.
Columns: A016116 (k = 1), A361426 (k = 2), A361427 (k = 3), A361428 (k = 4).
Cf. A360629, A361216, A361221.

T(n,1) = A016116(n).

A361218 Maximum number of ways in which a set of integer-sided rectangular pieces can tile an n X 2 rectangle.

Original entry on oeis.org

1, 4, 11, 29, 94, 263, 968, 3416, 11520, 41912, 136972, 481388, 1743784, 6275886, 23615432, 93819128, 368019576, 1367900808, 5403282616, 19831367476, 76031433360, 300581321056, 1143307393600, 4542840116352, 17001097572544, 65314285778004, 246695766031432

Offset: 1

Pontus von Brömssen, Mar 05 2023

nonn

Tilings that are rotations or reflections of each other are considered distinct.

			The following table shows the sets of pieces that give the maximum number of tilings for n <= 27. The solutions are unique except for n = 1.
    \     Number of pieces of size
   n \  1 X 1 | 1 X 2 | 1 X 3 | 1 X 4
  ----+-------+-------+-------+------
   1  |   2   |   0   |   0   |   0
   1  |   0   |   1   |   0   |   0
   2  |   2   |   1   |   0   |   0
   3  |   2   |   2   |   0   |   0
   4  |   4   |   2   |   0   |   0
   5  |   4   |   3   |   0   |   0
   6  |   4   |   4   |   0   |   0
   7  |   5   |   3   |   1   |   0
   8  |   5   |   4   |   1   |   0
   9  |   7   |   4   |   1   |   0
  10  |   7   |   5   |   1   |   0
  11  |   7   |   6   |   1   |   0
  12  |   9   |   6   |   1   |   0
  13  |   8   |   6   |   2   |   0
  14  |  10   |   6   |   2   |   0
  15  |  10   |   7   |   2   |   0
  16  |  10   |   6   |   2   |   1
  17  |  10   |   7   |   2   |   1
  18  |  12   |   7   |   2   |   1
  19  |  12   |   8   |   2   |   1
  20  |  12   |   9   |   2   |   1
  21  |  13   |   8   |   3   |   1
  22  |  13   |   9   |   3   |   1
  23  |  15   |   9   |   3   |   1
  24  |  15   |  10   |   3   |   1
  25  |  15   |  11   |   3   |   1
  26  |  17   |  11   |   3   |   1
  27  |  17   |  12   |   3   |   1

Second column of A361216.

Cf. A360631, A361224.

A361220 Maximum number of ways in which a set of integer-sided rectangular pieces can tile an n X 4 rectangle.

Original entry on oeis.org

3, 29, 370, 5752, 82310, 1232770, 19119198, 307914196, 5020522468, 89323885136, 1708142066600

Offset: 1

Pontus von Brömssen, Mar 05 2023

Tilings that are rotations or reflections of each other are considered distinct.

			The following table shows the sets of pieces that give the maximum number of tilings for n <= 11. All these sets are unique.
    \     Number of pieces of size
   n \  1 X 1 | 1 X 2 | 1 X 3 | 1 X 4
  ----+-------+-------+-------+------
   1  |   2   |   1   |   0   |   0
   2  |   4   |   2   |   0   |   0
   3  |   3   |   3   |   1   |   0
   4  |   5   |   4   |   1   |   0
   5  |   7   |   5   |   1   |   0
   6  |   8   |   5   |   2   |   0
   7  |  10   |   6   |   2   |   0
   8  |  10   |   8   |   2   |   0
   9  |  11   |   8   |   3   |   0
  10  |  11   |   8   |   3   |   1
  11  |  13   |   9   |   3   |   1

Fourth column of A361216.

cp's OEIS Frontend

A361221 Triangle read by rows: T(n,k) is the maximum number of ways in which a set of integer-sided rectangular pieces can tile an n X k rectangle, up to rotations and reflections.

Views

Author

Keywords

Examples

Crossrefs

A362142 Triangle read by rows: T(n,k) is the maximum number of ways in which a set of integer-sided squares can tile an n X k rectangle, 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

A361217 Maximum number of ways in which a set of integer-sided rectangular pieces can tile an n X n square.

Views

Author

Keywords

Comments

Crossrefs

A361219 Maximum number of ways in which a set of integer-sided rectangular pieces can tile an n X 3 rectangle.

Views

Author

Keywords

Comments

Examples

Crossrefs

A361424 Triangle read by rows: T(n,k) is the maximum of a certain measure of the difficulty level (see comments) for tiling an n X k rectangle with a set of integer-sided rectangular pieces, rounded down to the nearest integer.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A361218 Maximum number of ways in which a set of integer-sided rectangular pieces can tile an n X 2 rectangle.

Views

Author

Keywords

Comments

Examples

Crossrefs

A361220 Maximum number of ways in which a set of integer-sided rectangular pieces can tile an n X 4 rectangle.

Views

Author

Keywords

Comments

Examples

Crossrefs