|
| |
|
|
A100632
|
|
Number of Shapes(n, d) for a given number of polyhypercubes / polytopominoes n in a given dimensional space d.
|
|
0
|
|
|
|
1, 1, 1, 1, 2, 2, 1, 7, 8, 7, 1, 18, 29, 27, 26, 1, 60, 166
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
a(1/2 * n * (n-1) + d) gives values of Shapes(n, d) for n > 0, d > 0, d <= n. For d > n, use a(1/2 * n * (n + 1)) or A005519's a(n).
A polytopomino shape is a shape constructed of n contiguous hypercubes that is invariant over rotation but not necessarily over 'flipping', i.e. mirror images are distinct. See example for details of when flipping is or is not considered.
A000988 gives values for Shape(n, 2), e.g. a(1/2 * n * (n - 1) + 2) and A000162 for Shape(n, 3), e.g. a(1/2 * n * (n - 1) + 3.
A005519 gives values for Shape(n, n), e.g. a(1/2 * n * (n + 1)). These shapes always can be expressed using only n-1 dimensions and therefore contain no mirror-image or "flipped" shapes.
Shape(n, d) is the union of all shapes with n points that can be expressed in a dimension x for x from 1 to d - 1 where "flipped" shapes are excluded plus all shapes with n points that must be expressed by at least d dimensions where "flipped" shapes are included. A049429 gives values for x in [1, d - 1] and n.
Specificly, if b(m) defines the sequence A049429, b(1/2 * n * (n + 1) + x) is the term for all shapes that must be expressed in at least x dimensions and containing n points.
There is no sequence that describes shapes with n points and exactly d dimensions for which "flipped" shapes are considered distinct, so this formula cannot be completely expressed as the sum of other formula.
The main difficulty in computing this sequence is in a) the fast implemention of a set (as in a set of points [shape] and a set of shapes [Shape(n, d)]), especially with respect to rotation of points and b) the difficulty in eliminating duplicate entries.
The later case is difficult because in order to determine whether two shapes are the same, one must compute all possible R in order to determine the R that may orient shape X the same as shape Y. The translation vector T is uniquely given based on R but requires finding the minimum point of the bounding hypercube of each shape that is linear with respect to d.
Ideally, a good algorithm for b must be found, especially if a "definitive orientation" can be determined such that all shapes will be oriented using the definitive orientation before being compared and thus the comparison consists only of comparing the points in X and Y to make sure they are the same.
Also, it should be possible to reduce the loop over Cardinal Vectors since some vectors are equivalent, such as adding (1, 0) or (-1, 0) to the point (0, 0) since the shape has symmetry and therefore both new shapes are equivalent.
|
|
|
LINKS
|
|
|
|
FORMULA
|
Let a shape consist of a set of n integral points such that all points are adjacent to at least 1 other point and that all points are connected either directly or indirectly through adjacency.
Let two points be adjacent if and only if the distance between point A and point B is given by a unit vector which lies parallel to one of the Cartesian axes in d dimensional space.
E.g. if d is 2 and n is 2, a shape may consist of the points (0, 0) and (1, 0). The distance between these points would then be the unit vector (1, 0) which lies parallel to the x-axis.
Two shapes, X and Y are considered the same if and only if there exists some rotation unit matrix R and some translation vector T for which the set of points X * R + T is equal to the set of points Y. The unit rotation R must have determinant 1.
A determinant of -1 for R is considered a "flip" and is therefore not allowed. However it should be noted that there will always exist an R[d+1] such that R[d+1] = [[R 0] [0 det(R)]], which always has a determinant of 1.
Thus when considering a higher-order dimension, a flip in a lower dimension is now possible. In other words, Shapes are 1-sided only if they must be represented using at least d dimensions.
The Set of Cardinal Vectors consists of all unit vectors parallel to a Cartesian axis for the given dimension d. Thus when d is 2, the Set of Cardinal Vectors consists of { (1, 0) (0, 1) (-1, 0) (0, -1) }.
We then define Shape(n, d) recursively as follows:
Shape(1, d) consists of the single set containing a single point (0, 0, ..., 0) in d-Space, e.g. Shape(1, d) = { { (0, 0, ..., 0) } } for all d.
Shape(n+1, d) consists of all shapes generated by:
For each shape S in Shape(n, d):
For each point P in S:
For each vector V in the Set of Cardinal Vectors:
If P + V is not in S:
Shape(n+1, d) contains the Shape consisting of the union of S and { (P + V) }
a(1/2 n * (n - 1) + d) = the number of shapes in the set Shape(n, d).
|
|
|
EXAMPLE
|
Example 1: a(9) gives the number of shapes in Shape(4, 3). We describe these 3-dimensional shapes by using 2 rows of text where "O" represents a block in the z=0 plane and "2" two stacked blocks, the first in the z=0 plane, the second in the z=1 plane.
Shape(4, 3) consists of
OOOO ..0 .0. 00 00. 0. 0. .0
.... 000 000 00 .00 20 02 20
The second shape is considered to be the same as
OOO
..O
because it can be expressed in 2 dimensions and we are allowed 3 (d = 3) so these two shapes are the same despite being flipped. However the last two shapes require 3 dimensions to express and because that is equal to or greater than d = 3, the flipped shapes are considered distinct.
This is equivalent to saying that in 3 dimensions there is no physical way to turn or move the second to last shape to make it look like the last.
Example 2: a(8) gives the number of shapes in Shape(4, 2). This is equivalent to the set of 1-sided polyominoes consisting of 4 squares.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
Jeffrey C. Jacobs (timehorse(AT)starship.python.net), Dec 03 2004
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
