OFFSET
1,26
COMMENTS
A (D,d)-polyominoid is a connected set of d-dimensional unit cubes (cells) with integer coordinates in D-dimensional space. For normal polyominoids, two cells are connected if they share a (d-1)-dimensional facet, but here we allow connections where the cells share a lower-dimensional face.
Each row is the counting sequence (by number of cells) of (D,d)-polyominoids with certain restrictions on the allowed connections between cells. Two cells have a connection of type (g,h) if they intersect in a (d-g)-dimensional unit cube and extend in d-h common dimensions. For example, d-dimensional polyominoes use connections of type (1,0), polyplets use connections of types (1,0) (edge connections) and (2,0) (corner connections), normal (3,2)-polyominoids use connections of types (1,0) ("soft" connections) and (1,1) ("hard" connections), hard polyominoids use connections of type (1,1).
Each row corresponds to a triple (D,d,C), where 1 <= d <= D and C is a set of pairs (g,h) with 1 <= g <= d and 0 <= h <= min(g, D-d). The k-th term of that row is the number of free k-celled (D,d)-polyominoids with connections of the types in C. Connections of types not in C are permitted, but the polyominoids must be connected through the specified connections only. For example, polyominoes may have cells that intersect in a point (g = 2) and hard polyominoids can have soft connections (h = 0) that are not needed to keep the polyominoids connected.
The rows are sorted first by D, then by d, and finally by a binary vector indicating which types of connections are allowed, where the connection types (g,h) are sorted lexicographically. (See table in cross-references.)
For each pair (D,d), the first row is 1, 0, 0, ..., corresponding to (D,d,{}) (no connections allowed).
The number of rows corresponding to given values of D and d is 2^((d+1)*(d+2)/2-1) if 2*d <= D and 2^((D-d+1)*(3*d-D+2)/2-1) otherwise.
LINKS
Pontus von Brömssen, Table of n, a(n) for n = 1..210 (first 20 antidiagonals).
Pontus von Brömssen, Python programs that relate row numbers and parameter sets.
Wikipedia, Polyominoid.
EXAMPLE
Array begins:
n\k| 1 2 3 4 5 6 7 8 9 10 11 12
---+------------------------------------------------------------
1 | 1 0 0 0 0 0 0 0 0 0 0 0
2 | 1 1 1 1 1 1 1 1 1 1 1 1
3 | 1 0 0 0 0 0 0 0 0 0 0 0
4 | 1 1 1 1 1 1 1 1 1 1 1 1
5 | 1 1 3 7 20 60 204 702 2526 9180 33989 126713
6 | 1 2 5 16 55 222 950 4265 19591 91678 434005 2073783
7 | 1 0 0 0 0 0 0 0 0 0 0 0
8 | 1 1 2 5 12 35 108 369 1285 4655 17073 63600
9 | 1 1 2 5 12 35 108 369 1285 4655 17073 63600
10 | 1 2 5 22 94 524 3031 18770 118133 758381 4915652 32149296
11 | 1 0 0 0 0 0 0 0 0 0 0 0
12 | 1 1 1 1 1 1 1 1 1 1 1 1
CROSSREFS
The following table lists some sequences that are rows of the array, together with the corresponding values of D, d, and C. Some sequences occur in more than one row. Notation used in the table:
X: Allowed connection.
-: Not allowed connection (but may occur "by accident" as long as it is not needed for connectedness).
.: Not applicable for (D,d) in this row.
!: d < D and all connections have h = 0, so these polyominoids live in d < D dimensions only.
*: Whether a connection of type (g,h) is allowed or not is independent of h.
| | | connections |
| | | g:1122233334 |
n | D | d | h:0101201230 | sequence
----+---+---+--------------+---------
1 | 1 | 1 | * -......... | A063524
2 | 1 | 1 | * X......... | A000012
3 |!2 | 1 | * --........ | A063524
4 |!2 | 1 | X-........ | A000012
5 | 2 | 1 | -X........ | A361625
6 | 2 | 1 | * XX........ | A019988
7 | 2 | 2 | * -.-....... | A063524
8 | 2 | 2 | * X.-....... | A000105
9 | 2 | 2 | * -.X....... | A000105
10 | 2 | 2 | * X.X....... | A030222
11 |!3 | 1 | * --........ | A063524
12 |!3 | 1 | X-........ | A000012
13 | 3 | 1 | -X........ | A365654
14 | 3 | 1 | * XX........ | A365559
15 |!3 | 2 | * ----...... | A063524
16 |!3 | 2 | X---...... | A000105
17 | 3 | 2 | -X--...... | A365654
18 | 3 | 2 | * XX--...... | A075679
19 |!3 | 2 | --X-...... | A000105
20 |!3 | 2 | X-X-...... | A030222
21 | 3 | 2 | -XX-...... | A365995
22 | 3 | 2 | XXX-...... | A365997
23 | 3 | 2 | ---X...... | A365999
24 | 3 | 2 | X--X...... | A366001
25 | 3 | 2 | -X-X...... | A366003
26 | 3 | 2 | XX-X...... | A366005
27 | 3 | 2 | * --XX...... | A365652
28 | 3 | 2 | X-XX...... | A366007
29 | 3 | 2 | -XXX...... | A366009
30 | 3 | 2 | * XXXX...... | A365650
31 | 3 | 3 | * -.-..-.... | A063524
32 | 3 | 3 | * X.-..-.... | A038119
33 | 3 | 3 | * -.X..-.... | A038173
34 | 3 | 3 | * X.X..-.... | A268666
35 | 3 | 3 | * -.-..X.... | A038171
36 | 3 | 3 | * X.-..X.... | A363205
37 | 3 | 3 | * -.X..X.... | A363206
38 | 3 | 3 | * X.X..X.... | A272368
39 |!4 | 1 | * --........ | A063524
40 |!4 | 1 | X-........ | A000012
41 | 4 | 1 | -X........ | A366340
42 | 4 | 1 | * XX........ | A365561
43 |!4 | 2 | * -----..... | A063524
44 |!4 | 2 | X----..... | A000105
45 | 4 | 2 | -X---..... | A366338
46 | 4 | 2 | * XX---..... | A366334
47 |!4 | 2 | --X--..... | A000105
48 |!4 | 2 | X-X--..... | A030222
...
75 |!4 | 3 | * ----.--... | A063524
76 |!4 | 3 | X---.--... | A038119
77 | 4 | 3 | -X--.--... | A366340
78 | 4 | 3 | * XX--.--... | A366336
...
139 | 4 | 4 | * -.-..-...- | A063524
140 | 4 | 4 | * X.-..-...- | A068870
141 | 4 | 4 | * -.X..-...- | A365356
142 | 4 | 4 | * X.X..-...- | A365363
143 | 4 | 4 | * -.-..X...- | A365354
144 | 4 | 4 | * X.-..X...- | A365361
145 | 4 | 4 | * -.X..X...- | A365358
146 | 4 | 4 | * X.X..X...- | A365365
147 | 4 | 4 | * -.-..-...X | A365353
148 | 4 | 4 | * X.-..-...X | A365360
149 | 4 | 4 | * -.X..-...X | A365357
150 | 4 | 4 | * X.X..-...X | A365364
151 | 4 | 4 | * -.-..X...X | A365355
152 | 4 | 4 | * X.-..X...X | A365362
153 | 4 | 4 | * -.X..X...X | A365359
154 | 4 | 4 | * X.X..X...X | A365366
155 |!5 | 1 | * --........ | A063524
156 |!5 | 1 | X-........ | A000012
157 | 5 | 1 | -X........ |
158 | 5 | 1 | * XX........ | A365563
KEYWORD
nonn,tabl
AUTHOR
Pontus von Brömssen, Oct 22 2023
STATUS
approved