Decompositions of unit hypercubes and the reversion of a generalized Möbius series

Yu Hin (Gary) Au¹

¹University of Saskatchewan

The electronic journal of combinatorics, Tome 31 (2024) no. 2

Résumé

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 \geq 1} s_d(n)x^n$ satisfies the functional equation $x = \sum_{n\geq 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 $\mathbb{Z}$ 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.

Détail

DOI : 10.37236/11234

Classification : 05A15, 05A16, 05A19, 11A07, 11A25
Mots-clés : Möbius function, congruence, constant gap sequence, generating series, asymptotics