Pattern avoidance in “flattened” partitions

To flatten a set partition (with apologies to Mathematica^®) means to form a permutation by erasing the dividers between its blocks. Of course, the result depends on how the blocks are listed. For the usual listing—increasing entries in each block and blocks arranged in increasing order of their first entries—we count the partitions of [n] whose flattening avoids a single 3-letter pattern. Five counting sequences arise: a null sequence, the powers of 2, the Fibonacci numbers, the Catalan numbers, and the binomial transform of the Catalan numbers.     

Symmetries in trees and parking functions

We investigate a particular symmetry in labeled trees first discovered by Gessel, which can be stated as follows: In the set of rooted labeled trees on n+1 vertices rooted at the smallest vertex, the number of trees with a descents and b+1 leaves equals the number of trees with b descents and a+1 leaves. We present two new ways to prove the symmetry resulting from decompositions of trees, which lead to three different bijections from trees to trees in which leaves and descents are swapped. We also interpret the symmetry in terms of parking functions: the number of parking functions on [n] with a descents and b unfavorable spaces (defined in this paper) equals the number of parking functions on [n] with b descents and a unfavorable spaces. We conclude with a generalization of these results to binary trees.RésuméNous étudions une symétrie particulière dans les arbres étiquetés, découverte par Gessel, qu'on peut énoncer comme suit: Dans l'ensemble des arbres étiquetés pointés avec n+1 sommets, pointés au sommet minimum, le nombre d'arbres avec a descentes et b+1 feuilles égale le nombre d'arbres avec b descentes et a+1 feuilles. Nous présentons deux nouvelles démonstrations de la symétrie, qui resultent des décompositions des arbres; à partir des décompositions, nous obtenons trois bijections des arbres sur les arbres qui échangent les feuilles et les descentes. De plus, nous interprétons la symétrie en termes des “fonctions de stationnement” (parking functions): le nombre des fonctions de stationnement avec a descentes et b positions défavorables (définies dans cette article) égale le nombre de fonctions de stationnement avec b positions défavorable et a descentes. Nous donnons aussi une généralisation de ces resultats aux arbres binaires.     

Pattern avoidance and Boolean elements in the Bruhat order on involutions

We show that the principal order ideal of an element w in the Bruhat order on involutions in a symmetric group is a Boolean lattice if and only if w avoids the patterns 4321, 45312 and 456123. Similar criteria for signed permutations are also stated. Involutions with this property are enumerated with respect to natural statistics. In this context, a bijective correspondence with certain Motzkin paths is demonstrated. This article is largely based on results from the second author’s M.Sc. thesis [15].     

On the allocation of binary trees to secondary storage

Two paging techniques proposed by Muntz and Uzgalis to store a binary tree in secondary storage are considered. The first method (sequential allocation) is the basic allocation technique and here an exact formula is given, to be considered as a touchstone for every other method. Then a modification to the second method (grouped allocation) is proposed which gains control on storage utilization. This allows the structure to maintain both a high loading factor and a low retrieving time.     

Chemical trees enumeration algorithms

In the chemical community the need for representing chemical structures within a given family and of efficiently enumerating these structures suggested the use of computers and the implementation of fast enumeration algorithms. This paper considers the isomeric acyclic structures focusing on the enumeration of the alkane molecular family. For this family, Trinajsti et al. (1991) devised an enumeration algorithm which is the most widely known and utilized nowadays. Kvasnika and Pospichal (1991) have proposed an algorithmic scheme which, from the computational complexity point of view, can prove to be more efficient than the Trinajsti one, nevertheless, this algorithm, to the best of our knowledge, has never been implemented. Indeed an efficient implementation requires the introduction of non trivial data structures and other computational tricks. The main contribution of this paper consists of the definition of the implementation details of Kvasnika-Pospichals algorithm, in a comparison of Trinajstis, Kvasnika-Pospichals and two new algorithms, proposed here, in terms of both computational complexity analysis and running times.AMS classification: 05A15, 05C05, 05C30, 05C90Part of this work has been developed during a visit of the first two authors at the EPFL of Lausanne     

Pattern distributions in Dyck paths with a first return decomposition constrained by height

We provide generating functions for the popularity and the distribution of patterns of length at most three over the set of Dyck paths having a first return decomposition constrained by height.     

Generalized Waiting Time Problems Associated with Pattern in Polya's Urn Scheme

Let X ₁, X ₂, ... be a sequence obtained by Polya's urn scheme. We consider a waiting time problem for the first occurrence of a pattern in the sequence X ₁, X ₂, ... , which is generalized by a notion score. The main part of our results is derived by the method of generalized probability generating functions. In Polya's urn scheme, the system of equations is composed of the infinite conditional probability generating functions, which can not be solved. Then, we present a new methodology to obtain the truncated probability generating function in a series up to an arbitrary order from the system of infinite equations. Numerical examples are also given in order to illustrate the feasibility of our results. Our results in this paper are not only new but also a first attempt to treat the system of infinite equations.     

Limit laws for local counters in random binary search trees

Limit laws for several quantities in random binary search trees that are related to the local shape of a tree around each node can be obtained very simply by applying central limit theorems for w-dependent random variables. Examples include: the number of leaves (L_n), the number of nodes with k descendants (k fixed), the number of nodes with no left child, the number of nodes with k left descendants. Some of these results can also be obtained via the theory of urn models, but the present method seems easier to apply.     

Approximate inference in Bayesian networks using binary probability trees

The present paper introduces a new kind of representation for the potentials in a Bayesian network: Binary Probability Trees. They enable the representation of context-specific independences in more detail than probability trees. This enhanced capability leads to more efficient inference algorithms for some types of Bayesian networks. This paper explains the procedure for building a binary probability tree from a given potential, which is similar to the one employed for building standard probability trees. It also offers a way of pruning a binary tree in order to reduce its size. This allows us to obtain exact or approximate results in inference depending on an input threshold. This paper also provides detailed algorithms for performing the basic operations on potentials (restriction, combination and marginalization) directly to binary trees. Finally, some experiments are described where binary trees are used with the variable elimination algorithm to compare the performance with that obtained for standard probability trees.     

Generating 2-Gray codes for ballot sequences in constant amortized time

We present a simple algorithm that generates a cyclic 2-Gray code for ballot sequences. The algorithm generates each ballot sequence in constant amortized time using a linear amount of space. This is the first known cyclic 2-Gray code for ballot sequences that achieves this time bound. In addition, the algorithm can be easily modified to output ballot sequences in binary reflected Gray code order in constant amortized time per string using a linear amount of space.     

Planar binary trees and perturbative calculus of observables in classical field theory

We study the Klein–Gordon equation coupled with an interaction term (□+m²)φ+λφ^p=0. In the linear case (λ=0) a kind of generalized Noether's theorem gives us a conserved quantity. The purpose of this paper is to find an analogue of this conserved quantity in the interacting case. We will see that we can do this perturbatively, and we define explicitly a conserved quantity, using a perturbative expansion based on Planar Trees and a kind of Feynman rule. Only the case p=2 is treated but our approach can be generalized to any ^p-theory.     

Propagating belief functions in qualitative Markov trees

This article is concerned with the computational aspects of combining evidence within the theory of belief functions. It shows that by taking advantage of logical or categorical relations among the questions we consider, we can sometimes avoid the computational complexity associated with brute-force application of Dempster's rule.The mathematical setting for this article is the lattice of partitions of a fixed overall frame of discernment. Different questions are represented by different partitions of this frame, and the categorical relations among these questions are represented by relations of qualitative conditional independence or dependence among the partitions. Qualitative conditional independence is a categorical rather than a probabilistic concept, but it is analogous to conditional independence for random variables.We show that efficient implementation of Dempster's rule is possible if the questions or partitions for which we have evidence are arranged in a qualitative Markov tree—a tree in which separations indicate relations of qualitative conditional independence. In this case, Dempster's rule can be implemented by propagating belief functions through the tree.     

Crowding with nearest neighbors replacement for multiple species niching and building blocks preservation in binary multimodal functions optimization

This paper introduces a novel niching scheme called the q-nearest neighbors replacement (q-NNR) method in the framework of the steady-state GAs (SSGAs) for solving binary multimodal optimization problems. A detailed comparison of the main niching approaches are presented first. The niching paradigm and difference of the selection-recombination genetic algorithms (GAs) and the recombination-replacement SSGAs are discussed. Then the q-NNR is developed by adopting special replacement policies based on the SSGAs; a Boltzmann scheme for dynamically sizing the nearest neighbors set is designed to achieve a speed-up and control the proportion of individuals adapted to different niches. Finally, experiments are carried out on a set of test functions characterized by deception, epistasis, symmetry and multimodality. The results are satisfactory and illustrate the effectivity and efficiency of the proposed niching method.     

Chains in the Bruhat order

We study a family of polynomials whose values express degrees of Schubert varieties in the generalized complex flag manifold G/B. The polynomials are given by weighted sums over saturated chains in the Bruhat order. We derive several explicit formulas for these polynomials, and investigate their relations with Schubert polynomials, harmonic polynomials, Demazure characters, and generalized Littlewood-Richardson coefficients. In the second half of the paper, we study the classical flag manifold and discuss related combinatorial objects: flagged Schur polynomials, 312-avoiding permutations, generalized Gelfand-Tsetlin polytopes, the inverse Schubert-Kostka matrix, parking functions, and binary trees. A.P. was supported in part by National Science Foundation grant DMS-0201494 and by Alfred P. Sloan Foundation research fellowship. R.S. was supported in part by National Science Foundation grant DMS-9988459.