International audience

The study of the compressibility of repetitive sequences is an issue that is attracting great interest. We consider purely morphic words, which are highly repetitive sequences generated by iterating a morphism$\varphi$that admits a fixed point (denoted by$\varphi^{\infty}(a)$) starting from a given character$a$belonging to the finite alphabet$A$, i.e.$\varphi^{\infty}(a)=\lim\nolimits_{i\rightarrow\infty}\varphi^{i}(a)$. Such morphisms are called prolongable on$a$. Here we focus on the compressibility via the Burrows-Wheeler Transform ($BWT$) of infinite families of finite sequences generated by morphisms. In particular, denoted by$r(w)$the number of equal-letter runs of a word$w$, we provide new upper bounds on$r(\mathsf{bwt} (\varphi^{i}(a)))$, i.e. the number of equal-letter runs produced when$BWT$is applied on$\varphi^{i}(a)$. Such bounds depend on the factor complexity$f_{x}(n)$of the infinite word$x=\varphi^{\infty}(a)$, that counts, for each$n\geq 0$, the number of distinct factors of$x$having length$n$.

In this paper we study the family of permutations avoiding the pattern 122+3 (trivially equivalent to those avoiding 123⎵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 ev ery 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 123⎵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.

In this paper, we enumerate two families of pattern-avoiding permutations: those avoiding the vincular pattern $2\underbracket{41}3$, which we call semi-Baxter permutations, and those avoiding the vincular patterns $2\underbracket{41}3$, $3\underbracket{14}2,$ and $3\underbracket{41}2$, which we call strong-Baxter permutations. We call semi-Baxter numbers and strong-Baxter numbers the associated enumeration sequences. We prove that the semi-Baxter numbers enumerate in addition plane permutations (avoiding $2\underbracket{14}3$). The problem of counting these permutations was open and has given rise to several conjectures, which we also prove in this paper. For each family (that of semi-Baxter---or, equivalently, plane---and that of strong-Baxter permutations), we describe a generating tree, which translates into a functional equation for the generating function. For semi-Baxter permutations, it is solved using (a variant of) the kernel method: this gives an expression for the generating function while also proving its D-finiteness. From the obtained generating function, we derive closed formulas for the semi-Baxter numbers, a recurrence that they satisfy, as well as their asymptotic behavior. For strong-Baxter permutations, we show that their generating function is (a slight modification of) that of a family of walks in the quarter plane, which is known to be non--D-finite.

This 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.

Starting from a Theorem by Hall, we define the identity transform of a permutation π as C(π) = (0 + π(0), 1 + π(1), ..., (n − 1) + π(n − 1)), and we define the set Cn = {(C(π) : π ∈ Sn}, where Sn is the set of permutations of the elements of the cyclic group ℤn. In the first part of this paper we s tudy the set Cn: we show some closure properties of this set, and then provide some of its combinatorial and algebraic characterizations and connections with other combinatorial structures. In the second part of the paper, we use some of the combinatorial properties we have determined to provide a different algorithm for the proof of Hall’s Theorem.

In this paper we consider the class of column-convex permutominoes, i.e. column-convex polyominoes defined by a pair of permutations (π 1 , π 2 ). First, using a geometric construction, we prove that for every permutation π there is at least one column-convex permutomino P such that π 1 (P) = π or π 2 (P) = π. In the second part of the paper, we show how, for any given permutation π, it is possible to define a set of logical implications on the points of π, and prove that there exists a column-convex permutomino P such that π 1 (P) = π if and only if is satisfiable. This property can be then used to give a characterization of the set of column-convex permutominoes P such that π 1 (P) = π.

The 7th International Conference on Lattice Path Combinatorics and Applications was held in Sienna from 4-7 July, 2010, and was organized by the Dipartimento di Scienze Matematiche e Informatiche, University of Sienna, in cooperation with the Dipartimento di Sistemi e Informatica, University of Florence.Papers were sought in a wide spectrum of areas, for instance, lattice path enumeration, bijective and algebraic combinatorics, non parametric statistical inference, random walks, discrete distribution, analysis of algorithms, graph theory, and queueing theory.A large Scientif c Committee, guaranteeing wide coverage of subtopics and expertise in a variety of f elds, selected 37 papers for presentation as talks, and selected 14 other papers for presentation as posters.Furthermore, one plenary lecture was given by Anthony J. Guttmann, University of Melbourne, an outstanding researcher in combinatorics who studied several models of lattice paths.The present volume collects18enriched and extended versions of the papers presented in Sienna.All papers have been referred and we thank all referees for their assistance.Altogether, the papers collected here offer a snapshot of current research.At the same time, they illustrate the numerous ramif cations of the combinatorics of lattice paths throughout statistics, mathematics and computer science.Thus we hope that this volume will serve both as a reference text and as an introduction to many fascinating aspects of this f eld.

In this paper, we consider the class of L-convex polyominoes, i.e. the convex polyominoes in which any two cells can be connected by a path of cells in the polyomino that switches direction between the vertical and the horizontal at most once. Using the ECO method, we prove that the number fn of L-convex polyominoes with perimeter 2(n+2) satisfies the rational recurrence relation fn =4fn−1 −2fn−2, with f0 =1, f1 =2, f2 =7. Moreover, we give a combinatorial interpretation of this statement. In the last section, we present some open problems.