Counting permutations avoiding two flat partially ordered patterns

이 논문은 두 개의 평탄한 부분 순서 패턴을 동시에 피하는 치환의 열거를 연구하여 이를 $k$-피보나치 수와 연결하고, 제한된 치환 사이의 전단사 대응을 통해 생성 함수를 유도하며, 분리 가능 치환에 대한 통계적 결과를 확장했습니다.

핵심

이 논문은 수학의 한 분야인 '조합론'에서 **순열 (Permutation)**이라는 개념을 가지고 놀고 있는 연구자들의 이야기입니다. 순열을 쉽게 말해 '1 부터 n 까지의 숫자를 섞어서 나열하는 것'이라고 생각하시면 됩니다. 예를 들어, 1, 2, 3 을 섞으면 123, 132, 213, 231, 312, 321 이렇게 6 가지가 나오죠.

이 연구는 **"특정한 규칙을 위반하지 않는 숫자 나열을 몇 개나 만들 수 있을까?"**라는 질문을 던집니다.

이 복잡한 수학적 내용을 일상적인 언어와 비유로 풀어보겠습니다.

---

1. 핵심 개념: "규칙을 지키는 숫자 게임"

비유: "금지된 모양의 블록 쌓기"
상상해 보세요. 여러분은 레고 블록으로 탑을 쌓고 있습니다. 하지만 여기에는 **'금지된 모양'**이 있습니다.

• 예를 들어, "작은 블록 위에 큰 블록이 올라가면 안 된다"거나, "특정 순서로 블록이 나열되면 안 된다"는 규칙이 있는 거죠.
• 수학자들은 이 '금지된 모양'을 **POP(부분 순서 패턴)**이라고 부릅니다.

이 논문은 **두 가지의 다른 금지된 모양 (Pj 와 ePℓ)**을 동시에 피하면서 탑을 쌓는 방법을 연구합니다. 즉, "A 라는 나쁜 모양도 안 되고, B 라는 나쁜 모양도 안 되는데, 그럼 몇 가지 탑을 쌓을 수 있을까?"를 계산하는 것입니다.

2. 연구의 발견: "피보나치 숫자의 친척들"

연구자들은 놀라운 사실을 발견했습니다.

• 단순한 규칙 (길이 3): 만약 금지된 모양이 아주 간단하다면, 만들 수 있는 탑의 개수는 우리가 잘 아는 **피보나치 수열 (1, 1, 2, 3, 5, 8...)**과 똑같은 규칙을 따릅니다.
• 더 복잡한 규칙 (길이 4, 5): 금지된 모양이 조금 더 길어지고 복잡해지면, 피보나치 수열의 '친척'인 k-피보나치 수열이라는 새로운 규칙이 등장합니다.
  • 비유: 피보나치 수열이 "이전 두 수를 더한다"면, k-피보나치는 "이전 k 개의 수를 모두 더한다"는 식으로 확장된 것입니다.

이것은 마치 **"규칙이 조금만 바뀌어도, 세상의 숫자 흐름이 완전히 새로운 패턴을 보여준다"**는 것을 의미합니다.

3. 방법론: "제한된 공간에서의 춤"

연구자들은 이 문제를 풀기 위해 아주 창의적인 비유를 사용했습니다.

• 제한된 춤 (Restricted Permutations): 숫자들이 춤을 추는데, 무대 (숫자의 위치) 에 따라 춤추는 방식에 제한이 걸려 있습니다. "너는 원래 자리에서 2 칸 이상은 못 움직인다"거나 "너는 오른쪽으로만 1 칸은 가야 한다"는 식의 규칙입니다.
• 연구자들은 **"금지된 모양을 피하는 숫자 나열"**과 **"제한된 공간에서 춤추는 숫자"**가 사실은 동일한 문제임을 증명했습니다.
  • 비유: "특정 모양을 피하는 길 찾기"와 "좁은 복도에서 부딪히지 않고 걷기"가 사실은 같은 문제라는 것을 발견한 셈입니다. 이 연결고리를 통해 복잡한 문제를 훨씬 쉽게 풀 수 있게 되었습니다.

4. 결과: "거대한 공식의 탄생"

연구자들은 컴퓨터와 수학적 논리를 동원해 3 부터 5 까지의 다양한 규칙 조합에 대한 **생성 함수 (Generating Function)**라는 거대한 공식을 찾아냈습니다.

• 생성 함수란? "이 규칙을 따르는 숫자 나열이 1 개, 2 개, 3 개... 있을 때, 그 개수를 한 번에 나타내는 거대한 수식"입니다.
• 놀라운 사실: 규칙이 길어질수록 이 수식은 엄청나게 복잡해집니다.
  • 예를 들어, 규칙이 5 일 때, 분자 (수식의 윗부분) 에는 293 개의 항이, 분모 (아랫부분) 에는 17 개의 항이 들어가는 거대한 식이 나왔습니다.
  • 비유: 간단한 레고 놀이가 아니라, 293 개의 서로 다른 부품을 정교하게 조립해야만 완성되는 거대한 성을 설계한 것과 같습니다.

5. 왜 중요한가요?

이 연구는 단순히 숫자를 세는 것을 넘어, 복잡한 시스템에서 규칙을 어떻게 이해하고 예측할 수 있는지에 대한 통찰을 줍니다.

• 컴퓨터 과학: 데이터 정렬이나 암호화 알고리즘 설계에 활용될 수 있습니다.
• 수학적 아름다움: 아주 단순해 보이는 규칙 (숫자 나열) 이 얼마나 다양한 패턴을 만들어내는지, 그리고 그 패턴들이 서로 어떻게 연결되는지를 보여줍니다.

요약

이 논문은 **"특정 나쁜 모양을 피하면서 숫자를 나열하는 방법"**을 연구했습니다. 연구자들은 이 문제가 **"제한된 공간에서의 춤"**과 같다는 것을 발견했고, 이를 통해 피보나치 수열의 확장된 버전을 찾아냈습니다. 규칙이 복잡해질수록 수식은 거대하고 정교해지지만 (293 개의 항!), 그 안에 숨겨진 수학적 질서는 매우 아름답습니다.

마치 복잡한 미로에서 길을 찾는 것처럼, 연구자들은 두 가지의 다른 미로 규칙을 동시에 피하는 길을 찾아내어, 그 길의 개수를 정확히 계산해낸 것입니다.

기술 요약

논문 요약: 두 개의 평탄한 부분 순서 패턴 (Flat POPs) 을 피하는 순열의 계수

1. 연구 배경 및 문제 정의

• 배경: 부분 순서 패턴 (Partially Ordered Patterns, POPs) 은 고전적인 순열 패턴 (classical patterns) 을 포괄하는 일반적인 프레임워크로, 순열 패턴 이론에서 중요한 역할을 합니다. 기존 연구들은 주로 하나의 POP 을 피하는 순열의 계수에 집중해 왔으며, Gao 와 Kitaev 는 길이 4 와 5 인 POP 을 피하는 순열에 대한 많은 계수 문제를 해결했습니다.
• 연구 목표: 본 논문은 **두 개의 평탄한 부분 순서 패턴 (flat POPs)**인 $P_j$와 $\tilde{P}_\ell$을 동시에 피하는 순열의 계수 문제를 다룹니다. 여기서 $j, \ell \ge 2$입니다.
• 구체적 대상:
  • $P_j$: 길이 $j$의 특정 구조를 가진 POP.
  • $\tilde{P}_\ell$: 길이 $\ell$의 특정 구조를 가진 POP (그림 1 참조).
  • 연구는 특히 **분리 가능한 순열 (separable permutations)**에 초점을 맞추며, 이는 $2413$과$3142$패턴을 피하는 순열 집합$S_n(2413, 3142)$과 동일합니다.
• 목표: 두 패턴을 동시에 피하는 순열의 개수를 구하고, 6 가지 통계량 (ascents, descents, left-to-right maxima/minima, right-to-left maxima/minima) 에 대한 동시 분포를 나타내는 생성 함수 (generating function) 를 유도하는 것입니다.

2. 방법론

논문은 다음과 같은 세 가지 주요 단계로 접근법을 구성합니다.

1. k-피보나치 수와의 연결 (Section 2):

   • $P_j$와 $\tilde{P}_3$ (또는 $P_3$와 $\tilde{P}_j$) 을 동시에 피하는 순열의 개수가 **k-피보나치 수 (k-Fibonacci numbers)**와 직접적으로 연결됨을 증명합니다.
   • $|S_n(P_j, \tilde{P}_3)| = F^{(j-1)}_{n+1}$임을 보였습니다. 이는 순열의 첫 번째 또는 두 번째 원소가 1 이어야 한다는 조건을 통해 점화식을 유도하여 증명되었습니다.

2. 제한된 순열 (Restricted Permutations) 과의 동치성 (Section 3):

   • $P_j$와 $\tilde{P}_\ell$을 피하는 순열 $\pi$는 제한된 순열 조건인 $-\ell+2 \le \pi_i - i \le j-2$를 만족하는 순열과 동치임을 증명합니다 (Theorem 3.1).
   • 이 연결을 통해 Baltić [4] 가 개발한 제한된 순열의 생성 함수를 구하는 방법 (방정식 체계 해결) 을 적용하여 POP-avoiding 순열의 생성 함수를 계산할 수 있게 되었습니다.

3. 함수 방정식 체계 및 생성 함수 유도 (Section 4 & 5):

   • 분리 가능한 순열의 **Stankova 분해 (Stankova's decomposition)**를 활용하여 재귀적인 구조를 분석합니다.
   • $n$과 $n-1$의 위치 관계 (왼쪽/오른쪽) 에 따라 경우를 나누고, 이를 바탕으로 $F_{j,\ell}(x, p, q, u, v, s, t)$에 대한 함수 방정식 체계를 수립합니다.
   • 이 체계는 $3 \le j, \ell \le 5$인 모든 경우에 대해 명시적인 유리 함수 (rational function) 형태의 생성 함수를 유도하는 데 사용됩니다.

3. 주요 결과

• 일반적인 생성 함수 체계:

  • $3 \le j, \ell \le 5$인 모든 경우에 대해 6 가지 통계량에 대한 동시 분포를 나타내는 생성 함수$F_{j,\ell}$에 대한 함수 방정식 체계 (Theorem 4.2) 를 제시했습니다.
  • 이 체계는 $f_{j,\ell,i}$와 $g_{j,\ell,i}$와 같은 보조 생성 함수들을 통해 순열의 구조적 분해를 반영합니다.

• 명시적인 생성 함수 (Explicit Forms):

  • $j=\ell=3$ (Theorem 5.1): 분모가 $pqutx^2 + putx - 1$인 유리 함수. 계수화 시 피보나치 수열 ($1, 1, 2, 3, 5, \dots$) 이 나옵니다.
  • $j=3, \ell=4$ (Theorem 5.3) 및 $j=3, \ell=5$ (Theorem 5.5): 각각 3 차 및 4 차 피보나치 수열과 관련된 생성 함수를 유도했습니다.
  • $j=\ell=4$ (Theorem 5.7): 분자 49 항, 분모 7 항으로 구성된 유리 함수.
  • $j=4, \ell=5$ (Theorem 5.9): 분자 93 항, 분모 10 항으로 구성된 유리 함수.
  • $j=\ell=5$ (Theorem 5.11): 가장 복잡한 경우로, 분자에 293 개의 단항식 (monomials), 분모에 17 개의 단항식이 포함된 유리 함수를 유도했습니다. 이는 두 패턴이 모두 길이 5 일 때 생성 함수의 복잡도가 급격히 증가함을 보여줍니다.

• 통계량 분포:

  • 유도된 생성 함수는 순열의 오름차순 (ascents), 내림차순 (descents), 왼쪽에서 오른쪽 최대/최소값, 오른쪽에서 왼쪽 최대/최소값의 개수에 대한 동시 분포를 제공합니다.

4. 의의 및 기여

1. 이론적 확장: 기존에 단일 POP 을 피하는 순열에 대한 연구 (Gao et al.) 를 확장하여, 두 개의 평탄한 POP 을 동시에 피하는 경우를 체계적으로 연구한 최초의 논문 중 하나입니다.
2. 구조적 통찰: POP-avoiding 순열과 제한된 순열 (restricted permutations) 및 k-피보나치 수 사이의 깊은 연결을 규명하여, 다양한 조합론적 객체 간의 관계를 밝혔습니다.
3. 계산적 성과: $j, \ell \le 5$인 모든 경우에 대해 생성 함수의 명시적인 유리 함수 형태를 제공했습니다. 특히 $j=\ell=5$와 같이 패턴 길이가 커질수록 생성 함수가 매우 복잡해짐 (단항식 개수 급증) 을 보여주어, 이 문제의 계산적 난이도를 정량화했습니다.
4. 방법론적 기여: Stankova 분해와 Baltić의 방법을 결합하여 다중 패턴 회피 문제의 생성 함수를 유도하는 체계적인 알고리즘을 제시했습니다.

5. 결론 및 향후 과제

• 결론: 두 개의 평탄한 POP 을 피하는 분리 가능한 순열에 대한 완전한 생성 함수 체계를 $j, \ell \le 5$까지 확립했습니다.
• 한계 및 제언: $j, \ell \ge 4$인 일반적인 경우에 대해 모든 POP 에 적용 가능한 일반적인 방정식 체계를 수립하는 것은 여전히 열려 있는 문제 (open problem) 입니다. 패턴이 추가될수록 구조적 분석이 복잡해지고 생성 함수가 매우 거대해지기 때문에, 일반적인 해법을 찾는 것은 계산적 복잡성 측면에서 큰 도전과제입니다.

이 논문은 POP-avoiding 순열의 계수 이론을 심화시키고, 복잡한 패턴 회피 문제에 대한 생성 함수 유도 방법을 정립했다는 점에서 조합론 분야에서 중요한 기여를 합니다.