请输入您要查询的字词:

 

单词 PermutationPattern
释义

permutation pattern


A permutation patternMathworldPlanetmath is simply a permutationMathworldPlanetmath viewed as its representation in one-line notation. Let π=π1π2πk be a permutation pattern on k symbols. Then for any permutation σ=σ1σ2σn𝔖n, we say that σ contains π if there is a (not necessarily contiguous) subword of σ of length k that is order-isomorphic to π. More formally,for any subset J={j1,,jk}{1,,n} of cardinality k, write

σJ=σj1σj2σjk.

There is a isomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath (http://planetmath.org/GroupHomomorphism) 𝔖J𝔖k. We say that σ contains π if there is some J{1,,n} of cardinality k such that σJπ under the isomorphism.

If a permutation σ does not contain π, then we say that σ avoids the pattern π.

For example, let π=132. Then the permutation σ=1234 avoids π, since σ is strictly increasing but π has a descent. On the other hand, τ=1423 contains π twice, once as the subword 142 and once as the subword 143.

Knuth showed that a permutation is stack-sortable if and only if it avoids the permutation pattern 231.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 13:31:50