Stack-sortable permutation

In mathematics and computer science, a stack-sortable permutation (also called a tree permutation)[1] is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. The stack-sortable permutations are exactly the permutations that do not contain the permutation pattern 231; they are counted by the Catalan numbers, and may be placed in bijection with many other combinatorial objects with the same counting function including Dyck paths and binary trees.

  1. ^ Cite error: The named reference knott was invoked but never defined (see the help page).

From Wikipedia, the free encyclopedia · View on Wikipedia

Developed by razib.in