Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

How many (labeled or unlabeled) unfoldings of the 1 x 1 x n cube are there?

alt text

The dissections of the cube are related to each other by "hinge" moves (which I've tried to draw). The graph of unfolding of the cube seems connected by these hinge moves.


It's equivalent to consider cutting the cube along the edges. Then we're looking for uniform spanning trees on the surface of the cube.

For my 9 (unlabeled) (possibly incomplete list of) shapes, how often do they appear among (uniformly random) unfoldings of the labeled cube?? I'd like to know the general principles involved.

share|improve this question
    
Incidentally, there are exponentially many spanning trees in general: $2^{\Omega(\sqrt{F})}$ for a polyhedron of $F$ faces. –  Joseph O'Rourke Jan 22 '12 at 13:29

2 Answers 2

Let $a_n$ be defined by the recursion $$a_{n+2} + 4 a_{n+1} + a_n =0,\ a_1=-4,\ a_2=15.$$ Let $b_n$ be defined by the recursion $$b_{n+2} + 6 b_{n+1} + b_n =0,\ b_1 =-6,\ b_2=35.$$

The number of unfoldings of the labeled $1 \times 1 \times n$ cube is $-4 a_n^2 b_n$. (I might have a sign error here.)

We count spanning trees using the matrix tree theorem. Let $G$ be the dual graph to the $1 \times 1 \times n$ cube (so $G$ has $4n+2$ vertices). Let $V$ be the vector space of functions on the vertices of $G$. Let $\Lambda: V \to V$ be the Laplacian operator. Then $\Lambda$ has a one dimensional kernel -- the constant function -- and we are supposed to compute the coefficient of $t$ in $\det(\Lambda - t \mathrm{Id})$.

The cyclic group of order $4$ acts on the $1 \times 1 \times n$ cube by rotation around the long axis. This action commutes with $\Lambda$. So we can compute $\Lambda$ separately on each of the four eigenspaces of this rotation. The corresponding matrices are $$\begin{pmatrix} -4 & 1 & 0 & 0 & 0 & \cdots & 0 \\ 1 &-4 & 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 &-4 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 &-4 & 1 & \cdots & 0 \\ 0 & 0 & 0 & 1 &-4 & \cdots & 0 \\ & & & & & \ddots & \\ 0 & 0 & 0 & 0 & 0 & \cdots & -4 \end{pmatrix} \ \mathrm{on\ the} \pm i \ \mathrm{eigenspace}$$ $$\begin{pmatrix} -6 & 1 & 0 & 0 & 0 & \cdots & 0 \\ 1 &-6 & 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 &-6 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 &-6 & 1 & \cdots & 0 \\ 0 & 0 & 0 & 1 &-6 & \cdots & 0 \\ & & & & & \ddots & \\ 0 & 0 & 0 & 0 & 0 & \cdots & -6 \end{pmatrix} \ \mathrm{on\ the} -1 \ \mathrm{eigenspace}$$ $$\begin{pmatrix} -4 & 4 & 0 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 \\ 1 & -2 & 1 & 0 & 0 & 0 & \cdots & 0 & 0 & 0\\ 0 & 1 &-2 & 1 & 0 & 0 & \cdots & 0 & 0 & 0\\ 0 & 0 & 1 &-2 & 1 & 0 & \cdots & 0 & 0 & 0\\ 0 & 0 & 0 & 1 &-2 & 1 & \cdots & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 &-2 & \cdots & 0 & 0 & 0\\ & & & & & \ddots & \\ 0 & 0 & 0 & 0 & 0 & 0 & \cdots & 1 & -2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & \cdots & 0 & 4 & -4 \end{pmatrix} \ \mathrm{on\ the}\ 1 \ \mathrm{eigenspace}$$

The first two matrices are invertible and obey the recursions $a_n$ and $b_n$ respectfully. (See the recursive formula displayed in this article.)

The last matrix has a one dimension kernel. Taking the cofactor by deleting the last row and column, one gets a matrix whose determinant is $-4$, as can be checked from the same recursion as above.

Putting it all together, the number of spanning trees is $-4 a_n^2 b_n$.

I don't understand the statistical question you want to ask about the unfolded shapes.


Remark: Using the cyclic symmetry broght this computation down into the range of reasonable computation. But, even without that, I immediately knew that the answer would obey some linear recursion. Consider building a spanning tree of $G$ one layer at a time as we travel along the long axis of the cube. At the $k$-th partial stage, there are $4$ vertices of $G$ on the exposed boundary; call them $u_k$, $v_w$, $w_v$, $x_k$. The graph so far is a forest, each connected component of which contains at least one of the four exposed vertices. There are $15$ ways to group these $4$ vertices into connected components, one of which is actually impossible for planarity reasons. So there is some $14 \times 14$ matrix which records, for example, if the vertices on one level are grouped as $(\{ u_k, v_k \}, \{ w_k \}, \{ x_k \})$, how many ways are there to extend the forest to one where the vertices on the next level are grouped as $( \{ u_{k+1} \}, \{ v_{k+1}, w_{k+1}, x_{k+1} \})$. Taking powers of this $14 \times 14$ matrix and then pairing with some row and column vectors to handle end effects, you get this count.

This is what I learned to call the "transfer matrix method" (although Wikipedia seems to call something else by that name) and it solves almost all "linear" combinatorics problems.

share|improve this answer
    
So this is how you use matrix-tree! I will think about how to modify your answer to the labeled case & how to make my statistics question more precise. –  john mangual Jan 22 '12 at 18:34
    
Impressive analysis! I would just like to verify that if $n=1$, your formula yields $−4(−4)^{2}(−6)=384$, and indeed there are 384 unfoldings of the cube (and the regular octahedron), obviously many of them congruent as geometric objects. –  Joseph O'Rourke Jan 22 '12 at 19:00
    
we found 11 different shapes and I wanted to know how often each appears among the 384. they are related to each other by hinge moves and i bet you can have a markov chain out of them. –  john mangual Jan 22 '12 at 21:40
1  
You actually just want to know the answer for $n=1$? I assumed your question was meant to make sense as $n \to infty$, which is why I didn't understand it. If you just want the count for $n=1$, I don't see anything to do more clever that making a program to count them. –  David Speyer Jan 22 '12 at 22:37
2  
@Zsbán: Good question, but in fact no edge-unfolding (cutting along edges) of a Platonic solid overlaps in the plane. Long believed; recently settled. But as soon as one extends to Archimedian solids, overlap does occur. –  Joseph O'Rourke Jan 23 '12 at 13:17

Not an answer; just a remark: Your inventory of the unfoldings of the $1 \times 1 \times 1$ cube is missing two unfoldings: there are 11.
            Cube Nets
       (Figure from How To Fold It: The Mathematics of Linkages, Origami, and Polyhedra, p.166)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.