اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFibonacci, Motzkin, Schroder, Fuss-Catalan and other Combinatorial Structures: Universal and Embedded Bijections
60
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A combinatorial structure, $mathcal{F}$, with counting sequence ${a_n}_{nge 0}$ and ordinary generating function $G_mathcal{F}=sum_{nge0} 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 Schroder 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.
قيم البحث
اقرأ أيضاً
We introduce a new concept of permutation avoidance pattern called hatted pattern, which is a natural generalization of the barred pattern. We show the growth rate of the class of permutations avoiding a hatted pattern in comparison to barred pattern
. We prove that Dyck paths with no peak at height $p$, Dyck paths with no $ud... du$ and Motzkin paths are counted by hatted pattern avoiding permutations in $s_n(132)$ by showing explicit bijections. As a result, a new direct bijection between Motzkin paths and permutations in $s_n(132)$ without two consecutive adjacent numbers is given. These permutations are also represented on the Motzkin generating tree based on the Enumerative Combinatorial Object (ECO) method.
Three families of posets depending on a nonnegative integer parameter $m$ are introduced. The underlying sets of these posets are enumerated by the $m$-Fuss Catalan numbers. Among these, one is a generalization of Stanley lattices and another one is
a generalization of Tamari lattices. The three families of posets are related: they fit into a chain for the order extension relation and they share some properties. Two associative algebras are constructed as quotients of generalizations of the Malvenuto-Reutenauer algebra. Their products describe intervals of our analogues of Stanley lattices and Tamari lattices. In particular, one is a generalization of the Loday-Ronco algebra.
We introduce $delta$-cliffs, a generalization of permutations and increasing trees depending on a range map $delta$. We define a first lattice structure on these objects and we establish general results about its subposets. Among them, we describe su
fficient conditions to have EL-shellable posets, lattices with algorithms to compute the meet and the join of two elements, and lattices constructible by interval doubling. Some of these subposets admit natural geometric realizations. Then, we introduce three families of subposets which, for some maps $delta$, have underlying sets enumerated by the Fuss-Catalan numbers. Among these, one is a generalization of Stanley lattices and another one is a generalization of Tamari lattices. These three families of posets fit into a chain for the order extension relation and they share some properties. Finally, in the same way as the product of the Malvenuto-Reutenauer algebra forms intervals of the right weak order of permutations, we construct algebras whose products form intervals of the lattices of $delta$-cliff. We provide necessary and sufficient conditions on $delta$ to have associative, finitely presented, or free algebras. We end this work by using the previous Fuss-Catalan posets to define quotients of our algebras of $delta$-cliffs. In particular, one is a generalization of the Loday-Ronco algebra and we get new generalizations of this structure.
Squared singular values of a product of s square random Ginibre matrices are asymptotically characterized by probability distribution P_s(x), such that their moments are equal to the Fuss-Catalan numbers or order s. We find a representation of the Fu
ss--Catalan distributions P_s(x) in terms of a combination of s hypergeometric functions of the type sF_{s-1}. The explicit formula derived here is exact for an arbitrary positive integer s and for s=1 it reduces to the Marchenko--Pastur distribution. Using similar techniques, involving Mellin transform and the Meijer G-function, we find exact expressions for the Raney probability distributions, the moments of which are given by a two parameter generalization of the Fuss-Catalan numbers. These distributions can also be considered as a two parameter generalization of the Wigner semicircle law.
The Lucas sequence is a sequence of polynomials in s, and t defined recursively by {0}=0, {1}=1, and {n}=s{n-1}+t{n-2} for n >= 2. On specialization of s and t one can recover the Fibonacci numbers, the nonnegative integers, and the q-integers [n]_q.
Given a quantity which is expressed in terms of products and quotients of nonnegative integers, one obtains a Lucas analogue by replacing each factor of n in the expression with {n}. It is then natural to ask if the resulting rational function is actually a polynomial in s and t with nonnegative integer coefficients and, if so, what it counts. The first simple combinatorial interpretation for this polynomial analogue of the binomial coefficients was given by Sagan and Savage, although their model resisted being used to prove identities for these Lucasnomials or extending their ideas to other combinatorial sequences. The purpose of this paper is to give a new, even more natural model for these Lucasnomials using lattice paths which can be used to prove various equalities as well as extending to Catalan numbers and their relatives, such as those for finite Coxeter groups.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
