Cube Mountains

[davar55]

Call an "N-mountain" an arrangement of unit cubes in layers,
such that the bottom layer is an NxN square (of cubes --
I hope that's clear enough), each layer has fewer cubes than
any layer below it, and cubes are stacked evenly over cubes
(so that vertices of neighboring cubes correspond) and with
no vertical gaps.

For instance, the "height" of an N-mountain (number of layers)
can range from 1 to N^2.

How many N-mountains are there, for N=1,2,3,4,5 ?

(Don't count rotationally congruent mountains as distinct.)
((That's rotation around the center of the bottom layer.))

[davieddy]

This looks like a messy problem.
Looking at the N=2 case in my head
my first query starts at height 2:
Can we place a total of two cubes
in opposite corners or does this violate
your "vertical gaps" rule?
Why exclude rotational symmetry and not
reflectional?

[davar55]

I intended the simplest form of this problem,
and must have muddled my intent. In regard
to the issue of rotational symmetry, I just
meant that if you can rotate a "mountain"
thru a quarter or half turn and get the same
result, it should only be counted once. I
should probably have left the condition out.

As to vertical gaps, except for the bottom layer,
which must be full of cubes, every cube must
be situated over a column of cubes (no gaps
vertically) but within a layer any configuration
is allowed (so placing cubes in opposite corners,
creating "horizontal" gaps, is fine.)

Sorry about any confusion.

[Uncwilly]

For n=2 I get a quick count of 15.

[retina]

Isn't this the partition problem in disguise? Or at least a variant of it?

[wblipp]

If we ignore the rotation condition,

Then the square shape of the base is irrelevant, and we can ask about Mountains with "n" blocks in the base. These can be defined recursively. For n blocks, you can chose k = 0 to (n-1) blocks for the next level. You can place those k blocks in C(n,k) ways. You can continue building higher in M(k) ways. So M(0)=1 and

M(n) = Sum {k=0 to n-1} (C(n,k)*M(k))

which has first few values
0 1
1 1
2 3
3 13
4 75 -- this is the 2x2 base counting rotations as distinct
5 541
6 4683
7 47293
8 545835
9 7087261 -- this is the 3x3 base

Which matches two integer sequences.


To answer the actual puzzle, I would need to also need to count the 90 degree and 180 degree rotations to subtract the duplicates.

[wblipp]

For n even
The rotations are easy to calculate from the non-rotation numbers. For 180 degrees, you build any mountain on the front half, then duplicate it on the back half. For 90 degrees, you build any mountain in a quadrant and triplicate it to the other quadrants. For the 2x2 square we have M(4)=75 unrotated mountains, of which M(2)=3 have 180 degree symmetry and M(1)=1 have 90 degree symmetry. Undoing rotations, we have counted the 75-3=72 unsymmetric mountains 4 times, the 3-2=2 mountains with only 180 degree symmetry twice, and the 1 90 degree symmetric mountain once, so the answer for 2x2 is 72/4 + 2/2 + 1 = 20.

Comparing this to unwilly's count of 15 - I think unwilly counted mirror symmetry as identical, too. I sketched out the 20 unique mountains; there are five pairs that are mirror images but cannot be rotated to each other.

Continuing the calculation of M(n) through 16, it continues to match the two series. (At M(17), where the series diverge, M(n) matches A000670.)

For the 4x4 square, the answer is (M(16)-M(8))/4 +(M(8)-M(4))/2 +M(2)
= 1328913670631835

For odd n you must keep track of the base's central square separately from the other squares. I'm not sufficiently interested to work this out tonight. Perhaps someone else will work out the odd bases.

[davieddy]

Originally Posted by davar55

As to vertical gaps, except for the bottom layer,
which must be full of cubes, every cube must
be situated over a column of cubes (no gaps
vertically) but within a layer any configuration
is allowed (so placing cubes in opposite corners,
creating "horizontal" gaps, is fine.)

Sorry about any confusion.

If you put one cube on top of another
then lift the top one 1 mm I would describe
the resulting 1 mm thick gap as "horizontal".
Hence my initial confusion.

[wblipp]

For odd n
It's easier to count the symmetric mountains than I has thought. For 180 degrees, you build a mountain on half of the non-central squares plus the central square. When you rotate that to get a symmetric mountain on the full base, the central square rotates onto itself, but that's OK. The same process works for counting 90 degree symmetric mountains.

Hence the number of unique mountains on the 3x3 base is

(M(9)-M(5))/4 + (M(5)-M(3))/2 + M(3) = 1771957

And the 5x5 base has

(M(25)-M(13))/4 + (M(13)-M(7))/2 + M(7)
= 26674341359618944088110485277

There's a substantial chance I made an error in calculating M(25). Here are my calculations to check against:

0 1
1 1
2 3
3 13
4 75
5 541
6 4683
7 47293
8 545835
9 7087261
10 102247563
11 1622632573
12 28091567595
13 526858348381
14 10641342970443
15 230283190977853
16 5315654681981355
17 130370767029135901
18 3385534663256845323
19 92801587319328411133
20 2677687796244384203115
21 81124824998504073881821
22 2574844419803190384544203
23 85438451336745709294580413
24 2958279121074145472650648875
25 106697365438475775825583498141

[nibble4bits]

When I was reading this problem, I was initially thinking you meant something like this for c=number of cubes and n=number of layers:

c=n^2+(n-1)^2+(n-2)^2+...+3^2+2^2+1
In other words the number of cubes is the sum of the squares. Sorry for the pun.

It turns out that you seem to be wanting to know the number of combinations to something like this:

n=2
3x3 for bottom
2x2 for top
no 1x1

n=2
3x3 for bottom
1x1 for top

n=3
4x4 for bottom
2x2 for middle
1x1 for top

There is of course an infinite number if you don't limit the base to a finite value.

Or did you mean the same cases I provided, but n=3,3, and 4, respectively?

It seems that you could also mean that if I had a 2x2 square on top of a 5x5, that there's (1+5-2)^2=4^2=16 possible positions assuming they're aligned to a grid and always within the area of the layer directly below. Removing rotations and reflections is going to reduce that from 16 to just 3 positions. Removing translations of course reduces it to just one position.


Note that these other possible interpretations are interesting problems in their own rights. They're all fun to work on.