# Number of hypercube unfoldings

While writing the code for this answer, I noticed that I not only could calculate the number of unfoldings of the $4$-cube, but also the number of the $n$-cube for more values of $n$. Basically, we count pairs $(T, P)$, where $T$ is a tree on $2n$ nodes and $P$ is a perfect matching of the complement of $P$. We consider $(T, P)$ equivalent to $(T', P')$ if there is an automorphism $\phi$ of $T$, such that $T=\phi(T)=T'$ and $\phi(P) = P'$.

Here's what I found: $$\begin{array}{c|cccccc}n&3&4&5&6&7&8\\\hline \text{# of unfoldings} &11& 261& 9694& 502110& 33064966& 2642657228\end{array}$$ For $n=7$ the calculation took about $7$ hours on a desktop pc with 8 cores. The calculation can almost trivially be parallelized, since we can consider each tree $T$ at the same time. The case $n=8$ was done on a small cluster.

Have these unfoldings be counted before?

The sequence is in the oeis: A091159, but only two terms are given (as of today). I searched for the number $33064966$ on the net but couldn't find anything.

[11, 261, 9694, 502110, 33064966, 2642657228]

• Searching for 502110 yields some results (if you filter out postal zip-codes): lews-garage.org/unfolding-the-6-cube, for instance, with the date stamp of May 2015 (unless that is you :-) ). – fedja May 21 '18 at 12:03
• @fedja that's a cool blog post (it is not by me)! I am glad to see that the numbers agree, which is of course an artifact of the method of finding the post... – Moritz Firsching May 21 '18 at 19:07