OFFSET
1,4
COMMENTS
Null tilings (no k X 1 tiles at all) are not counted. Peter Munn, May 30 2019
There are A000105(n) free n-ominoes. In a loop over all of them, first consider one fixed representative.
Consider the straight k-ominoes (in horizontal or vertical alignments commensurate with the grid of the n-omino), and let c(i,n,k) be the maximum number of straight k-ominoes in any mixture of vertical-horizontal alignments that can be placed inside the i-th n-omino such that no k-ominoes overlap and such that all cells of the k-ominoes are cells of the n-omino.
Obviously c(i,n,k) <= floor(n/k): The coverage by a set of fixed k-ominoes is always incomplete if k is not a divisor of n.
Count all configurations with the number of c(i,n,k) k-ominos in the representative. Configurations with distinct multisets of k-ominoes are considered distinct, even if rotations or flips of the (partially) covered n-omino may exist that map these onto others.
T(n,k) is the number of (partial) tilings of the free n-ominoes with c(i,n,k) straight k-ominoes.
LINKS
FORMULA
T(n,1) = A000105(n).
T(n,n) = 1.
EXAMPLE
The triangle starts with n >= 1, 1 <= k <= n as follows:
1;
1, 1;
2, 4, 1;
5, 8, 4, 1;
12, 35, 18, 4, 1;
35, 89, 61, 22, 5, 1;
108, 425, 206, 97, 28, 5, 1;
369, 1438, 739, 436, 141, 36, 6, 1;
1285, 6818, 3008, 1853, 687, 193, 44, 6, 1;
(...)
From M. F. Hasler and R. J. Mathar, May 27 2019: (Start)
We have T(n,1) = A000105(n) which is the number of different inequivalent n-ominoes, and each one can be maximally filled in exactly one (trivial) way with 1 X 1 monominoes.
We have T(n,n) = 1 because only the straight n X 1 polyomino can be filled in the required way, namely with only straight n-ominoes.
T(3,2) = 4 counts 2 ways of placing a domino into the straight tromino (the two ends of the tromino considered distinct) and 2 ways of placing a domino into the L-tromino (again the two variants obtained by flipping along the diagonal considered distinct). (End)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
R. J. Mathar, May 27 2019
EXTENSIONS
NAME improved, Peter Munn, May 30 2019
STATUS
approved