ترغب بنشر مسار تعليمي؟ اضغط هنا

Bijective recurrences concerning two Schroder triangles

78   0   0.0 ( 0 )
 نشر من قبل Shishuo Fu
 تاريخ النشر 2019
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

Let $r(n,k)$ (resp. $s(n,k)$) be the number of Schroder paths (resp. little Schroder paths) of length $2n$ with $k$ hills, and set $r(0,0)=s(0,0)=1$. We bijectively establish the following recurrence relations: begin{align*} r(n,0)&=sumlimits_{j=0}^{n-1}2^{j}r(n-1,j), r(n,k)&=r(n-1,k-1)+sumlimits_{j=k}^{n-1}2^{j-k}r(n-1,j),quad 1le kle n, s(n,0) &=sumlimits_{j=1}^{n-1}2cdot3^{j-1}s(n-1,j), s(n,k) &=s(n-1,k-1)+sumlimits_{j=k+1}^{n-1}2cdot3^{j-k-1}s(n-1,j),quad 1le kle n. end{align*} The infinite lower triangular matrices $[r(n,k)]_{n,kge 0}$ and $[s(n,k)]_{n,kge 0}$, whose row sums produce the large and little Schroder numbers respectively, are two Riordan arrays of Bell type. Hence the above recurrences can also be deduced from their $A$- and $Z$-sequences characterizations. On the other hand, it is well-known that the large Schroder numbers also enumerate separable permutations. This propelled us to reveal the connection with a lesser-known permutation statistic, called initial ascending run, whose distribution on separable permutations is shown to be given by $[r(n,k)]_{n,kge 0}$ as well.



قيم البحث

اقرأ أيضاً

In this paper, we compute the distribution of the first letter statistic on nine avoidance classes of permutations corresponding to two pairs of patterns of length four. In particular, we show that the distribution is the same for each class and is g iven by the entries of a new Schroder number triangle. This answers in the affirmative a recent conjecture of Lin and Kim. We employ a variety of techniques to prove our results, including generating trees, direct bijections and the kernel method. For the latter, we make use of in a creative way what we are trying to show in three cases to aid in solving a system of functional equations satisfied by the associated generating functions.
Given a family of sets on the plane, we say that the family is intersecting if for any two sets from the family their interiors intersect. In this paper, we study intersecting families of triangles with vertices in a given set of points. In particula r, we show that if a set $P$ of $n$ points is in convex position, then the largest intersecting family of triangles with vertices in $P$ contains at most $(frac{1}{4}+o(1))binom{n}{3}$ triangles.
Alon and Yuster proved that the number of orientations of any $n$-vertex graph in which every $K_3$ is transitively oriented is at most $2^{lfloor n^2/4rfloor}$ for $n geq 10^4$ and conjectured that the precise lower bound on $n$ should be $n geq 8$. We confirm their conjecture and, additionally, characterize the extremal families by showing that the balanced complete bipartite graph with $n$ vertices is the only $n$-vertex graph for which there are exactly $2^{lfloor n^2/4rfloor}$ such orientations.
We study Schroder paths drawn in a (m,n) rectangle, for any positive integers m and n. We get explicit enumeration formulas, closely linked to those for the corresponding (m,n)-Dyck paths. Moreover we study a Schroder version of (m,n)-parking functions, and associated (q,t)-analogs.
In this paper, firstly, by a determinant of deformed Pascals triangle, namely the normalized Hessenberg matrix determinant, to count Dyck paths, we give another combinatorial proof of the theorems which are of Catalan numbers determinant representati ons and the recurrence formula. Secondly, a determinant of normalized Toeplitz-Hessenberg matrix, whose entries are binomials, arising in power series, we derive new four properties of Pascals triangle.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا