2025-11-11T23:22:27.749446

Emerging consecutive pattern avoidance

Hassler, Kirgizov
In this note we study the {\em asymptotic popularity}, that is, the limit probability to find a given consecutive pattern at a random position in a random permutation in the eighteen classes of permutations avoiding at least two length 3 consecutive patterns. We show that for ten classes, this popularity can be readily deduced from the structure of permutations. By combining analytical and bijective approaches, we study in details two more involved cases. The problem remains open for five classes.
academic

새로운 연속 패턴 회피

기본 정보

  • 논문 ID: 2511.02442
  • 제목: Emerging consecutive pattern avoidance
  • 저자: Nathanaël Hassler, Sergey Kirgizov (Université Bourgogne Europe)
  • 분류: math.CO (조합론), cs.DM (이산수학)
  • 발표일: 2025년 11월 5일 (arXiv 사전인쇄본)
  • 논문 링크: https://arxiv.org/abs/2511.02442

초록

본 논문은 점근적 인기도(asymptotic popularity) 문제를 연구합니다. 즉, 길이 3의 연속 패턴 중 최소 두 개를 회피하는 18개 배열류에서, 무작위 배열의 무작위 위치에서 주어진 연속 패턴을 발견할 확률의 극한을 조사합니다. 연구 결과, 10개 배열류의 경우 이러한 인기도를 배열 구조에서 직접 도출할 수 있음을 보여줍니다. 해석적 방법과 전단사 방법을 결합하여 저자들은 두 가지 더 복잡한 경우를 상세히 연구했습니다. 5개 배열류에 대한 문제는 여전히 미해결 상태입니다.

연구 배경 및 동기

연구 문제

본 논문은 배열에서 연속 패턴 회피(consecutive pattern avoidance)의 점근적 행동을 연구합니다. 구체적으로:

  • 특정 길이 3의 연속 패턴을 회피하는 배열류가 주어질 때
  • 이러한 배열류에서 회피되지 않은 다른 패턴의 점근적 인기도 연구
  • 점근적 인기도는 다음과 같이 정의됩니다: 크기 n인 무작위 배열의 무작위 위치에서 특정 패턴 p를 발견할 확률이 n이 무한대로 갈 때의 극한

문제의 중요성

  1. 이론적 의의: 특정 패턴이 점근적 의미에서 사라지는 "흥미로운 사실"을 드러냅니다 (확률이 0으로 수렴)
  2. 고전적 문제의 확장: Bóna와 Homberger의 고전적 패턴(비연속)에 관한 연구를 연속 패턴으로 확장합니다
  3. 서로 다른 조합 대상의 연결: 전단사를 통해 배열과 다른 조합 구조(예: Dyck 경로, 대합)를 연결합니다

기존 방법의 한계

  • Bóna와 Homberger의 연구는 고전적(비연속) 패턴에만 적용됨
  • Kitaev와 Mansour는 18개 회피 배열류의 개수를 제시했지만 점근적 인기도는 연구하지 않음
  • 모든 18개 배열류를 처리하는 체계적 방법 부재

연구 동기

Baril, Burstein, Kirgizov의 4에서 Class 7에 대한 연구에서 비롯되었으며, 그들은 배열과 분산된 Dyck 경로 사이의 전단사를 사용하여 패턴을 전이시켰고, 이것이 본 논문의 작업에 영감을 주었습니다.

핵심 기여

  1. 18개 배열류의 체계적 연구: Kitaev-Mansour가 제시한 길이 3의 최소 두 개 연속 패턴을 회피하는 18개 배열류의 완전한 분석
  2. 10개 단순 류 해결: Classes 1,2,3,5,6,8,9,16,18 및 이미 해결된 Class 7에 대해 구조에서 직접 점근적 인기도 도출
  3. 2개 복잡 류의 심층 분석:
    • Class 11 (Av(123,132,321)): 해석적 및 조합적 방법 결합
    • Class 17 (Av(123,132)): Foata 변환과 대합의 전단사 활용
  4. 미해결 문제 제시: 5개 배열류(Classes 10,12,13,14,15)의 문제가 여전히 미해결임을 명확히 함
  5. 패턴 소멸 현상 발견: 특정 류에서 특정 패턴의 점근적 인기도가 0임을 증명 (패턴 소멸)

방법론 상세 설명

작업 정의

입력:

  • 배열류 An=Avn(p1,…,pm)A_n = \text{Av}_n(p_1, \ldots, p_m), 연속 패턴 p1,…,pmp_1, \ldots, p_m 회피
  • 회피되지 않은 길이 3의 연속 패턴 pp

출력:

  • 점근적 인기도 popA(p):=lim⁡n→∞pnAn∣An∣\text{pop}_A(p) := \lim_{n \to \infty} \frac{p_n^A}{n|A_n|}

여기서 pnAp_n^A는 AnA_n의 모든 배열에서 패턴 p의 총 출현 횟수입니다.

핵심 개념

연속 패턴: 배열 π는 연속 부분수열 aiai+1⋯ai+r−1a_i a_{i+1} \cdots a_{i+r-1}이 p와 순서 동형이면 연속 패턴 p를 포함합니다.

대칭 연산:

  • 역순 R(π): 배열을 역순으로 정렬
  • 보수 C(π): 각 원소 a를 n+1-a로 대체
  • 이러한 연산은 연속 패턴의 출현을 보존합니다

방법 분류

1. 구조 분석법 (단순 류)

구조가 단순한 배열류의 경우, 배열 형식에서 직접 도출:

Class 1 (Av(123,132,312,321)):

  • 2개의 교대 배열만 포함
  • 대칭성에서 직접 pop(213) = pop(231) = 1/2 도출

Class 18 (Av(132,231)):

  • 배열 형식: a1⋯ak1b1⋯bn−k−1a_1 \cdots a_k 1 b_1 \cdots b_{n-k-1}
  • 여기서 a1⋯aka_1 \cdots a_k는 감소, b1⋯bn−k−1b_1 \cdots b_{n-k-1}는 증가
  • 개수: 321의 출현 횟수 = ∑k=1n−1(n−1k)(k−1)=(n−1)⋅2n−2−2n−1+1\sum_{k=1}^{n-1} \binom{n-1}{k}(k-1) = (n-1) \cdot 2^{n-2} - 2^{n-1} + 1
  • 결론: pop₁₈(321) = pop₁₈(123) = 1/2, pop₁₈(213) = pop₁₈(312) = 0

Class 16 (Av(123,321)):

  • 대칭성 활용: 류는 R, C, R∘C에서 안정
  • 4개의 회피되지 않은 패턴이 이러한 전단사를 통해 일대일 대응
  • 결론: pop₁₆(132) = pop₁₆(231) = pop₁₆(312) = pop₁₆(213) = 1/4

2. 해석적 방법 (Class 11)

Class 11 (Av(123,132,321)):

단계 1: 구조 분석

  • 배열은 교대 또는 반교대
  • 오른쪽에서 왼쪽으로 한 원소를 건너뛰면 증가 수열 획득
  • 두 부분집합으로 분류: AnrA_n^r (마지막 원소가 1) 및 AnlA_n^l (끝에서 두 번째 원소가 1)
  • ∣Anr∣=(n−2)!!|A_n^r| = (n-2)!!, ∣Anl∣=(n−1)!!|A_n^l| = (n-1)!!

단계 2: 패턴 231의 개수 위치 구조 직접 관찰: 231n=(n−1)!!⌈n−32⌉+(n−2)!!⌈n−22⌉231_n = (n-1)!! \left\lceil \frac{n-3}{2} \right\rceil + (n-2)!! \left\lceil \frac{n-2}{2} \right\rceil

단계 3: 패턴 312의 재귀 재귀 관계 설정 (Lemma 3.2):

  • 312nr=312n−1l312_n^r = 312_{n-1}^l
  • 312nl=(n−1)(312n−2l+(n−3)!!)−(n−5)!!(n−3)(n−2)2312_n^l = (n-1)(312_{n-2}^l + (n-3)!!) - (n-5)!! \frac{(n-3)(n-2)}{2}

단계 4: 생성함수 풀이un:=312nl(n−1)!!u_n := \frac{312_n^l}{(n-1)!!}로 설정하면, 생성함수: f(z)=z(2(z−1)ln⁡(1−z)+z3+3z2−2z)4(1−z)2(1+z)f(z) = \frac{z(2(z-1)\ln(1-z) + z^3 + 3z^2 - 2z)}{4(1-z)^2(1+z)}

결론: 312nl=(n−1)!!((−1)n−1+n−34+12∑k=1k≠nmod2n−11k)312_n^l = (n-1)!! \left( \frac{(-1)^{n-1} + n - 3}{4} + \frac{1}{2} \sum_{\substack{k=1\\k \neq n \bmod 2}}^{n-1} \frac{1}{k} \right)

점근 결과: pop₁₁(231) = 1/2, pop₁₁(213) = pop₁₁(312) = 1/4

3. 전단사 방법 (Class 17)

Class 17 (Av(123,132)):

핵심 도구: Foata 변환 Claesson은 Foata 변환이 Av_n(123,132)과 대합 집합 I_n 사이의 전단사를 설정함을 증명했습니다.

표준 형식:

  1. 각 사이클은 최소 원소로 시작
  2. 사이클은 최소 원소의 감소 순서로 정렬
  3. 괄호를 제거하여 배열 획득

패턴 대응 (Table 2):

  • Av(123,132)의 321 ↔ I_n의 (c)(b)(a) 또는 고정점을 포함하는 형식
  • 231 ↔ (bc)(a⋆) (고정점 없음)
  • 213 ↔ (⋆b)(ac) (고정점 없음)
  • 312 ↔ (⋆c)(ab) (고정점 없음)

핵심 보조정리:

  • Lemma 4.2: 고정점 개수의 점근적 행동 fpn∣In∣∼n→∞n\frac{\text{fp}_n}{|I_n|} \sim_{n \to \infty} \sqrt{n} 이는 고정점이 대합에서 희소함을 나타내며, 고정점을 포함하는 패턴은 무시할 수 있습니다.
  • Lemma 4.3: 고정점 없는 패턴의 인기도만 계산하면 됨

패턴 231 분석 (Proposition 4.4):

  • 패턴 α = (bc)(a⋆)는 두 개의 연속 대합에 대응
  • 각 연속 대합 쌍은 정확히 하나의 α와 하나의 β 또는 γ 생성
  • 결론: pop₁₇(231) = 1/2, pop₁₇(321) = 0

패턴 213 분석 (가장 복잡):

  • Av(123,132)의 패턴 2314에 대응
  • 재귀 관계 설정 (Lemma 4.5): 2314n=2314n−1+(n−1)⋅2314n−2+(n−22)∣In−4∣2314_n = 2314_{n-1} + (n-1) \cdot 2314_{n-2} + \binom{n-2}{2}|I_{n-4}|
  • 지수 생성함수 (Proposition 4.6): G(z)=e(1+z)222∫0ze−(1+t)22dt+z(z−2)ez+z224G(z) = \frac{e^{\frac{(1+z)^2}{2}}}{2} \int_0^z e^{-\frac{(1+t)^2}{2}} dt + \frac{z(z-2)e^{z+\frac{z^2}{2}}}{4}
  • 점근 분석:
    • 첫 번째 항: [zn]z(z−2)ez+z22∼n∣In∣n![z^n]z(z-2)e^{z+\frac{z^2}{2}} \sim \frac{n|I_n|}{n!}
    • 두 번째 항: 안장점 방법을 사용하여 [zn]F(z)=o(n∣In∣n!)[z^n]F(z) = o(\frac{n|I_n|}{n!}) 증명
    • 안장점 ζ=n\zeta = \sqrt{n} 선택으로 충분한 상한 획득

결론: pop₁₇(312) = pop₁₇(213) = 1/4

기술적 혁신점

  1. 혼합 방법: 연속 패턴 점근적 인기도 연구에 구조 분석, 생성함수, 전단사 방법을 처음으로 체계적으로 결합
  2. 안장점 방법의 창의적 적용: Class 17에서 정확한 안장점 대신 근사 안장점 ζ=n\zeta = \sqrt{n}을 선택하여 분석 단순화
  3. 패턴 전이: Foata 변환을 사용하여 배열의 패턴 문제를 대합의 사이클 구조 문제로 변환
  4. 고정점 희소성: 고정점의 O(n)O(\sqrt{n}) 성장률이 점근 분석에서 무시 가능함을 증명

실험 설정

데이터 출처

본 논문은 순수 이론 연구로, 주로 다음을 기반으로 합니다:

  • Kitaev와 Mansour의 18개 배열류 개수 결과
  • 알려진 생성함수 및 점근 공식

검증 방법

전통적 의미의 실험은 없지만, 저자들은 다음을 언급합니다:

  • Classes 10,12,13,14,15에 대한 수치 실험 수행
  • 수렴 속도가 매우 느려 신뢰할 수 있는 추측 형성 어려움

실험 결과

주요 결과 (Table 1 요약)

류해결됨결과
1-9, 16, 18✓ (단순)인기도 0, 1/4, 1/2 또는 1
11✓ (Section 3)213: 1/4, 231: 1/2, 312: 1/4
17✓ (Section 4)213: 1/4, 231: 1/2, 312: 1/4, 321: 0
7✓ (기존 문헌4)213: 1/2, 231: 1/2, 312: 0
10, 12-15✗미해결 문제

주요 발견

  1. 패턴 소멸 현상:
    • 여러 류에서 특정 패턴의 점근적 인기도가 0 (예: Class 2의 231, Class 17의 321)
    • 이는 "상당히 흥미로운 사실"
  2. 대칭성 결과:
    • Class 16은 완벽한 4중 대칭성 전시 (모든 4개 패턴 인기도가 1/4)
    • 많은 류가 1/2의 대칭 분포 전시
  3. 유리수 인기도:
    • 모든 해결된 경우에서 인기도는 유리수 (0, 1/4, 1/2, 1)
    • 미해결 문제: 무리수 인기도가 존재하는가?

관련 연구

고전적 패턴 회피

  • Bóna & Homberger 1,2,3: 길이 3 고전적 패턴 하나를 회피하는 배열류 연구
    • Av(123)과 Av(132)에서 321의 점근적 인기도가 1임을 증명
  • Janson 15,16: Av(132)와 Av(321)에서 길이 3 고전적 패턴의 극한 분포 연구

연속 패턴 연구

  • Kitaev & Mansour 17,18,19: 18개 회피 배열류의 개수 제시 (본 논문의 기초)
  • Elizalde & Noy 9,10:
    • 증가 트리 및 박스 곱 기반 방법
    • Goulden-Jackson 클러스터 방법의 개작

전단사 및 패턴 전이

  • Barnabei, Bonetti, Silimbani 5:
    • Av(312)에서 크기 3 연속 패턴의 결합 분포 연구
    • Krattenthaler 전단사 및 Deutsch 대합 사용
  • Baril, Burstein, Kirgizov 4:
    • Faro 단어 및 배열의 패턴 통계 연구
    • 본 논문의 직접적 선행 연구 및 동기 출처

점근 정규성

  • Borga 6: 특정 패턴을 회피하는 배열에서 연속 패턴 출현의 점근 정규성 연구 (생성 트리 기반)

결론 및 논의

주요 결론

  1. 완전성: 18개 류 중 13개 체계적 해결 (10개 단순 + 2개 복잡 + 1개 기존)
  2. 방법론: 구조 분석, 생성함수, 전단사 방법의 효과적 결합 시연
  3. 이론적 통찰: 패턴 소멸 및 대칭성 등 흥미로운 현상 발견

한계

  1. 미완성 작업: 5개 배열류 (Classes 10,12,13,14,15) 여전히 미해결
  2. 수치적 어려움: 이러한 미해결 류의 수렴 속도가 매우 느려 수치 실험으로 추측 제시 어려움
  3. 방법의 한계: 기존 방법이 남은 복잡한 경우를 처리하기에 불충분해 보임

향후 방향

저자들은 Section 5에서 여러 미해결 문제를 제시합니다:

  1. 추측 5.1: popₐ(p) = 0이면, p를 회피하는 부분류 B에 대해 popB(q) = popₐ(q)
    • 이는 해결된 모든 경우에서 성립
  2. 확장 문제:
    • 길이 3 연속 패턴 하나만 회피할 때는 어떻게 되는가?
    • 무리수 점근적 인기도를 생성하는 패턴 집합을 찾을 수 있는가?
    • 극한(1.1)이 항상 존재하는가? 존재성을 어떻게 특성화하는가?
  3. 방법론적 문제:
    • 열거 또는 확률 방법으로 남은 5개 류를 해결할 수 있는가?
    • 모든 경우를 처리하는 통일된 프레임워크가 존재하는가?

심층 평가

장점

  1. 체계성 강함:
    • 18개 배열류의 점근적 인기도를 처음으로 체계적 연구
    • 명확한 분류 및 방법론 (단순 vs 복잡)
  2. 방법의 다양성:
    • 구조 분석, 생성함수, 전단사, 안장점 방법을 유연하게 활용
    • Class 17의 분석이 특히 정교하며 여러 기법의 유기적 결합 시연
  3. 이론적 깊이:
    • Lemma 4.2의 고정점 희소성 증명이 우아함
    • 생성함수 도출이 엄밀함 (특히 Class 11의 미분방정식)
  4. 명확한 작성:
    • 구조가 우수하며 단순에서 복잡으로 진행
    • Table 1이 명확한 개요 제공
    • 도표 (Figures 1-2)가 이해 도움

부족한 점

  1. 완전성:
    • 5개 문제 미해결 (전체의 28%)
    • 이러한 어려운 경우에 대한 심층 분석 또는 부분 결과 미제시
  2. 수치적 지원:
    • 수치 실험 언급이 있으나 구체적 데이터 미제시
    • 수렴 속도의 정량적 분석 부재
  3. 추측 검증:
    • 추측 5.1이 해결된 경우에서만 검증되며 더 광범위한 증거 부족
  4. 기술적 세부사항:
    • Class 17의 안장점 선택 ζ=n\zeta = \sqrt{n}의 동기를 더 상세히 설명 가능
    • 일부 계산 단계에서 점프가 큼

영향력

  1. 이론적 기여:
    • 연속 패턴 점근적 인기도의 체계적 연구 개척
    • 패턴 회피 이론에 새로운 관점 제공
  2. 방법론적 가치:
    • 여러 기법의 효과적 결합 시연
    • 패턴 전이 아이디어를 다른 조합 구조에 적용 가능
  3. 영감 제공:
    • 제시된 미해결 문제가 명확하고 흥미로움
    • 새로운 연구 방향 자극 가능
  4. 한계:
    • 주로 이론 결과로 실제 응용이 명확하지 않음
    • 남은 문제의 어려움이 단기 영향력 제한 가능

적용 분야

  1. 조합론 연구:
    • 배열 패턴 이론
    • 점근 열거
    • 생성함수 방법
  2. 알고리즘 설계:
    • 제약 배열 생성
    • 패턴 매칭 알고리즘
  3. 관련 분야:
    • 통계 물리의 제약 모델에 영감 제공 가능
    • 유전체학의 패턴 회피 문제와 관련 가능

참고문헌

주요 참고문헌:

  1. 4 Baril, Burstein, Kirgizov (2021): 본 논문의 직접적 동기 출처
  2. 17 Kitaev (2003): 18개 배열류 열거의 기초
  3. 7 Claesson (2001): Foata 변환 전단사 (Class 17의 핵심)
  4. 1-3 Bóna & Homberger (2010-2012): 고전적 패턴의 선구적 연구
  5. 11 Flajolet & Sedgewick (2005): 해석적 조합론의 표준 참고서

종합 평가: 이는 자연스럽고 흥미로운 문제를 체계적으로 연구한 견고한 조합론 논문입니다. 방법론 측면에서 여러 기법의 효과적 결합을 시연하며, 특히 Class 11과 17의 분석은 깊은 기술적 역량을 보여줍니다. 5개 류의 문제가 미해결되어 있지만, 완성된 작업은 해당 분야에 견고한 기초를 마련합니다. 논문은 명확하게 작성되었으며, 결과가 흥미롭고 (특히 패턴 소멸 현상), 제시된 미해결 문제는 명확하고 도전적입니다. 배열 패턴 이론을 연구하는 조합론자들에게 이는 깊이 있게 읽을 가치가 있는 논문입니다.