cp's OEIS Frontend

A331621 Number of distinct structures that can be made from n cubes without overhangs.

%I A331621 #51 Mar 04 2025 07:51:34
%S A331621 1,1,2,4,12,35,129,495,2101,9154,41356,189466,880156,4120515,19425037,
%T A331621 92038062,438030079,2092403558,10027947217,48198234188,232261124908,
%U A331621 1121853426115,5430222591596
%N A331621 Number of distinct structures that can be made from n cubes without overhangs.
%C A331621 This is an extension of the free polyominoes (A000105) to the third dimension. Structures are considered equivalent if they can be mapped into each other by reflection in a vertical plane or rotation around the vertical axis. They are not equivalent if they can only be mapped onto each other by rotation around an axis parallel to the horizontal plane.
%C A331621 From _John Mason_, Mar 03 2025: (Start)
%C A331621 Equivalently, the sequence enumerates inscribed polyominoes that have a positive integer in each square, such that the size of the polyomino is considered to be the sum of the integers.
%C A331621 Examples.
%C A331621   Size 1:
%C A331621   +-+
%C A331621   |1|
%C A331621   +-+
%C A331621 .
%C A331621   Size 2:
%C A331621   +-+-+ +-+
%C A331621   |1|1| |2|
%C A331621   +-+-+ +-+
%C A331621 .
%C A331621   Size 3:
%C A331621   +-+-+-+ +-+-+ +-+-+ +-+
%C A331621   |1|1|1| |2|1| |1|1| |3|
%C A331621   +-+-+-+ +-+-+ +-+-+ +-+
%C A331621                   |1|
%C A331621                   +-+
%C A331621 (End)
%H A331621 Arnauld Chevallier, <a href="https://codegolf.stackexchange.com/a/198183/">Javascript Node.JS program</a>
%H A331621 Nicholas A. Kennedy, <a href="https://codegolf.stackexchange.com/q/198175/">Buildings made from cubes</a>, Code Golf Stack Exchange 2020
%H A331621 Nicholas A. Kennedy, <a href="https://i.stack.imgur.com/nEgsP.png">Images of possible structures made from 4 cubes</a>
%H A331621 Miles, <a href="https://codegolf.stackexchange.com/a/198205/">Java program</a>
%F A331621 From _John Mason_, Mar 03 2025: (Start)
%F A331621 Define a(n)=f(n)+g(n) where f(n) enumerates the structures having an asymmetrical base, and g(n) enumerates the structures having a symmetrical base.
%F A331621 Then for n>=4, f(n) = Sum_{i=4..n} ((A006749(i)*C(n-1,i-1)), and g(n) < Sum_{i=1..n} ((A259090(i)*C(n-1,i-1)).
%F A331621 For structures having a base with: reflective orthogonal symmetry about an axis that passes through cell vertices, 180 degree rotational symmetry about a point at a cell vertex or midway along an edge, the number of structures is (1) for odd n: Sum_{i=1..n} ((S(i)*C(n-1,i-1)) / 2, and (2) for even n: Sum_{i=1..n} ((S(i)*(C(n-1,i-1)+C(n/2-1,i/2-1)) / 2, for S(n) = A349329(n), A351616(n) and A234008(n) respectively.
%F A331621 As almost all polyominoes are asymmetrical, a(n)/f(n) tends to 1. (End)
%e A331621 For n = 0, one (the empty) structure is possible.
%e A331621 For n = 1, only one structure is possible, a single cube.
%e A331621 For n = 2, two structures are possible: two cubes one on top of the other, and two next to each other.
%e A331621 For n = 3, four structures are possible: an L shape with the L oriented vertically, an L shape with the L laid flat, a structure with 3 cubes stacked on top of each other and a structure with 3 cubes laid flat.
%e A331621 For n = 4, there are 12 possible distinct structures made from 4 cubes without overhangs. These include 1 structure that is 4 cubes tall, 1 structure that is 3 cubes tall, 5 structures that are 2 cubes tall and 5 that are 1 cube tall.
%o A331621 (JavaScript) See Arnauld Chevallier link
%o A331621 (Java) See Miles link
%Y A331621 Extension to the third dimension of A000105.
%Y A331621 Cf. A006749, A007318, A259090, A349329, A351616, A234008.
%K A331621 nonn,more
%O A331621 0,3
%A A331621 _Nicholas A. Kennedy_, Jan 22 2020
%E A331621 a(15)-a(22) from _John Mason_, Mar 03 2025