Finitely labeled generating trees and restricted permutations

V Vatter

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)

Abstract

Generating trees represent a useful technique in the enumeration of various combinatorial objects, particularly restricted permutations. Quite often the generating tree for the set of permutations avoiding a set of patterns requires infinitely many labels. Sometimes, however, this generating tree needs only finitely many labels. We characterize the finite sets of patterns for which this phenomenon occurs. We also present an algorithm - in fact, a special case of an algorithm of Zeilberger - that is guaranteed to find such a generating tree if it exists. (c) 2005 Elsevier Ltd. All rights reserved.

Original languageEnglish
Pages (from-to)559-572
Number of pages14
JournalJournal of Symbolic Computation
Volume41
DOIs
Publication statusPublished - May 2006

Keywords

  • restricted permutation
  • forbidden subsequence
  • generating tree
  • FORBIDDEN SUBSEQUENCES
  • ENUMERATION
  • CATALAN
  • NUMBER
  • ECO

Fingerprint

Dive into the research topics of 'Finitely labeled generating trees and restricted permutations'. Together they form a unique fingerprint.

Cite this