1,721,056 research outputs found
Production matrices and Riordan arrays
No full textWe translate the concept of succession rule and the ECO method into matrix notation, introducing the concept of production matrix. This allows us to combine our method with other enumeration techniques using matrices, such as the method of Riordan matrices. Finally we treat the case of rational production matrices, i.e., those leading to rational generating functions
A Generating Tree for Permutations Avoiding the Pattern 122+3
No full textIn this paper we study the family of permutations avoiding the pattern 122+3 (trivially equivalent to those avoiding 1 23 4), which extend the popular 123-avoiding permutations. In particular we provide an algorithmic description of a generating tree for these permutations, that is a way to build every object of a given size n + 1 in a unique way by performing local modifications on an object of size n. Our algorithm leads to a direct bijection between 1 23 4-avoiding permutations and valley-marked Dyck paths. It extends a known bijection between 123-avoiding permutations and Dyck paths, and makes explicit the connection between these objects that was earlier obtained by Callan through a series of non-trivial bijective steps. In particular our construction is simple enough to allow for efficient exhaustive generation
A partial order structure on interval orders
Full text linkWe introduce a partial order structure on the set of interval orders of a given size, and prove that such a structure is in fact a lattice. We also provide a way to compute meet and join inside this lattice. Finally, we show that, if we restrict to series parallel interval order, what we obtain is the classical Tamari poset
On directed-convex polyominoes in a rectangle
No full textWe provide bijective proofs for the number of directed-convex polyominoes having a fixed number of rows and columns in two ways: by means of the ECO method, and through a correspondence with the set of 2-colored Grand-Motzkin paths
Geometric properties of matrices induced by pattern avoidance
Full text linkThe notion of submatrix avoidance in polyominoes has recently been introduced in [2] with the aim of extending most of the concepts and properties concerning pattern avoiding permutations to the setting of polyominoes. In this paper we use submatrix avoidance to describe families of polyominoes which, in the literature, are usually defined by means of the geometric constraints of convexity, k-convexity, and directedness. To reach this goal, we provide an extension of the notion of pattern in a polyomino, by introducing generalized polyomino patterns. In the second part of the paper, we tackle the same problem in the context of discrete sets, which can be naturally regarded as binary matrices. In this case, we consider two types of geometric constraints: convexity and directedness, and we study how these constraints can be imposed on matrices by using submatrix avoidance
THE COMBINATORICS OF CONVEX PERMUTOMINOES
No full textA permutomino of size n is a polyomino determined by particular pairs (1, 2) of permutations of n. Here we study
various classes of convex permutominoes. We determine some combinatorial properties and, in particular, the characterization for the permutations defining convex, directed-convex, and parallelogram permutominoes.
Using standard combinatorial techniques we provide a recursive decomposition for permutations associated with convex permutominoes, and we derive a closed formula
for the number of these permutations of size n
Permutation classes and polyomino classes with excluded submatrices
No full textThis article introduces an analogue of permutation classes in the context of polyominoes. For both permutation classes and polyomino classes, we present an original way of characterizing them by avoidance constraints (namely, with excluded submatrices) and we discuss how canonical such a description by submatrix-avoidance can be. We provide numerous examples of permutation and polyomino classes which may be defined and studied from the submatrix-avoidance point of view, and conclude with various directions for future research on this topic
- …
