A100632 - OEIS

%I #20 Jun 19 2021 12:43:53

%S 1,1,1,1,2,2,1,7,8,7,1,18,29,27,26,1,60,166

%N Number of Shapes(n, d) for a given number of polyhypercubes / polytopominoes n in a given dimensional space d.

%C 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).

%C 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.

%C 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.

%C 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.

%C 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.

%C 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.

%C 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.

%C 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.

%C 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.

%C 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.

%C 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.

%H A. Clarke, <a href="http://www.recmath.com/PolyPages/index.htm">The Poly Pages</a>

%F 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.

%F 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.

%F 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.

%F 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.

%F 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.

%F 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.

%F 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) }.

%F We then define Shape(n, d) recursively as follows:

%F 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.

%F Shape(n+1, d) consists of all shapes generated by:

%F For each shape S in Shape(n, d):

%F For each point P in S:

%F For each vector V in the Set of Cardinal Vectors:

%F If P + V is not in S:

%F Shape(n+1, d) contains the Shape consisting of the union of S and { (P + V) }

%F a(1/2 n * (n - 1) + d) = the number of shapes in the set Shape(n, d).

%e 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.

%e Shape(4, 3) consists of

%e OOOO ..0 .0. 00 00. 0. 0. .0

%e .... 000 000 00 .00 20 02 20

%e The second shape is considered to be the same as

%e OOO

%e ..O

%e 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.

%e 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.

%e 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.

%Y Cf. A005519, A000988, A000162.

%K hard,more,nonn,tabl

%O 1,5

%A Jeffrey C. Jacobs (timehorse(AT)starship.python.net), Dec 03 2004

%E Link updated by _William Rex Marshall_, Dec 16 2009