Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Stack-sortable permutation
open-in-new
<p>In <a href="/facts/Mathematics/pxTouaz4">mathematics</a> and <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a stack-sortable permutation (also called a tree permutation) is a <a href="/facts/Permutation/JSw9ukmv">permutation</a> whose elements may be <a href="/facts/Sorting_algorithm/PwHpj1Gs">sorted</a> by an algorithm whose internal storage is limited to a single <a href="/facts/Stack_(abstract_data_type)/bj7l94v1">stack data structure</a>. The stack-sortable permutations are exactly the permutations that do not contain the <a href="/facts/Permutation_pattern/ytUU2b91">permutation pattern</a> 231; they are counted by the <a href="/facts/Catalan_number/R9vd4D3V">Catalan numbers</a>, and may be placed in <a href="/facts/Bijection/j4gTuTmW">bijection</a> with many other combinatorial objects with the same counting function including <a href="/facts/Dyck_path/R9vd4D3V">Dyck paths</a> and <a href="/facts/Binary_tree/TDV7GMpu">binary trees</a>. </p>