1,721,006 research outputs found
Some statistics on the hypercubes of Catalan permutations
No full textFor a permutation σ of length 3, we define the oriented graph Qn(σ). The graph Qn(σ) is obtained by imposing edge constraints on the classical oriented hypercube Qn, such that each path going from 0^n to 1^n in Qn(σ) bijectively encodes a permutation of size n avoiding the pattern σ. The orientation of the edges in Qn(σ) naturally induces an order relation ≼_σ among its nodes. First, we characterize ≼_σ. Next, we study several enumerative statistics on Qn(σ), including the number of intervals, the number of intervals of fixed length k, and the number of paths (or permutations) intersecting a given node
André permutations, left to right and right to left minima
No full textWe provide enumerative results concerning right-to-left minima and left-to-right
minima in Andre' permutations of the first and second kind. For both of the two kinds, the distribution of right-to-left and left-to-right minima is the same. We provide generating functions and associated asymptotic results. Our approach is based on the tree-structure of Andre' permutations
Unbalanced subtrees in binary rooted ordered and unordered trees
No full textBinary rooted trees, both in the ordered and in the un-ordered case,
are well studied structures in the field of combinatorics. The aim of this work is to study particular patterns in these classes of trees. We consider completely unbalanced subtrees, where unbalancing is measured according to the so-called Colless index. The size of the biggest unbalanced subtree becomes then a new parameter with respect to which we find several enumeration formulas
On the sub-permutations of pattern avoiding permutations
No full textThere is a deep connection between permutations and trees. Certain sub-structures of permutations, called sub-permutations, bijectively map to sub-trees of binary increasing trees. This opens a powerful tool set to study enumerative and probabilistic properties of sub-permutations and to investigate the relationships between 'local' and 'global' features using the concept of pattern avoidance. First, given a pattern mu, we study how the avoidance of mu in a permutation pi affects the presence of other patterns in the sub-permutations of pi. More precisely, considering patterns of length 3, we solve instances of the following problem: given a class of permutations K and a pattern mu, we ask for the number of permutations pi is an element of Av(n)(mu) whose sub-permutations in K satisfy certain additional constraints on their size. Second, we study the probability for a generic pattern to be contained in a random permutation pi of size n without being present in the sub-permutations of pi generated by the entry 1 <= k <= n. These theoretical results can be useful to define efficient randomized pattern-search procedures based on classical algorithms of pattern-recognition, while the general problem of pattern-search is NP-complete. (C) 2014 Elsevier B.V. All rights reserved
Asymptotic properties of the number of matching coalescent histories for caterpillar-like families of species trees
No full textCoalescent histories provide lists of species tree branches on which gene tree coalescences can take place, and their enumerative properties assist in understanding the computational complexity of calculations central in the study of gene trees and species trees. Here, we solve an enumerative problem left open by Rosenberg (IEEE/ACM Transactions on Computational Biology and Bioinformatics 10: 1253-1262, 2013) concerning the number of coalescent histories for gene trees and species trees with a matching labeled topology that belongs to a generic caterpillar-like family. By bringing a generating function approach to the study of coalescent histories, we prove that for any caterpillar-like family with seed tree t , the sequence h_n describing the number of matching coalescent histories of the n th tree of the family grows asymptotically as a constant multiple of the Catalan numbers. Thus, h_n ∼ β(t) c_n, where the asymptotic constant β(t) > 0 depends on the shape of the seed tree t. The result extends a claim demonstrated only for seed trees with at most eight taxa to arbitrary seed trees, expanding the set of cases for which detailed enumerative properties of coalescent histories can be determined. We introduce a procedure that computes from t the constant β(t) as well as the algebraic expression for the generating function of the sequence h_n
On the number of ranked species trees producing anomalous ranked gene trees
No full textAnalysis of probability distributions conditional on species trees has demonstrated the existence of anomalous ranked gene trees (ARGTs), ranked gene trees that are more probable than the ranked gene tree that accords with the ranked species tree. Here, to improve the characterization of ARGTs, we study enumerative and probabilistic properties of two classes of ranked labeled species trees, focusing on the presence or avoidance of certain subtree patterns associated with the production of ARGTs. We provide exact enumerations and asymptotic estimates for cardinalities of these sets of trees, showing that as the number of species increases without bound, the fraction of all ranked labeled species trees that are ARGT-producing approaches 1. This result extends beyond earlier existence results to provide a probabilistic claim about the frequency of ARGTs
Symmetric convex permutominoes and involutions
No full textA permutomino of size n is a polyomino determined by particular pairs of permutations of length n. In this paper we consider the class of convex permutominoes which are symmetric with respect to the diagonal x = y. We determine the number of these permutominoes according to their size and we characterize the class of permutations associated to these objects as particular involutions of length n. To do this we need to introduce a larger class of objects, called symmetric permutominides, and to study their combinatorial
propertie
Exact enumeration of cherries and pitchforks in ranked trees under the coalescent model
No full textWe consider exact enumerations and probabilistic properties of ranked trees when generated under the random coalescent process. Using a new approach, based on generating functions, we derive several statistics such as the exact probability of finding k cherries in a ranked tree of fixed size n. We then extend our method to consider also the number of pitchforks. We find a recursive formula to calculate the joint and conditional probabilities of cherries and pitchforks when the size of the tree is fixed. These results provide insights into structural properties of coalescent trees under the model of neutral evolution
Coalescent histories for lodgepole species trees
No full textCoalescent histories are combinatorial structures that describe for a given gene tree and species tree the possible lists of branches of the species tree on which the gene tree coalescences take place. Properties of the number of coalescent histories for gene trees and species trees affect a variety of probabilistic calculations in mathematical phylogenetics. Exact and asymptotic evaluations of the number of coalescent histories, however, are known only in a limited number of cases. Here we introduce a particular family of species trees, the lodgepole species trees λ_n, in which tree λ_n has m=2n+1 taxa. We determine the number of coalescent histories for the lodgepole species trees, in the case that the gene tree matches the species tree, showing that this number grows with m!! in the number of taxa m. This computation demonstrates the existence of tree families in which the growth in the number of coalescent histories is faster than exponential. Further, it provides a substantial improvement on the lower bound for the ratio of the largest number of matching coalescent histories to the smallest number of matching coalescent histories for trees with m taxa, increasing a previous bound of (sqrt{π}/32)[(5m-12)/(4m-6)]m sqrt{m} to [sqrt{m-1}/(4sqrt{e})]^m. We discuss the implications of our enumerative results for phylogenetic computations
On the Number of Non-equivalent Ancestral Configurations for Matching Gene Trees and Species Trees
No full textAn ancestral configuration is one of the combinatorially distinct sets of gene lineages that, for a given gene tree, can reach a given node of a specified species tree. Ancestral configurations have appeared in recursive algebraic computations of the conditional probability that a gene tree topology is produced under the multispecies coalescent model for a given species tree. For matching gene trees and species trees, we study the number of ancestral configurations, considered up to an equivalence relation introduced by Wu (Evolution 66:763â775, 2012) to reduce the complexity of the recursive probability computation. We examine the largest number of non-equivalent ancestral configurations possible for a given tree size n. Whereas the smallest number of non-equivalent ancestral configurations increases polynomially with n, we show that the largest number increases with (Formula presented.), where k is a constant that satisfies (Formula presented.). Under a uniform distribution on the set of binary labeled trees with a given size n, the mean number of non-equivalent ancestral configurations grows exponentially with n. The results refine an earlier analysis of the number of ancestral configurations considered without applying the equivalence relation, showing that use of the equivalence relation does not alter the exponential nature of the increase with tree size
- …
