Search results for "Mathematics::Combinatorics"
showing 10 items of 81 documents
Dyck paths with a first return decomposition constrained by height
2018
International audience; We study the enumeration of Dyck paths having a first return decomposition with special properties based on a height constraint. We exhibit new restricted sets of Dyck paths counted by the Motzkin numbers, and we give a constructive bijection between these objects and Motzkin paths. As a byproduct, we provide a generating function for the number of Motzkin paths of height k with a flat (resp. with no flats) at the maximal height. (C) 2018 Elsevier B.V. All rights reserved.KeywordsKeyWords Plus:STATISTICS; STRINGS
Enumeration of Łukasiewicz paths modulo some patterns
2019
Abstract For any pattern α of length at most two, we enumerate equivalence classes of Łukasiewicz paths of length n ≥ 0 where two paths are equivalent whenever the occurrence positions of α are identical on these paths. As a byproduct, we give a constructive bijection between Motzkin paths and some equivalence classes of Łukasiewicz paths.
Equivalence classes of permutations modulo descents and left-to-right maxima
2014
Abstract In a recent paper [2], the authors provide enumerating results for equivalence classes of permutations modulo excedances. In this paper we investigate two other equivalence relations based on descents and left-to-right maxima. Enumerating results are presented for permutations, involutions, derangements, cycles and permutations avoiding one pattern of length three.
Ordering and Convex Polyominoes
2005
We introduce a partial order on pictures (matrices), denoted by ≼ that extends to two dimensions the subword ordering on words. We investigate properties of special families of discrete sets (corresponding to {0,1}-matrices) with respect to this partial order. In particular we consider the families of polyominoes and convex polyominoes and the family, recently introduced by the authors, of L-convex polyominoes. In the first part of the paper we study the closure properties of such families with respect to the order. In particular we obtain a new characterization of L-convex polyominoes: a discrete set P is a L-convex polyomino if and only if all the elements Q≼P are polyominoes. In the seco…
Reconstruction of L-convex Polyominoes.
2003
Abstract We introduce the family of L-convex polyominoes, a subset of convex polyominoes whose elements satisfy a special convexity property. We develop an algorithm that reconstructs an L-convex polyomino from the set of its maximal L-polyominoes.
A new Euler–Mahonian constructive bijection
2011
AbstractUsing generating functions, MacMahon proved in 1916 the remarkable fact that the major index has the same distribution as the inversion number for multiset permutations, and in 1968 Foata gave a constructive bijection proving MacMahon’s result. Since then, many refinements have been derived, consisting of adding new constraints or new statistics.Here we give a new simple constructive bijection between the set of permutations with a given number of inversions and those with a given major index. We introduce a new statistic, mix, related to the Lehmer code, and using our new bijection we show that the bistatistic (mix,INV) is Euler–Mahonian. Finally, we introduce the McMahon code for …
A loopless algorithm for generating the permutations of a multiset
2003
AbstractMany combinatorial structures can be constructed from simpler components. For example, a permutation can be constructed from cycles, or a Motzkin word from a Dyck word and a combination. In this paper we present a constructor for combinatorial structures, called shuffle on trajectories (defined previously in a non-combinatorial context), and we show how this constructor enables us to obtain a new loopless generating algorithm for multiset permutations from similar results for simpler objects.
A characterization of the Schur property through the disk algebra
2017
[EN] In this paper we give a new characterization of when a Banach space E has the Schur property in terms of the disk algebra. We prove that E has the Schur property if and only if A(D, E) = A(D,E-w). (C) 2016 Elsevier Inc. All rights reserved.
Finitary Representations and Images of Transitive Finitary Permutation Groups
1999
Abstract We characterize the point stabilizers and kernels of finitary permutation representations of infinite transitive groups of finitary permutations. Moreover, the number of such representations is determined.
Abelian Repetitions in Sturmian Words
2012
We investigate abelian repetitions in Sturmian words. We exploit a bijection between factors of Sturmian words and subintervals of the unitary segment that allows us to study the periods of abelian repetitions by using classical results of elementary Number Theory. We prove that in any Sturmian word the superior limit of the ratio between the maximal exponent of an abelian repetition of period $m$ and $m$ is a number $\geq\sqrt{5}$, and the equality holds for the Fibonacci infinite word. We further prove that the longest prefix of the Fibonacci infinite word that is an abelian repetition of period $F_j$, $j>1$, has length $F_j(F_{j+1}+F_{j-1} +1)-2$ if $j$ is even or $F_j(F_{j+1}+F_{j-1}…