On edge-weighted recursive trees and inversions in random permutations

We introduce random recursive trees, where deterministically weights are attached to the edges according to the labeling of the trees. We will give a bijection between recursive trees and permutations, which relates the arising edge-weights in recursive trees with inversions of the corresponding permutations. Using this bijection we obtain exact and limiting distribution results for the number of permutations of size n, where exactly m elements have j inversions. Furthermore we analyze the distribution of the sum of labels of the elements, which have exactly j inversions, where we can identify Dickman's infinitely divisible distribution as the limit law. Moreover we give a distributional analysis of weighted depths and weighted distances in edge-weighted recursive trees.     

Two theorems on graceful trees

Let T be a tree on n vertices which are labelled by the integers in N = {1,2,…,n} such that each vertex of T is associated with a distinct number in N. The weight of an edge is defined to be the absolute value of the difference between the two numbers labelled at its end vertices. If the weights of all edges of T are distinct, we call T a graceful tree. In this note, two methods for constructing bigger graceful trees from a given one and a given pair of graceful trees are provided.     

The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees

A unicellular map is a map which has only one face. We give a bijection between a dominant subset of rooted unicellular maps of given genus and a set of rooted plane trees with distinguished vertices. The bijection applies as well to the case of labelled unicellular maps, which are related to all rooted maps by Marcus and Schaeffer’s bijection. This gives an immediate derivation of the asymptotic number of unicellular maps of given genus, and a simple bijective proof of a formula of Lehman and Walsh on the number of triangulations with one vertex. From the labelled case, we deduce an expression of the asymptotic number of maps of genus g with n edges involving the ISE random measure, and an explicit characterization of the limiting profile and radius of random bipartite quadrangulations of genus g in terms of the ISE.     

On the average number of nodes in a subtree of a tree

For any tree T (labelled, not rooted) of order n, it will be shown that the average number of nodes in a subtree of T is at least $\text{(n + 2)}\text{3}$, with this minimum achieved iff T is a path. For T rooted, the average number of nodes in a subtree containing the root is at least $\text{(n + 1)}\text{2}$ and always exceeds the average over all unrooted subtrees. For the maximum mean, examples show that there are arbitrarily large trees in which the average subtree contains essentially all of the nodes. The mean subtree order as a function on trees is also shown to be monotone with respect to inclusion.     

Counting labelled trees with given indegree sequence

For a labelled tree on the vertex set [n]:={1,2,…,n}, define the direction of each edge ij to be i→j if i<j. The indegree sequence of T can be considered as a partition λ?n−1. The enumeration of trees with a given indegree sequence arises in counting secant planes of curves in projective spaces. Recently Ethan Cotterill conjectured a formula for the number of trees on [n] with indegree sequence corresponding to a partition λ. In this paper we give two proofs of Cotterill's conjecture: one is “semi-combinatorial” based on induction, the other is a bijective proof.     

Two matrix inversions associated with the Hagen-Rothe formula, their q-analogues and applications

By means of the Hagen-Rothe formula, we establish two new matrix inversions with four parameters. These new inversions uniformize Riordan's inverse relations of Abel-, Chebyshev-, and Legendre-type as well as Gould's inversions based on Vandermonde-type convolutions. Some related q-series inverse relations using the known q-analogues of the Hagen-Rothe formula are established. A Λ-extension of Gould's g-inverse, a novel expression for all Chebyshev-type inversions, and several new summation and transformation formulas of series are presented as applications.     

On the average shape of monotonically labelled tree structures

Let $\text{B}$_k denote one of the families of binary trees, t-aray trees (t> 2) or ordered trees with nodes labelled monotonically by elements of {1 < 2 < ? < k}. The average height of the j-th leaf of the trees of $\text{B}$_k with exactly n nodes is shown to converge to a finite limit (depending on k and j) for n → ∞. The limit is determined explicitly for small values of k and its asymptotic behaviour in j and k is investigated. Some recent results on the average shape of rooted tree structures appear as special cases.     

The Length of the Longest Increasing Subsequence of a Random Mallows Permutation

The Mallows measure on the symmetric group S _n is the probability measure such that each permutation has probability proportional to q raised to the power of the number of inversions, where q is a positive parameter and the number of inversions of π is equal to the number of pairs i<j such that π _i >π _j . We prove a weak law of large numbers for the length of the longest increasing subsequence for Mallows distributed random permutations, in the limit that n→∞ and q→1 in such a way that n(1?q) has a limit in R.     

Un analogue du monoı̈de plaxique pour les arbres binaires de rechercheAn analogue of the plactic monoid for binary search trees

We introduce a monoid structure on a certain set of labelled binary trees, by a process similar to the construction of the plactic monoid. This leads to a new interpretation of the algebra of planar binary trees of Loday–Ronco. To cite this article: F. Hivert et al., C. R. Acad. Sci. Paris, Ser. I 335 (2002) 577–580.     

Signatures of Strings

The parity of a permutation π can be defined as the parity of the number of inversions in π. The signature ε(π) of π is an encoding of the parity in a multiplicative group of order 2: ε(π) = (?1)^inv(π). It is also well known that half of the permutations of a finite set are even and half are odd. In this paper, we explore the natural notion of parity for larger moduli; that is, we define the m-signature of a permutation π to be the number of inversions of π, reduced modulo m. Unlike with the 2-signatures of permutations of sets, the m-signatures of the permutations of a multiset are not typically equi-distributed among the modulo m residue classes, though the distribution is close to uniform. We present a recursive method of calculating the distribution of m-signatures of permutations of a multiset, develop properties of this distribution, and present sufficient conditions for the distribution to be uniform.     

Counting Special Families of Labelled Trees

A labelled tree rooted at its least labelled vertex is Least-Child-Being-Monk if it has the property that the least labelled child of 0 is a leaf. One of our main results is that the number of Least-Child-Being-Monk trees labelled on {0, 1, 2,... ,n + 1} is equal to nⁿ. More generally, let be the set of labelled trees on {0,1,2,..., n + 1}, such that the total number of descendants of the least labelled child of 0 is p. We prove that the cardinality of is equal to Furthermore, a labelled tree rooted at its least labelled vertex is Hereditarily-Least-Single if it has the property that every least child in this tree is a leaf. Let the number of Hereditarily-Least-Single trees with n vertices be h_n. We find a functional equation for the generating function of h(n) and derive a recurrence that will quickly compute h(n). Received November 13, 2004     

On cographic regular matroids

The presentation of alternating permutatioas via labelled binary trees is used to define polynomials H_2n?1(x) as enumerating polynomials for the height of peaks in alternating permutations of length 2n?1. A divisibility property of the coefficients of these polynomials is proved, which generalizes and explains combinatirially a well-known property of the tangent numbers. Furthermore, a version of the exponential generating function for the H_2n?1(x) is given, leading to a new combinatorial interpretation of Dumont's modified Ghandi-polynomials.     

The Estrada index of trees

The Estrada index of a graph G is defined as , where λ₁,λ₂,…,λ_n are the eigenvalues of its adjacency matrix. We determine the unique tree with maximum Estrada index among the set of trees with given number of pendant vertices. As applications, we determine trees with maximum Estrada index among the set of trees with given matching number, independence number, and domination number, respectively. Finally, we give a proof of a conjecture in [J. Li, X. Li, L. Wang, The minimal Estrada index of trees with two maximum degree vertices, MATCH Commun. Math. Comput. Chem. 64 (2010) 799-810] on trees with minimum Estrada index among the set of trees with two adjacent vertices of maximum degree.     

Graphs, partitions and Fibonacci numbers

The Fibonacci number of a graph is the number of independent vertex subsets. In this paper, we investigate trees with large Fibonacci number. In particular, we show that all trees with n edges and Fibonacci number >2^n-1+5 have diameter ?4 and determine the order of these trees with respect to their Fibonacci numbers. Furthermore, it is shown that the average Fibonacci number of a star-like tree (i.e. diameter ?4) is asymptotically for constants A,B as n→∞. This is proved by using a natural correspondence between partitions of integers and star-like trees.     

The height of multiple edge plane trees

Multi-edge trees as introduced in a recent paper of Dziemiańczuk are plane trees where multiple edges are allowed. We first show that d-ary multi-edge trees where the out-degrees are bounded by d are in bijection with classical d-ary trees. This allows us to analyse parameters such as the height. The main part of this paper is concerned with multi-edge trees counted by their number of edges. The distribution of the number of vertices as well as the height are analysed asymptotically.     

A greedy algorithm for multicut and integral multiflow in rooted trees

We present an O(min(Kn,n²)) algorithm to solve the maximum integral multiflow and minimum multicut problems in rooted trees, where K is the number of commodities and n is the number of vertices. These problems are NP-hard in undirected trees but polynomial in directed trees. In the algorithm we propose, we first use a greedy procedure to build the multiflow then we use duality properties to obtain the multicut and prove the optimality.     

Trees with extremal numbers of maximal independent sets including the set of leaves

A subset S of vertices of a graph G is independent if no two vertices in S are adjacent. In this paper we study maximal (with respect to set inclusion) independent sets in trees including the set of leaves. In particular the smallest and the largest number of these sets among n-vertex trees are determined characterizing corresponding trees. We define a local augmentation of trees that preserves the number of maximal independent sets including the set of leaves.     

On the number of trees in a random forest

The analytic methods of Pólya, as reported in [1, 6] are used to determine the asymptotic behavior of the expected number of (unlabeled) trees in a random forest of order p. Our results can be expressed in terms of η = .338321856899208 …, the radius of convergence of t(x) which is the ordinary generating function for trees. We have found that the expected number of trees in a random forest approaches 1 + Σ_k=1^∞t(η^k) = 1.755510 … and the form of this result is the same     

More on complementary trees

It is shown that a graph with no multiple edges on n vertices, n ≥ 5, with 2(n?2) arcs labelled 1,…,n?1 and 1′,…,n?1′ having at least one spanning tree whose arcs include no pair (j,j?), has at least six of them. This is a result of Rothblum. It is also shown that if the graph has only one multiple edge and that is a double edge, and n ≥ 4, then it has at least four such spanning trees.     

Ordering of trees with fixed matching number by the Laplacian coefficients

Let G be a simple undirected graph with the characteristic polynomial of its Laplacian matrix L(G), . Aleksandar Ili? [A. Ili?, Trees with minimal Laplacian coefficients, Comput. Math. Appl. 59 (2010) 2776-2783] identified n-vertex trees with given matching number q which simultaneously minimize all Laplacian coefficients. In this paper, we give another proof of this result. Generalizing the approach in the above paper, we determine n-vertex trees with given matching number q which have the second minimal Laplacian coefficients. We also identify the n-vertex trees with a perfect matching having the largest and the second largest Laplacian coefficients, respectively. Extremal values on some indices, such as Wiener index, modified hyper-Wiener index, Laplacian-like energy, incidence energy, of n-vertex trees with matching number q are obtained in this paper.