Thread: Cube Mountains
View Single Post
Old 2008-05-30, 04:09   #7
wblipp's Avatar
May 2003
New Haven

236110 Posts

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.
wblipp is offline   Reply With Quote