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.