Enumeration and Asymptotic Formulas for Rectangular Partitions of the Hypercube

We study a two-parameter generalization of the Catalan numbers: Cd,p(n) is the number of ways to subdivide the d-dimensional hypercube into n rectangular blocks using orthogonal partitions of fixed arity p. Bremner & Dotsenko introduced Cd,p(n) in their work on Boardman--Vogt tensor products of operads; they used homological algebra to prove a recursive formula and a functional equation. We express Cd,p(n) as simple finite sums, and determine their growth rate and asymptotic behaviour. We give an elementary proof of the functional equation, using a bijection between hypercube decompositions and a family of full p-ary trees. Our results generalize the well-known correspondence between Catalan numbers and full binary trees.