Decompositions of Unit Hypercubes and the Reversion of a Generalized Möbius Series

Abstract

Let $s_d(n)$ be the number of distinct decompositions of the $d$-dimensional hypercube with $n$ rectangular regions that can be obtained via a sequence of splitting operations. We prove that the generating series $y={\sum }_{n\ge 1}{s}_d(n)x^n$ satisfies the functional equation $x={\sum }_{n\ge 1}{\mu }_d(n)y^n$, where ${\mu }_d(n)$ is the $d$-fold Dirichlet convolution of the Möbius function. This generalizes a recent result by Goulden et al., and shows that $s_1(n)$ also gives the number of natural exact covering systems of $\mZ$ with $n$ residual classes. We also prove an asymptotic formula for $s_d(n)$ and describe a bijection between $1$-dimensional decompositions and natural exact covering systems.