اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the enumeration of tanglegrams and tangled chains
223
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Tanglegrams are a special class of graphs appearing in applications concerning cospeciation and coevolution in biology and computer science. They are formed by identifying the leaves of two rooted binary trees. We give an explicit formula to count the number of distinct binary rooted tanglegrams with $n$ matched vertices, along with a simple asymptotic formula and an algorithm for choosing a tanglegram uniformly at random. The enumeration formula is then extended to count the number of tangled chains of binary trees of any length. This includes a new formula for the number of binary trees with $n$ leaves. We also give a conjecture for the expected number of cherries in a large randomly chosen binary tree and an extension of this conjecture to other types of trees.
قيم البحث
اقرأ أيضاً
In this paper we are interested in the asymptotic enumeration of Cayley graphs. It has previously been shown that almost every Cayley digraph has the smallest possible automorphism group: that is, it is a digraphical regular representation (DRR). In
this paper, we approach the corresponding question for undirected Cayley graphs. The situation is complicated by the fact that there are two infinite families of groups that do not admit any graphical regular representation (GRR). The strategy for digraphs involved analysing separately the cases where the regular group $R$ has a nontrivial proper normal subgroup $N$ with the property that the automorphism group of the digraph fixes each $N$-coset setwise, and the cases where it does not. In this paper, we deal with undirected graphs in the case where the regular group has such a nontrivial proper normal subgroup.
In this paper, firstly we show that the entropy constants of the number of independent sets on certain plane lattices are the same as the entropy constants of the corresponding cylindrical and toroidal lattices. Secondly, we consider three more compl
ex lattices which can not be handled by a single transfer matrix as in the plane quadratic lattice case. By introducing the concept of transfer multiplicity, we obtain the lower and upper bounds of the entropy constants of crossed quadratic lattice, generalized aztec diamond lattice and 8-8-4 lattice.
In this paper, we consider various classes of polyiamonds that are animals residing on the triangular lattice. By careful analyses through certain layer-by-layer decompositions and cell pruning/growing arguments, we derive explicit forms for the gene
rating functions of the number of nonempty translation-invariant baryiamonds (bargraphs in the triangular lattice), column-convex polyiamonds, and convex polyiamonds with respect to their perimeter. In particular, we show that the number of (A) baryiamonds of perimeter $n$ is asymptotically $$frac{(xi+1)^2sqrt{xi^4+xi^3-2xi+1}}{2sqrt{pi n^3}}xi^{-n-2},$$ where $xi$ is a root of a certain explicit polynomial of degree 5. (B) column-convex polyiamonds of perimeter $n$ is asymptotic to $$frac{(17997809sqrt{17}+3^3cdot13cdot175463)sqrt{95sqrt{17}-119}}{2^7cdot43^2cdot 89^2sqrt{6pi n^3}}left(frac{3+sqrt{17}}{2}right)^{n-1}.$$ (C) convex polyiamonds of perimeter $n$ is asymptotic to $$frac{1280}{441sqrt{3pi n^3}}3^n.$$
Let $mge 2$ be a fixed positive integer. Suppose that $m^j leq n< m^{j+1}$ is a positive integer for some $jge 0$. Denote $b_{m}(n)$ the number of $m$-ary partitions of $n$, where each part of the partition is a power of $m$. In this paper, we show t
hat $b_m(n)$ can be represented as a $j$-fold summation by constructing a one-to-one correspondence between the $m$-ary partitions and a special class of integer sequences rely only on the base $m$ representation of $n$. It directly reduces to Andrews, Fraenkel and Sellers characterization of the values $b_{m}(mn)$ modulo $m$. Moreover, denote $c_{m}(n)$ the number of $m$-ary partitions of $n$ without gaps, wherein if $m^i$ is the largest part, then $m^k$ for each $0leq k<i$ also appears as a part. We also obtain an enumeration formula for $c_m(n)$ which leads to an alternative representation for the congruences of $c_m(mn)$ due to Andrews, Fraenkel, and Sellers.
In this paper we enumerate $k$-noncrossing tangled-diagrams. A tangled-diagram is a labeled graph whose vertices are $1,...,n$ have degree $le 2$, and are arranged in increasing order in a horizontal line. Its arcs are drawn in the upper halfplane wi
th a particular notion of crossings and nestings. Our main result is the asymptotic formula for the number of $k$-noncrossing tangled-diagrams $T_{k}(n) sim c_k n^{-((k-1)^2+(k-1)/2)} (4(k-1)^2+2(k-1)+1)^n$ for some $c_k>0$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
