##
**
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

Canada

**Abstract:**

We study a two-parameter generalization of the
Catalan numbers *C*_{d,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 *C*_{d,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 *C*_{d,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**