On a question about pattern avoidance of cyclic permutations

이 논문은 Archer 등이 제시한 순환 순열의 패턴 회피 문제 중 $\tau=1432$인 경우를 해결하기 위해 순환 형태의 구조 분석과 딜워스 정리를 적용하여 명시적인 공식을 유도했습니다.

핵심

🎡 제목: "숫자 놀이와 회전 목마: 숨겨진 규칙 찾기"

이 연구는 **1 부터 n 까지의 숫자들을 일렬로 나열하는 '순열'**과 **숫자들을 원형으로 연결한 '사이클'**이라는 두 가지 세계에서 동시에 특정 '나쁜 패턴'을 피하는 숫자 배열이 몇 가지인지 세는 문제를 다룹니다.

1. 두 가지 세계: "줄 서기"와 "회전 목마"

이 문제를 이해하려면 두 가지 상황을 상상해 보세요.

• 상황 A: 줄 서기 (One-line notation)
  숫자들이 1 번부터 n 번까지 일렬로 줄을 서 있습니다. 예를 들어 3, 1, 4, 2 처럼요.
  여기서 **'나쁜 패턴 (δk)'**은 숫자가 크기 순서대로 거꾸로 줄을 서는 것을 말합니다.

  • 예: 4, 3, 2, 1처럼 큰 숫자가 앞에 오고 작은 숫자가 뒤에 오면 안 됩니다. (특히 3 개 이상 연속해서 거꾸로 서면 안 됨)

• 상황 B: 회전 목마 (Cycle forms)
  같은 숫자들이 원형으로 연결된 회전 목마에 탑승했습니다. 1이 가장 먼저 탑승하고, 그 다음에 다른 숫자들이 앉습니다.
  이 회전 목마는 어디서 시작하든 (회전하든) 같은 구조로 간주됩니다. 하지만 문제는 이 회전 목마를 어떤 각도에서 보든 특정 모양을 만들지 않아야 한다는 것입니다.

  • 나쁜 패턴 (1432): 회전 목마를 어느 각도에서 보든, 작은 숫자 → 아주 큰 숫자 → 중간 숫자 → 작은 숫자 순서로 앉으면 안 됩니다. (예: 1, 4, 3, 2 순서)

연구의 목표:
이전 연구자들은 "줄 서기"에서 4, 3, 2, 1 같은 거꾸로 줄을 서는 것을 피하고, "회전 목마"에서 1, 3, 2, 4나 1, 3, 4, 2 같은 나쁜 패턴을 피하는 경우를 세어냈습니다. 하지만 **1, 4, 3, 2**라는 특정 패턴을 피하는 경우는 아직 답을 못 찾았습니다. 이 논문은 바로 그 **마지막 퍼즐 조각 (1, 4, 3, 2)**을 맞춰냈습니다.

---

🔍 해결 방법: "다일워스의 정리"라는 자석

저자들은 이 복잡한 숫자 배열을 세기 위해 **'다일워스의 정리 (Dilworth's Theorem)'**라는 강력한 수학적 도구를 사용했습니다.

• 비유:
  숫자들을 높이 다른 사람들이라고 상상해 보세요.

  • 사슬 (Chain): 키가 작은 사람부터 큰 사람까지 순서대로 줄을 서 있는 그룹.
  • 반사슬 (Antichain): 서로 키 순서가 안 맞는 사람들 (예: 큰 사람이 작은 사람 앞에 서 있는 경우).

  다일워스의 정리는 "사람들을 키 순서대로 줄을 세우는 그룹 (사슬) 으로 나누는 데 필요한 최소 그룹 수"와 "키 순서가 뒤죽박죽인 사람들 (반사슬) 의 최대 크기"가 같다는 것을 말합니다.

  이 논문의 저자들은 **"만약 '거꾸로 줄 서기 (δk)'가 없다면, 숫자들을 몇 개의 '올바른 줄 (사슬)'로만 나누어 설명할 수 있다"**는 사실을 이용했습니다. 이를 통해 무작위처럼 보이는 숫자 배열이 사실은 매우 제한된 규칙을 따르고 있음을 발견하고, 그 규칙을 이용해 경우의 수를 정확히 계산해 냈습니다.

---

📊 연구 결과: 세 가지 경우의 답

저자들은 숫자 k (거꾸로 줄 서는 길이의 기준) 에 따라 세 가지 경우로 나누어 답을 찾았습니다.

1. 경우 1: 거꾸로 줄 서는 길이가 3 일 때 (δ3)

   • 숫자가 3, 2, 1처럼 3 개 연속으로 거꾸로 서면 안 됩니다.
   • 결과: n이 클수록 그 수는 **약 n²/2**에 비례하여 증가합니다. (OEIS A061925)

2. 경우 2: 거꾸로 줄 서는 길이가 4 일 때 (δ4)

   • 숫자가 4, 3, 2, 1처럼 4 개 연속으로 거꾸로 서면 안 됩니다.
   • 결과: 그 수는 **약 2ⁿ**에 가까운 형태로 증가합니다. (OEIS A088921 과 관련됨)

3. 경우 3: 거꾸로 줄 서는 길이가 5 이상일 때 (δk, k≥5)

   • 숫자가 5 개 이상 연속으로 거꾸로 서면 안 됩니다.
   • 재미있는 사실: 1, 4, 3, 2 패턴을 피하는 회전 목마 구조 자체가 이미 5 개 이상의 거꾸로 줄을 서는 것을 자연스럽게 막아줍니다. 즉, "줄 서기" 규칙이 사실상 필요 없어집니다.
   • 결과: 이 경우의 수는 **2ⁿ + 1 - 2n - n³/6**이라는 깔끔한 공식으로 나옵니다.

---

💡 요약 및 의미

이 논문은 수학자들이 **"숫자들이 원형으로 배열될 때, 어떤 나쁜 모양을 피할 수 있는가?"**라는 질문에 답을 찾았습니다.

• 핵심 아이디어: 복잡한 숫자 나열을 **"올바른 줄 (사슬)"**로 나누어 생각하면, 무작위처럼 보이는 배열도 사실은 매우 단순한 규칙을 따르고 있음을 발견했습니다.
• 성공: 이전까지 풀리지 않았던 1, 4, 3, 2 패턴 회피 문제를 해결하여, 수학자들이 이 숫자 놀이의 전체적인 그림을 완성할 수 있게 했습니다.

이 연구는 단순히 숫자를 세는 것을 넘어, **복잡한 시스템 (숫자 배열) 속에 숨겨진 단순한 질서 (규칙)**를 찾아내는 수학적 사고의 힘을 보여줍니다. 마치 혼란스러운 회전 목마에서 모든 승객이 규칙적으로 앉는 방법을 찾아내는 것과 같습니다!

기술 요약

논문 요약: 순환 치환의 패턴 회피에 관한 연구

1. 연구 배경 및 문제 제기

• 연구 대상: $n$ 개의 원소로 이루어진 대칭군 $S_n$ 내의 순환 치환 (Cyclic Permutations). 순환 치환은 disjoint cycle decomposition 으로 표현했을 때 하나의 $n$-사이클로만 구성된 치환을 의미합니다.
• 패턴 회피 조건:
  1. 한 줄 표기 (One-line notation): 치환 $\pi = \pi_1 \pi_2 \cdots \pi_n$이 감소 패턴 $\delta_k = k(k-1)\cdots 21$을 포함하지 않아야 함.
  2. 표준 사이클 형태 (Standard cycle form): $C(\pi) = (1, c_2, \dots, c_n)$으로 시작하는 사이클 표현과 그 모든 순환 회전 (cyclic rotations) 이 길이 4 의 패턴 $\tau$를 포함하지 않아야 함.
• 구체적 문제: Archer 등 (2023) 은 $\tau$가 $1324$와$1342$인 경우를 해결했으나,$\tau = 1432$인 경우를 미해결 문제로 남겼습니다. 본 논문은 **$\tau = 1432$인 경우**를 해결하여, 한 줄 표기에서$\delta_k$를, 모든 사이클 형태에서$1432$를 회피하는 순환 치환의 개수$a^\circ_n(\delta_k; 1432)$에 대한 명시적 공식을 유도하는 것을 목표로 합니다.

2. 방법론 (Methodology)

본 논문은 다음과 같은 수학적 도구와 논리적 구조를 활용하여 문제를 해결했습니다.

• 구조적 분석 및 동치 조건 도출:
  • Proposition 2.1: 모든 사이클 형태가 $1432$를 회피할 필요충분조건은 **표준 사이클 형태$C(\pi)$가$321$과$2143$패턴을 모두 회피**하는 것임을 증명했습니다. 이는$1432$패턴의 존재 여부를$321$및$2143$ 패턴의 존재 여부로 환원시킴으로써 분석을 단순화했습니다.
• 다일워스 정리 (Dilworth's Theorem) 의 적용:
  • 한 줄 표기에서 감소 부분열 (decreasing subsequence) 의 길이가 $k$ 이상인 것은 해당 순서체 (poset) 에서 크기 $k$인 반사슬 (antichain) 이 존재함을 의미합니다.
  • Lemma 2.4: 다일워스 정리에 따라, 순서체 $S_\pi$가 $k-1$개의 체인 (chain) 으로 덮일 수 있다면, $\pi$는 $\delta_k$를 회피합니다. 이를 이용해 $k=3, 4, 5$에 대한 조건을 검증했습니다.
• 생성 함수 및 점화식 유도:
  • $C(\pi) = (1, j, c_3, \dots, c_n)$에서 두 번째 원소 $j$의 값에 따라 경우를 나누어 (Case analysis) 각 경우의 수 $a^\circ_{n,j}$를 계산했습니다.
  • $n$과 $j$의 관계에 따른 재귀적 관계 (bijection) 를 구성하여 점화식을 세우고 이를 풀어 명시적 공식을 도출했습니다.

3. 주요 결과 (Key Results)

$n \ge 5$인 경우, $k$의 값에 따라 다음과 같은 명시적 공식이 성립함을 증명했습니다.

• Theorem 1.1 ($k=3$인 경우):

  • 한 줄 표기에서 $\delta_3$ (감소 길이 3) 을 회피하고, 모든 사이클 형태에서 $1432$를 회피하는 순환 치환의 개수:
    $$a^\circ_n(\delta_3; 1432) = \left\lfloor \frac{n^2+7}{2} \right\rfloor - 2n$$
  • 이는 OEIS A061925 시퀀스에 해당합니다.

• Theorem 1.2 ($k=4$인 경우):

  • 한 줄 표기에서 $\delta_4$ (감소 길이 4) 를 회피하고, 모든 사이클 형태에서 $1432$를 회피하는 순환 치환의 개수:
    $$a^\circ_n(\delta_4; 1432) = 2^{n-1} - \left\lfloor \frac{3n-5}{2} \right\rfloor$$

• Theorem 1.3 ($k \ge 5$인 경우):

  • Lemma 4.1: 표준 사이클 형태가 $321$과$2143$을 회피하면, 자동으로 한 줄 표기에서$\delta_5$ (감소 길이 5) 를 회피하게 됩니다. (Erdős–Szekeres 정리를 활용하여 증명).
  • 따라서 $k \ge 5$인 경우, 한 줄 표기 조건은 사이클 형태 조건에 의해 자동으로 만족되므로, 단순히 $321$과$2143$을 회피하는 순환 치환의 개수와 동일해집니다.
    $$a^\circ_n(\delta_k; 1432) = 2^n + 1 - 2n - \binom{n}{3} \quad (k \ge 5)$$
  • 이는 OEIS A088921 시퀀스에 해당합니다.

4. 의의 및 기여 (Significance)

1. 미해결 문제 해결: Archer 등이 남긴 $\tau = 1432$에 대한 오픈 퀘스천을 완전히 해결하여, 길이 4 패턴 회피와 관련된 순환 치환의 분류를 완성했습니다.
2. 패턴 회피 이론의 확장: 순환 치환의 "한 줄 표기"와 "사이클 형태"라는 두 가지 서로 다른 표현 방식에 대한 동시 패턴 회피 조건을 체계적으로 분석한 사례를 제공합니다.
3. 이론적 도구 활용: 다일워스 정리를 순환 치환의 패턴 회피 문제 (특히 감소 부분열 제한) 에 적용하여 강력한 조합론적 증명을 제시했습니다.
4. 계산적 결과 제공: $k$의 값에 따라 다른 수열 (OEIS 등재) 로 귀결되는 명확한 공식을 제시함으로써, 향후 관련 연구나 알고리즘 개발에 기초 데이터를 제공합니다.

5. 결론

본 논문은 순환 치환이 특정 패턴 ($\delta_k$와 $1432$) 을 동시에 회피하는 경우의 수를$k$의 값 ($3, 4, \ge 5$) 에 따라 분류하고, 각각에 대한 닫힌 형식 (closed-form) 공식을 유도했습니다. 특히$k \ge 5$인 경우 한 줄 표기 조건이 사이클 형태의 구조적 제약에 의해 자동으로 충족된다는 발견은 이 분야의 중요한 통찰을 제공합니다.