Enumeration and Asymptotic Formulas for Rectangular Partitions of the Hypercube
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909940526874624 |
|---|---|
| author | Au, Yu Hin Bagherzadeh, Fatemeh Bremner, Murray R. |
| author_facet | Au, Yu Hin Bagherzadeh, Fatemeh Bremner, Murray R. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1903_00813 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Enumeration and Asymptotic Formulas for Rectangular Partitions of the Hypercube Au, Yu Hin Bagherzadeh, Fatemeh Bremner, Murray R. Combinatorics K-Theory and Homology Rings and Algebras 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. |
| title | Enumeration and Asymptotic Formulas for Rectangular Partitions of the Hypercube |
| topic | Combinatorics K-Theory and Homology Rings and Algebras |
| url | https://arxiv.org/abs/1903.00813 |