1,721,008 research outputs found
Polyominoes determined by permutations: enumeration via bijections
No full textA permutominide is a set of cells in the plane satisfying special connectivity constraints and uniquely defined by a pair of permutations. It naturally generalizes the concept of permutomino, recently investigated by several authors and from different points of view [1, 2, 4, 6, 7]. In this paper, using bijective methods, we determine the enumeration of various classes of convex permutominides, including, parallelogram, directed convex, convex, and row convex permutominides. As a corollary we have a bijective proof for the number of convex permutominoes, which was still an open problem
Catalan structures and Catalan pairs
No full textA Catalan pair is a pair of binary relations (S,R) satisfying some axioms. These pairs are enumerated by the well-known Catalan numbers, and have been introduced in Disanto et al. (2010) [2] with the aim of giving a common language to many structures counted by Catalan numbers. Here, a simple method is given to pass from the recursive definition of a generic Catalan structure to the recursive definition of the Catalan pair on the same structure, thus giving an automatic way of interpreting Catalan structures in terms of Catalan pairs. Our method is applied to several well-known Catalan structures, focusing on the combinatorial meaning of the relations S and R in each case considere
Generation and enumeration of some classes of interval orders
No full textIn this paper we consider the class of interval orders, recently considered by several authors from both an algebraic and an enumerative point of view. According to Fishburn's Theorem (Fishburn J Math Psychol 7:144-149, 1970), these objects can be characterized as posets avoiding the poset 2 + 2. We provide a recursive method for the unique generation of interval orders of size n + 1 from those of size n, extending the technique presented by El-Zahar (1989) and then re-obtain the enumeration of this class, as done in Bousquet-Melou et al. (2010). As a consequence we provide a method for the enumeration of several subclasses of interval orders, namely AV(2 + 2, N), AV(2 + 2, 3 + 1), AV(2 + 2, N, 3 + 1). In particular, we prove that the first two classes are enumerated by the sequence of Catalan numbers, and we establish a bijection between the two classes, based on the cardinalities of the principal ideals of the posets
Lattice paths moments by cut and paste
No full textIn the coordinate plane consider those lattice paths whose step types consist of (1, 1), (1,−1), and perhaps one or more horizontal steps. For the set of such paths running from (0, 0) to (n+ 2, 0) and remaining strictly elevated above the horizontal axis elsewhere, we define a zeroth moment (cardinality), a first moment (essentially, the total area), and a second moment, each in terms of the ordinates of the lattice points traced by the paths. We then establish a bijection relating these moments to the cardinalities of sets of selected marked unrestricted paths running from (0, 0) to (n, 0). Roughly, this bijection acts by cutting each elevated path into well-defined subpaths and then
pasting the subpaths together in a specified order to form an unrestricted path
Catalan pairs: a relational-theoretic approach to Catalan numbers
No full textWe define the notion of a Catalan pair (which is a pair of binary relations (S,R) satisfying certain axioms) with the aim of giving a common language to several combinatorial interpretations of Catalan numbers. We show, in particular, that the second component R uniquely determines the pair, and we give a characterization of R in terms of forbidden configurations. We also propose some generalizations of Catalan pairs arising from some slight modifications of (some of the) axioms
A tiling system for L-convex polyominoes
No full textA polyomino is said to be L-convex if any two of its cells can be connected by a path entirely contained in the polyomino, and having at most one change of direction. In this paper, answering a problem posed by Castiglione and Vaglica [6], we prove that the class of L-convex polyominoes is tiling recognizable. To reach this goal, first we express the L-convexity constraint in terms of a set of independent properties, then we show that each class of convex polyominoes having one of these properties is tiling recognizable
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
Some applications arising from the interactions between the theory of Catalan-like numbers and the ECO method
No full textIn [FP] the ECO method and Aigner's theory of Catalan-like numbers are compared, showing that it is often possible to translate a combinatorial situation from one theory into the other by means of a standard change of basis in a suitable vector space. In the present work we emphasize the soundness of such an approach by finding some applications suggested by the above mentioned translation. More precisely, we describe a presumably new bijection between two classes of lattice paths and we give a combinatorial interpretation to an integer sequence not appearing in [S1]
- …
