Search results for "Combinatorics"
showing 10 items of 1770 documents
On the optimal approximation rate of certain stochastic integrals
2010
AbstractGiven an increasing function H:[0,1)→[0,∞) and An(H)≔infτ∈Tn(∑i=1n∫ti−1ti(ti−t)H(t)2dt)12, where Tn≔{τ=(ti)i=0n:0=t0<t1<⋯<tn=1}, we characterize the property An(H)≤cn, and give conditions for An(H)≤cnβ and An(H)≥1cnβ for β∈(0,1), both in terms of integrability properties of H. These results are applied to the approximation of stochastic integrals.
The Phagocyte Lattice of Dyck Words
2006
We introduce a new lattice structure on Dyck words. We exhibit efficient algorithms to compute meets and joins of Dyck words.
Every triangle-free induced subgraph of the triangular lattice is(5m,2m)-choosable
2014
A graph G is (a,b)-choosable if for any color list of size a associated with each vertex, one can choose a subset of b colors such that adjacent vertices are colored with disjoint color sets. This paper proves that for any integer m>=1, every finite triangle-free induced subgraph of the triangular lattice is (5m,2m)-choosable.
A Motzkin filter in the Tamari lattice
2015
The Tamari lattice of order n can be defined on the set T n of binary trees endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we restrict our attention to the subset M n of Motzkin trees. This set appears as a filter of the Tamari lattice. We prove that its diameter is 2 n - 5 and that its radius is n - 2 . Enumeration results are given for join and meet irreducible elements, minimal elements and coverings. The set M n endowed with an order relation based on a restricted rotation is then isomorphic to a ranked join-semilattice recently defined in Baril and Pallo (2014). As a consequence, we deduce an upper bound for the rotation distan…
Matchings in three Catalan lattices
2003
In this note we consider a series of lattices that are enumerated by the well-known Catalan numbers. For each of these lattices, we exhibit a matching in a constructive way.
Generating binary trees by Glivenko classes on Tamari lattices
2003
Using algebraic-theoretic results, we give an algorithm for generating binary trees within Glivenko classes in Tamari lattices. Tamari lattices are lattices of binary trees endowed by the well-known rotation transformation.
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…