{
  "id": "1909.09296",
  "version": "v1",
  "published": "2019-09-20T02:22:33.000Z",
  "updated": "2019-09-20T02:22:33.000Z",
  "title": "Fibonacci, Motzkin, Schroder, Fuss-Catalan and other Combinatorial Structures: Universal and Embedded Bijections",
  "authors": [
    "R. Brak",
    "N. Mahony"
  ],
  "categories": [
    "math.CO",
    "math.RA"
  ],
  "abstract": "A combinatorial structure, $\\mathcal{F}$, with counting sequence $\\{a_n\\}_{n\\ge 0}$ and ordinary generating function $G_\\mathcal{F}=\\sum_{n\\ge0} a_n x^n$, is positive algebraic if $G_\\mathcal{F}$ satisfies a polynomial equation $G_\\mathcal{F}=\\sum_{k=0}^N p_k(x)\\,G_\\mathcal{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 $\\mathbf{n}$-magma. An $\\mathbf{n}$-magma with $\\mathbf{n}=(n_1,\\dots, n_k)$ is a pair $\\mathcal{M}$ and $\\mathcal{F}$ where $\\mathcal{M}$ is a set of combinatorial structures and $\\mathcal{F}$ is a tuple of $n_i$-ary maps $f_i\\,:\\,\\mathcal{M}^{n_i}\\to \\mathcal{M}$. A norm is a super-additive size map $||\\cdot||\\,:\\, \\mathcal{M}\\to \\mathbb{N} $. If the normed $\\mathbf{n}$-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 $\\mathbf{n}$-magma is defined using a universal mapping principle. We state a theorem which provides a combinatorial method of proving if a particular $\\mathbf{n}$-magma is free. We illustrate this by defining several $\\mathbf{n}$-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 $\\mathbf{n}$. We also show how the $\\mathbf{n}$-magma structure manifests as an embedded bijection.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-09-20T02:22:33.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "combinatorial structure",
      "embedded bijection",
      "fuss-catalan",
      "universal bijection",
      "counting sequence"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}