Enumeration and Asymptotic Formulas for Rectangular Partitions of the Hypercube

We study a two-parameter generalization of the Catalan numbers: \(C_{d,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 \(C_{d,p}(n)\) in their work on Boardma...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-03
Main Authors: Au, Yu Hin, Bagherzadeh, Fatemeh, Bremner, Murray R
Format: Article
Language:English
Subjects:
Asymptotic properties
Enumeration
Functional equations
Homology
Hypercubes
Mathematical analysis
Partitions
Tensors
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study a two-parameter generalization of the Catalan numbers: \(C_{d,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 \(C_{d,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 \(C_{d,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.
ISSN:2331-8422