cp's OEIS Frontend

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

%I A100632 #20 Jun 19 2021 12:43:53
%S A100632 1,1,1,1,2,2,1,7,8,7,1,18,29,27,26,1,60,166
%N A100632 Number of Shapes(n, d) for a given number of polyhypercubes / polytopominoes n in a given dimensional space d.
%C A100632 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 A100632 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 A100632 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 A100632 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 A100632 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 A100632 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 A100632 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 A100632 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 A100632 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 A100632 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 A100632 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 A100632 A. Clarke, <a href="http://www.recmath.com/PolyPages/index.htm">The Poly Pages</a>
%F A100632 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 A100632 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 A100632 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 A100632 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 A100632 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 A100632 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 A100632 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 A100632 We then define Shape(n, d) recursively as follows:
%F A100632 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 A100632 Shape(n+1, d) consists of all shapes generated by:
%F A100632 For each shape S in Shape(n, d):
%F A100632 For each point P in S:
%F A100632 For each vector V in the Set of Cardinal Vectors:
%F A100632 If P + V is not in S:
%F A100632 Shape(n+1, d) contains the Shape consisting of the union of S and { (P + V) }
%F A100632 a(1/2 n * (n - 1) + d) = the number of shapes in the set Shape(n, d).
%e A100632 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 A100632 Shape(4, 3) consists of
%e A100632 OOOO ..0 .0. 00 00. 0. 0. .0
%e A100632 .... 000 000 00 .00 20 02 20
%e A100632 The second shape is considered to be the same as
%e A100632 OOO
%e A100632 ..O
%e A100632 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 A100632 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 A100632 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 A100632 Cf. A005519, A000988, A000162.
%K A100632 hard,more,nonn,tabl
%O A100632 1,5
%A A100632 Jeffrey C. Jacobs (timehorse(AT)starship.python.net), Dec 03 2004
%E A100632 Link updated by _William Rex Marshall_, Dec 16 2009