Words near each other
 ・ Permsky Uyezd ・ Permutable prime ・ Permutation ・ Permutation (album) ・ Permutation (Bill Laswell album) ・ Permutation (disambiguation) ・ Permutation (music) ・ Permutation (policy debate) ・ Permutation automaton ・ Permutation box ・ Permutation City ・ Permutation graph ・ Permutation group ・ Permutation matrix ・ Permutation model ・ Permutation pattern ・ Permutation polynomial ・ Permutation representation (disambiguation) ・ Permutatude theory ・ Permutohedron ・ Permutotetraviridae ・ Permyak Salty Ears ・ Pern ・ PERN Przyjazn SA ・ Pern, Lot ・ Perna ・ Perna (genus) ・ Perna canalicula ・ Perna caste ・ Perna perna
 Dictionary Lists
 mini英和辞書
 mini和英辞書
 Webster 1913
 Latin-English
 FOLDOC
 Wikipedia English
 ウィキペディア
 翻訳と辞書　辞書検索 [ 開発暫定版 ]
 スポンサード リンク
 Permutation pattern ： ウィキペディア英語版
Permutation pattern
In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. A permutation π of length ''n'' is written as a word in one-line notation (i.e., in two-line notation with the first line omitted) as π = π1π2…πn, where πi is the ith number in the word. For example, in the permutation π = 391867452, π1=3 and π9=2. A permutation π is said to ''contain'' the permutation σ if there exists a subsequence of (not necessarily consecutive) entries of π that has the same relative order as σ, and in this case σ is said to be a ''pattern'' of π, written σ ≤ π. Otherwise, π is said to ''avoid'' the permutation σ. For example, the permutation π = 391867452 contains the pattern σ = 51342, as can be seen in the highlighted subsequence of π = 391867452 (or π = 391867452 or π = 391867452 or π = 391867452). Each subsequence (91674, 91675, 91672, 91452) is called a ''copy,'' ''instance,'' or ''occurrence'' of σ. Since the permutation π = 391867452 contains no increasing subsequence of length four, π avoids 1234.
== Early results ==
A case can be made that was the first to prove a result in the field with his study of "lattice permutations".〔.〕 In particular MacMahon shows that the permutations which can be divided into two decreasing subsequences (i.e., the 123-avoiding permutations) are counted by the Catalan numbers.〔, Items 97 and 98.〕
Another early landmark result in the field is the Erdős–Szekeres theorem; in permutation pattern language, the theorem states that for any positive integers ''a'' and ''b'' every permutation of length at least ''ab'' + 1 must contain either the pattern 1, 2, 3, ..., ''a'' + 1 or the pattern ''b'' + 1, ''b'', ..., 2, 1.

ウィキペディアで「Permutation pattern」の詳細全文を読む

スポンサード リンク
 翻訳と辞書 : 翻訳のためのインターネットリソース