DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2023.33

Pattern-Avoiding Binary Trees - Generation, Counting, and Bijections

Authors: Petr Gregor, Torsten Mütze, and Namrata

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract

In this paper we propose a notion of pattern avoidance in binary trees that generalizes the avoidance of contiguous tree patterns studied by Rowland and non-contiguous tree patterns studied by Dairyko, Pudwell, Tyner, and Wynn. Specifically, we propose algorithms for generating different classes of binary trees that are characterized by avoiding one or more of these generalized patterns. This is achieved by applying the recent Hartung-Hoang-Mütze-Williams generation framework, by encoding binary trees via permutations. In particular, we establish a one-to-one correspondence between tree patterns and certain mesh permutation patterns. We also conduct a systematic investigation of all tree patterns on at most 5 vertices, and we establish bijections between pattern-avoiding binary trees and other combinatorial objects, in particular pattern-avoiding lattice paths and set partitions.

Cite as

Petr Gregor, Torsten Mütze, and Namrata. Pattern-Avoiding Binary Trees - Generation, Counting, and Bijections. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.ISAAC.2023.33,
  author =	{Gregor, Petr and M\"{u}tze, Torsten and Namrata},
  title =	{{Pattern-Avoiding Binary Trees - Generation, Counting, and Bijections}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.33},
  URN =		{urn:nbn:de:0030-drops-193350},
  doi =		{10.4230/LIPIcs.ISAAC.2023.33},
  annote =	{Keywords: Generation, binary tree, pattern avoidance, permutation, bijection}
}

Search Results

Documents authored by Namrata

Pattern-Avoiding Binary Trees - Generation, Counting, and Bijections

Abstract

Cite as

Thanks for your feedback!

Could not send message