A331621 Number of distinct structures that can be made from n cubes without overhangs.
1, 1, 2, 4, 12, 35, 129, 495, 2101, 9154, 41356, 189466, 880156, 4120515, 19425037, 92038062, 438030079, 2092403558, 10027947217, 48198234188, 232261124908, 1121853426115, 5430222591596
Offset: 0
Examples
For n = 0, one (the empty) structure is possible. For n = 1, only one structure is possible, a single cube. For n = 2, two structures are possible: two cubes one on top of the other, and two next to each other. 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. 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.
Links
- Arnauld Chevallier, Javascript Node.JS program
- Nicholas A. Kennedy, Buildings made from cubes, Code Golf Stack Exchange 2020
- Nicholas A. Kennedy, Images of possible structures made from 4 cubes
- Miles, Java program
Crossrefs
Programs
-
Java
See Miles link
-
JavaScript
See Arnauld Chevallier link
Formula
From John Mason, Mar 03 2025: (Start)
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.
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)).
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.
As almost all polyominoes are asymmetrical, a(n)/f(n) tends to 1. (End)
Extensions
a(15)-a(22) from John Mason, Mar 03 2025
Comments