| 翻訳と辞書 |
| superpattern ： ウィキペディア英語版 |
superpattern
In the mathematical study of permutations and permutation patterns, a superpattern is a permutation that contains all of the patterns of a given length. More specifically, a ''k''-superpattern contains all possible patterns of length ''k''.〔.〕
==Definitions and example==
If π is a permutation of length ''n'', represented as a sequence of the numbers from 1 to ''n'' in some order, and ''s'' = ''s''1, ''s''2, ..., ''s''''k'' is a subsequence of π of length ''k'', then ''s'' corresponds to a unique ''pattern'', a permutation of length ''k'' whose elements are in the same order as ''s''. That is, for each pair ''i'' and ''j'' of indexes, the ''i''th element of the pattern for ''s'' should be less than the ''j''the element if and only if the ''i''th element of ''s'' is less than the ''j''th element. Equivalently, the pattern is order-isomorphic to the subsequence. For instance, if π is the permutation 25314, then it has ten subsequences of length three, forming the following patterns:
A permutation π is called a ''k''-superpattern if its patterns of length ''k'' include all of the length-''k'' permutations. For instance, the length-3 patterns of 25314 include all six of the length-3 permutations, so 25314 is a 3-superpattern. No 3-superpattern can be shorter, because any two subsequences that form the two patterns 123 and 321 can only intersect in a single position, so five symbols are required just to cover these two patterns.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「superpattern」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|