Enumeration and asymptotic formulas for rectangular partitions of the hypercube

MaRDI QIDQ5212151zbMATH OpenFDO

Authors Fatemeh Bagherzadeh, Murray R. Bremner, Yu Hin Au

Publication date 27 January 2020

Full work available at URL https://arxiv.org/abs/1903.00813, https://cs.uwaterloo.ca/journals/JIS/VOL23/Au/au3.html

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

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)

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.

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

Cites work

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

Cited in

(3)

• Decompositions of Unit Hypercubes and the Reversion of a Generalized M\"obius Series
• 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

Describes a project that uses

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)