Fibonacci, Motzkin, Schroder, Fuss-Catalan and other Combinatorial Structures: Universal and Embedded Bijections

arXiv1909.09296MaRDI QIDQ6325664

Author name not available (Why is that?)

Publication date: 19 September 2019

Abstract: A combinatorial structure, $mathcalF$, with counting sequence ${a_n}_{nge0}$ and ordinary generating function $G_{m}athcalF=su{m}_{nge0}{a}_n{x}^n$, is positive algebraic if $G_{m}athcalF$ satisfies a polynomial equation $G_{m}athcalF=su{m}_{k=0}^N{p}_k(x),G_{m}athcal{F}^k$ and $p_k(x)$ is a polynomial in $x$ with non-negative integer coefficients. We show that every such family is associated with a normed $mathbfn$-magma. An $mathbfn$-magma with $mathbfn=(n_1,dots,n_k)$ is a pair $mathcalM$ and $mathcalF$ where $mathcalM$ is a set of combinatorial structures and $mathcalF$ is a tuple of $n_i$-ary maps $f_i,:,mathcal{M}^{n_i}omathcalM$. A norm is a super-additive size map $||cdot||,:,mathcalMomathbbN$. If the normed $mathbfn$-magma is free then we show there exists a recursive, norm preserving, universal bijection between all positive algebraic families $mathcal{F}_i$ with the same counting sequence. A free $mathbfn$-magma is defined using a universal mapping principle. We state a theorem which provides a combinatorial method of proving if a particular $mathbfn$-magma is free. We illustrate this by defining several $mathbfn$-magmas: eleven $(1,1)$-magmas (the Fibonacci families), seventeen $(1,2)$-magmas (nine Motzkin and eight Schr"oder families) and seven $(3)$-magmas (the Fuss-Catalan families). We prove they are all free and hence obtain a universal bijection for each $mathbfn$. We also show how the $mathbfn$-magma structure manifests as an embedded bijection.

This page was built for publication: Fibonacci, Motzkin, Schroder, Fuss-Catalan and other Combinatorial Structures: Universal and Embedded Bijections

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