Wyniki wyszukiwania - BazTech

1

A Generating Tree for Permutations Avoiding the Pattern 122+3

Duchi E., Guerrini V., Rinaldi S.

Fundamenta Informaticae

|

2018

|

Vol. 163, nr 1

21--39

EN

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

2

The Identity Transform of a Permutation and its Applications

Frosini A., Battaglino D., Rinaldi S., Socci S.

Fundamenta Informaticae

|

2015

|

Vol. 141, nr 2/3

191--205

EN

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 Zn. In the first part of this paper we study 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.

3

Polygons Drawn from Permutations

Bilotta S., Rinaldi S., Socci S.

Fundamenta Informaticae

|

2013

|

Vol. 125, nr 3/4

329--342

EN

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 F(p) on the points of π, and prove that there exists a column-convex permutomino P such that π1(P) = π if and only if F(p) is satisfiable. This property can be then used to give a characterization of the set of column-convex permutominoes P such that π1(P) = π.