Journal of Integer Sequences, Vol. 23 (2020), Article 20.1.4

Enumeration and Asymptotic Formulas for Rectangular Partitions of the Hypercube

Yu Hin (Gary) Au, Fatemeh Bagherzadeh, and Murray R. Bremner
Department of Mathematics and Statistics
University of Saskatchewan
Saskatoon, SK S7N 5E6


We study a two-parameter generalization of the Catalan numbers Cd,p(n), which counts the number of ways to subdivide the d-dimensional hypercube into n rectangular regions using orthogonal partitions of fixed arity p. Bremner & Dotsenko first introduced the numbers Cd,p(n) in their work on tensor products of operads, wherein 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 behavior. We give an elementary combinatorial proof of the functional equation, as well as 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.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000108 A001190 A236339 A236342.)

Received March 5 2019; revised version received November 4 2019; November 5 2019. Published in Journal of Integer Sequences, December 29 2019.

Return to Journal of Integer Sequences home page