Enumeration of fixed points of an involution on β(1, 0)-trees

Sergey Kitaev, Anna de Mier

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

β(1, 0)-trees provide a convenient description of rooted non-separable planar maps. The involution h on β(1, 0)-trees was introduced to prove a complicated equidistribution result on a class of pattern-avoiding permutations. In this paper, we describe and enumerate fixed points of the involution h. Intriguingly, the fixed points are equinumerous with the fixed points under taking the dual map on rooted non-separable planar maps, even though the fixed points do not go to each other under the know (natural) bijection between the trees and the maps.
LanguageEnglish
Pages1207-1221
Number of pages15
JournalGraphs and Combinatorics
Volume30
Issue number5
Early online date2 Jul 2013
DOIs
Publication statusPublished - 1 Sep 2014

Fingerprint

Involution
Enumeration
Fixed point
Planar Maps
Nonseparable
Pattern-avoiding Permutation
Equidistribution
Bijection

Keywords

  • planar maps
  • description trees
  • fixed points
  • enumeration

Cite this

@article{b803e04856d4479c86f134354612d303,
title = "Enumeration of fixed points of an involution on β(1, 0)-trees",
abstract = "β(1, 0)-trees provide a convenient description of rooted non-separable planar maps. The involution h on β(1, 0)-trees was introduced to prove a complicated equidistribution result on a class of pattern-avoiding permutations. In this paper, we describe and enumerate fixed points of the involution h. Intriguingly, the fixed points are equinumerous with the fixed points under taking the dual map on rooted non-separable planar maps, even though the fixed points do not go to each other under the know (natural) bijection between the trees and the maps.",
keywords = "planar maps, description trees, fixed points, enumeration",
author = "Sergey Kitaev and {de Mier}, Anna",
note = "The final publication is available at Springer via http://dx.doi.org/10.1007/s00373-013-1336-6",
year = "2014",
month = "9",
day = "1",
doi = "10.1007/s00373-013-1336-6",
language = "English",
volume = "30",
pages = "1207--1221",
journal = "Graphs and Combinatorics",
issn = "0911-0119",
number = "5",

}

Enumeration of fixed points of an involution on β(1, 0)-trees. / Kitaev, Sergey; de Mier, Anna.

In: Graphs and Combinatorics, Vol. 30, No. 5, 01.09.2014, p. 1207-1221.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Enumeration of fixed points of an involution on β(1, 0)-trees

AU - Kitaev, Sergey

AU - de Mier, Anna

N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/s00373-013-1336-6

PY - 2014/9/1

Y1 - 2014/9/1

N2 - β(1, 0)-trees provide a convenient description of rooted non-separable planar maps. The involution h on β(1, 0)-trees was introduced to prove a complicated equidistribution result on a class of pattern-avoiding permutations. In this paper, we describe and enumerate fixed points of the involution h. Intriguingly, the fixed points are equinumerous with the fixed points under taking the dual map on rooted non-separable planar maps, even though the fixed points do not go to each other under the know (natural) bijection between the trees and the maps.

AB - β(1, 0)-trees provide a convenient description of rooted non-separable planar maps. The involution h on β(1, 0)-trees was introduced to prove a complicated equidistribution result on a class of pattern-avoiding permutations. In this paper, we describe and enumerate fixed points of the involution h. Intriguingly, the fixed points are equinumerous with the fixed points under taking the dual map on rooted non-separable planar maps, even though the fixed points do not go to each other under the know (natural) bijection between the trees and the maps.

KW - planar maps

KW - description trees

KW - fixed points

KW - enumeration

UR - http://link.springer.com/journal/373

U2 - 10.1007/s00373-013-1336-6

DO - 10.1007/s00373-013-1336-6

M3 - Article

VL - 30

SP - 1207

EP - 1221

JO - Graphs and Combinatorics

T2 - Graphs and Combinatorics

JF - Graphs and Combinatorics

SN - 0911-0119

IS - 5

ER -