스큐머지 순열

순열 패턴 이론에서 스큐-머지 순열은 증가 시퀀스와 감소 시퀀스로 분할할 수 있는 순열입니다.그것들은 스탄코바(1994)에 의해 처음 연구되었고 앳킨슨(1998)에 의해 이름이 붙여졌다.

특성화

증가 수열과 감소 수열로 분할할 수 없는 가장 작은 두 순열은 3412와 2143입니다.스칸코바(1994)는 스큐 병합 순열을 두 패턴 3412와 2143을 피하는 순열로 동등하게 정의할 수 있다는 것을 최초로 확립했다.

치환은 관련된 치환 그래프가 분할 그래프일 경우에만(내림차순에 대응) 클리크 및 독립 세트(내림차순에 대응)로 분할할 수 있는 그래프인 경우에만 스큐머지됩니다.스큐 병합 순열의 두 가지 금지된 패턴인 3412와 2143은 분할 그래프에 대해 금지된 세 가지 하위 그래프 중 두 가지, 4개의 버텍스 사이클과 두 개의 분리된 가장자리를 가진 그래프에 각각 대응한다.세 번째 금지 유도 하위 그래프인 5개의 완전 순환은 순열 그래프에 존재할 수 없다(Kézdy, Snevily & Wang(1996) 참조).

열거

n ${\displaystyle =1}$,${\displaystyle 2}$,${\displaystyle }$3 $...({displaystyle$ n$=1,2,3,\display$})의 경우 $길이{\displaystyle }$n({$displaystyle$n$$})의 스큐 정렬 수는 다음과 같습니다.

1, 2, 6, 22, 86, 340, 1340, 5254, 20518, 79932, 311028, 1209916, 4707964, 18330728, ...(OEIS의 시퀀스 A029759).

앳킨슨(1998)은 이 숫자들의 생성 함수가

${\displaystyle {1-3x}{(1-2x){\displayrt {1-4x}}}},$

따라서 길이$n{\displaystyle }$(\$displaystyle$ n$)$의 스큐-스큐 배열의 수는 다음 공식에 의해 주어진다.

${\displaystyle {2n}{n}\sum _{m=0}^{n-1}2^{n-m-1}{\binom {2m}{m}}}$

그리고 이 숫자들이 반복 관계를 따르고 있다.

${\displaystyle P_{n}=black {(9n-8)P_{n-1}-(26n-46)P_{n-2}+(24n-60)P_{n-3}:{n}}.}$

스큐 병합 순열의 생성 함수의 또 다른 파생은 Albert & Vatter(2013)에 의해 제시되었다.

계산의 복잡성

Albert 등(2016년)에 나타난 바와 같이, 한 치열이 다른 치환의 패턴인지 아닌지를 테스트하는 것은 두 치환 중 더 큰 치환의 스큐 병합 시 효율적으로 해결할 수 있다.

레퍼런스

• 를 클릭합니다Albert, Michael; Vatter, Vincent (2013), "Generating and enumerating 321-avoiding and skew-merged simple permutations", Electronic Journal of Combinatorics, 20 (2): Paper 44, 11 pp., MR 3084586.

• 를 클릭합니다Albert, Michael; Lackner, Marie-Louise; Lackner, Martin; Vatter, Vincent (2016), "The complexity of pattern matching for 321-avoiding and skew-merged permutations", Permutation Patterns 2015, Discrete Mathematics & Theoretical Computer Science, 18 (2): P11:1–17, arXiv:1510.06051, Bibcode:2015arXiv151006051A, MR 3597961.

• 첨부된 Volker Strehl의 코멘트도 참조해 주세요Atkinson, M. D. (1998), "Permutations which are the union of an increasing and a decreasing subsequence", Electronic Journal of Combinatorics, 5: RP6:1–13, MR 1490467.

• Kézdy, André E.; Snevily, Hunter S.; Wang, Chi (1996), "Partitioning permutations into increasing and decreasing subsequences", Journal of Combinatorial Theory, Series A, 73 (2): 353–359, doi:10.1016/S0097-3165(96)80012-4, MR 1370138

• Sloane, N. J. A. (ed.). "Sequence A029759". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

• 특히 정리 2.9, 페이지 303–304를 참조한다Stankova, Zvezdelina E. (1994), "Forbidden subsequences", Discrete Mathematics, 132 (1–3): 291–316, doi:10.1016/0012-365X(94)90242-9, MR 1297387.