슈퍼패턴

수학적 순열과 순열 패턴 연구에서 슈퍼패턴 또는 범용 순열은 주어진 길이의 모든 패턴을 포함하는 순열이다.좀 더 구체적으로 말하자면, k-superpatter는 k 길이의 가능한 모든 패턴을 포함하고 있다.^[1]

정의 및 예제

만약 π이 어떤 순서로 1부터 n까지의 숫자의 순열로 표현되는 길이 n의 순열이고 s = s₁, s₂, ...s가_k 길이 k의 subsequ의 순열인 경우, s는 원소가 s와 같은 순서에 있는 길이 k의 순열인 고유한 패턴에 해당한다.즉, 인덱스의 각 쌍 i와 j에 대해 s의 i번째 요소가 j번째 요소보다 작은 경우에만 패턴의 i번째 요소가 jthe 요소보다 작아야 한다.동등하게, 패턴은 순서에 따라 이질화된다.예를 들어, π이 순열 25314인 경우, 길이 3의 10개의 반복을 가지며, 다음과 같은 패턴을 형성한다.

반복	패턴
253	132
251	231
254	132
231	231
234	123
214	213
531	321
534	312
514	312
314	213

순열 π은 길이 k의 패턴이 길이 k의 순열 모두를 포함하면 k-슈퍼패턴이라고 불린다.예를 들어, 25314의 길이-3 패턴은 길이-3 순열 6개를 모두 포함하고 있으므로 25314는 3-슈퍼 패턴이다.3-슈퍼 패턴은 짧을 수 없다. 왜냐하면 123과 321 두 패턴을 형성하는 두 개의 반복은 한 위치에서 교차할 수 있기 때문에 이 두 패턴을 덮기 위해서만 5개의 기호가 필요하다.

길이 한계

Arratia(1999)는 가능한 최단 k-슈퍼패턴의 길이를 결정하는 문제를 소개했다.^[2]그는 길이 k의² 슈퍼패턴(제곱 격자 내 점의 좌표 벡터에 대한 사전 편찬 순서에 의해 주어짐)이 존재한다고 관찰했으며, 길이 n의 슈퍼패턴의 경우 패턴이 있는 만큼 최소한 부속이 있는 경우라고 보았다.즉$,{\displaystyle }$ (${\displaystyle n\genfrac{}{}{0ex}{}{}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{k}{}}$) ${\displaystyle \ge }$ ${\displaystyle k!}$ ${\displaystyle {\tbinom {n}{k}}\geq$ k$!\},$ 여기서 n ≥ k²/e², 여기서 e ≈ 2.71828은 오일러의 번호라는 스털링의 근사치가 따르게 된다.이 하한은 나중에 크로만, 콴, 싱할(2021년)이 1.000076k²/e로² 증가시켜 k²/e² 하한선이 팽팽하다는 아라티아의 추측을 반증했다.^[3][2]

아랏티아가 입증한 슈퍼패턴 길이에 대한² k의 상한이 팽팽하지 않다.중간 개선 후,^[4] 밀러(2009)는 모든 k에 대해 최대 k(k + 1)/2 길이의 k-슈퍼패턴이 있음을 증명했다.^[5]이 바운드는 나중에 엥겐과 바터(2021년)가 improved(k²+1)/2⌉^[6]로 낮춘 것에 의해 개선되었다.

에릭손 등은 가장 짧은 k-슈퍼패턴의 실제 길이가 k²/2에 무증상이라고 추측했다.^[4]그러나 이는 아래에 기술된 임의의 슈퍼패턴에 대한 알론의 추측과 모순된다.

랜덤 슈퍼패턴

연구원들은 또한 무작위 과정에 의해 생성되는 시퀀스가 슈퍼패턴이 되기 위해 필요한 길이도 연구했다.^[7]Arratia(1999)는 무작위 순열의 최장 증가 순열은 길이(높은 확률) 약 2㎛n을 가지기 때문에, k-슈퍼 패턴일 확률이 높으려면 임의 순열의 길이가 최소 k²/4 이상이어야 한다고 본다. 이것보다 짧은 순열은 ID 패턴을 포함하지 않을 가능성이 높다.^[2]그는 어떤 to > 0에 대해서도 높은 확률로 길이² k/(4 - ε)의 무작위 순열이 k-슈퍼패턴이 될 것이라는 추측을 앨런의 탓으로 돌린다.

참고 항목

• 슈퍼퍼뮤테이션

참조