Enumeration and asymptotic formulas for rectangular partitions of the hypercube

zbMATH Open1431.05004arXiv1903.00813MaRDI QIDQ5212151FDOQ5212151

Yu Hin Au, Murray R. Bremner, Fatemeh Bagherzadeh

Publication date: 27 January 2020

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1903.00813

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Catalan numbers, their generalization, and their uses
• Restricted partitions and generalized Catalan numbers
• Generalized Catalan numbers from hypergraphs
• A generalization of the Catalan numbers
• ON THE (n, k)-TH CATALAN NUMBERS

zbMATH Keywords

Catalan numbergenerating functionLagrange inversionenumeration problemnonassociative algebrahigher categoryinterchange lawBoardman-Vogt tensor productalgebraic operadhigher-dimensional analoghypercube decomposition

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Combinatorial identities, bijective combinatorics (05A19) Other (n)-ary compositions ((n ge 3)) (17A42) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Free nonassociative algebras (17A50)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Analytic combinatorics
• The geometry of iterated loop spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algebraic Operads
• Introductory notes on Richard Thompson's groups
• Nonabelian algebraic topology. Filtered spaces, crossed complexes, cubical homotopy groupoids. With contributions by Christopher D. Wensley and Sergei V. Soloviev
• Homotopy invariant algebraic structures on topological spaces
• Operads and algebraic combinatorics of trees
• Permutation of elements in double semigroups
• Title not available (Why is that?)
• On the enumeration of tanglegrams and tangled chains
• Cut equivalence of \(d\)-dimensional guillotine partitions
• Title not available (Why is that?)
• The number of guillotine partitions in \(d\) dimensions
• Note on commutativity in double semigroups and two-fold monoidal categories
• Gröbner bases for operads
• Higher dimensional Thompson groups.
• Catalan Numbers
• Inversion of integral series enumerating planar trees
• Generalized Catalan Numbers and the Enumeration of Planar Embeddings
• Higher-dimensional algebra. III: \(n\)-categories and the algebra of opetopes
• Title not available (Why is that?)
• Asymptotic Methods in Enumeration
• Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations
• A bijection between permutations and floorplans, and its applications
• Separable \(d\)-permutations and guillotine partitions
• On the number of tilings of a square by rectangles
• Generic rectangulations
• The Hopf algebra of diagonal rectangulations.
• Multivariate Fuss-Catalan numbers
• On generating series of coloured planar trees
• Algebras of higher operads as enriched categories
• Comparing operadic theories of \(n\)-category
• Algebraic operads. An algorithmic companion
• Title not available (Why is that?)
• A simple optimal binary representation of mosaic floorplans and Baxter permutations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Commutativity in double interchange semigroups
• Lagrange inversion
• Nonsymmetric operads in combinatorics
• Generalizing Bailey's generalization of the Catalan numbers
• Non-Associate Powers and a Functional Equation
• Boardman–Vogt tensor products of absolutely free operads
• An asymptotic expansion for the Wedderburn–Etherington sequence

Cited In (2)

• On the number of hypercubic bipartitions of an integer
• Asymptotics of the partition of the cube into Weyl simplices and an encoding of a Bernoulli scheme

Uses Software

• OEIS

This page was built for publication: Enumeration and asymptotic formulas for rectangular partitions of the hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212151)