Equivalence classes of permutations avoiding a pattern

Details Equivalence classes of permutations avoiding a pattern Equivalence classes of permutations avoiding a pattern

2010-05-29

arxiv.org/abs/1005.5419v1

Mathematics

Combinatorics

27 pages

Scientific paper

Given a permutation pattern p and an equivalence relation on permutations, we study the corresponding equivalence classes all of whose members avoid p. Four relations are studied: Conjugacy, order isomorphism, Knuth-equivalence and toric equivalence. Each of these produces a known class of permutations or a known counting sequence. For example, involutions correspond to conjugacy, and permutations whose insertion tableau is hook-shaped with 2 in the first row correspond to Knuth-equivalence. These permutations are equinumerous with certain congruence classes of graph endomorphisms. In the case of toric equivalence we find a class of permutations that are counted by the Euler totient function, with a subclass counted by the number-of-divisors function. We also provide a new symmetry for bivincular patterns that produces some new non-trivial Wilf-equivalences

Affiliated with

Also associated with

No associations

Rating

Equivalence classes of permutations avoiding a pattern does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Equivalence classes of permutations avoiding a pattern, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Equivalence classes of permutations avoiding a pattern will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-86106