Pattern Avoidance for Fibonacci Sequences using $k$-Regular Words

이 논문은 $k$-정규 단어에서 특정 패턴을 피하는 경우의 수가 각각 $k$-피보나치 점화식 $a_k(n)$과 $b_k(n)$을 따름을 증명하고, 관련 패턴의 변형에 대한 제곱된 피보나치 수에 대한 가설을 제시합니다.

핵심

🎮 게임의 규칙: "숫자 블록 쌓기"

이 논문에서 연구자들은 1 부터 n 까지의 숫자를 가지고 게임을 합니다.

• 규칙 1: 각 숫자는 정확히 k 번씩 사용해야 합니다. (예: k=2 이면 1, 1, 2, 2, 3, 3 처럼 두 번씩 나옵니다. 이를 'k-정규 단어'라고 부릅니다.)
• 규칙 2: 숫자들을 나열할 때, 특정 모양 (패턴) 을 만들면 안 됩니다.

예를 들어, 121 패턴이 금지되었다면, 1 과 2 가 섞여 있을 때 1 이 2 를 사이에 두고 다시 나오는 모양 (1...2...1) 은 허용되지 않습니다. 마치 "누군가 (2) 를 사이에 두고, 같은 사람 (1) 이 다시 나타나면 안 된다"는 규칙과 같습니다.

연구자들은 이 금지된 패턴을 피하면서 만들 수 있는 나열의 개수를 세어보았습니다. 놀랍게도 그 개수는 우리가 잘 아는 피보나치 수열이나 제이콥스탈 수열 같은 유명한 숫자 열과 정확히 일치했습니다.

---

🔍 주요 발견 3 가지

이 논문은 크게 세 가지 중요한 발견을 제시합니다.

1. "피보나치-k" 게임 (Theorem 1)

• 상황: 숫자 k 번씩 쓰고, 121, 123, 132, 213 이라는 4 가지 나쁜 패턴을 피합니다.
• 결과: 이때 만들 수 있는 나열의 개수는 **'피보나치-k 수열 (Fibonacci-k numbers)'**이라는 새로운 숫자 열과 정확히 같습니다.
• 비유: 마치 레고 블록을 쌓을 때, 특정 모양을 피하면 쌓을 수 있는 방법의 수가 피보나치 수열처럼 규칙적으로 늘어나는 것입니다.
  • k=1 이면 일반적인 피보나치 수열 (1, 1, 2, 3, 5...) 이 됩니다.
  • k=2 이면 '제이콥스탈 수열 (1, 1, 3, 5, 11...)'이 됩니다.
• 의미: 이전에 복잡한 방법으로 증명된 것을, 이 논문은 훨씬 간단하고 직관적인 방법으로 다시 증명했습니다.

2. "k-피보나치" 게임 (Theorem 2)

• 상황: 이번에는 122 와 213 이라는 2 가지 패턴만 피합니다.
• 결과: 이때의 나열 개수는 **'k-피보나치 수열 (k-Fibonacci numbers)'**과 일치합니다.
• 비유: 규칙을 조금만 바꾸면 (금지된 패턴을 줄이면), 또 다른 유명한 숫자 열이 나타납니다. 이는 피보나치 수열의 변형 버전이라고 볼 수 있습니다.

3. "피보나치 제곱"의 비밀 (Theorem 5)

• 상황: 가장 흥미로운 부분입니다. 121 패턴을 피할 때, 단순히 1과 2가 떨어져 있어도 안 되는 것이 아니라, 1과 2가 딱 붙어 있어야만 (연속적으로) 금지되는 경우를 다룹니다.
• 결과: 이렇게 규칙을 더 엄격하게 (연속 패턴으로) 바꾸면, 나열의 개수가 **피보나치 수열의 제곱 (1, 1, 4, 9, 25...)**이 됩니다.
• 비유: 마치 "1 과 2 가 붙어 있으면 안 되지만, 떨어져 있으면 괜찮다"는 규칙을 "1 과 2 가 바로 옆에 붙어 있으면 안 된다"로 바꾸자, 전체 경우의 수가 피보나치 수를 두 번 곱한 것처럼 변했습니다.

---

💡 왜 이 연구가 중요한가요?

1. 복잡한 것을 단순하게: 이전에 수학자들이 매우 어렵고 복잡한 방법 (생성 함수 등) 으로 증명했던 내용을, 이 논문은 직관적인 그림과 간단한 논리로 설명했습니다. 마치 복잡한 미로를 가장 짧은 길로 찾아낸 것과 같습니다.
2. 새로운 연결고리 발견: '숫자 나열 (단어)'이라는 개념과 '피보나치 수열'이라는 숫자 열 사이의 숨겨진 관계를 찾아냈습니다. 이는 수학의 다른 분야들 (그래프 이론, 컴퓨터 과학 등) 을 연결하는 다리가 됩니다.
3. 컴퓨터 과학적 응용: 패턴 회피 문제는 데이터 압축, 암호학, 알고리즘 설계 등 컴퓨터 과학 분야에서 매우 중요합니다. 이 연구는 이러한 문제들을 해결하는 새로운 도구를 제공합니다.

📝 한 줄 요약

"숫자 블록을 특정 나쁜 모양을 피해서 쌓는 게임에서, 그 경우의 수가 우리가 잘 아는 피보나치 수열이나 그 변형들과 정확히 일치한다는 것을, 아주 쉽고 아름다운 방법으로 증명했습니다."

이 논문은 수학이 단순히 숫자를 계산하는 것이 아니라, 세상의 복잡한 규칙 속에서 숨겨진 아름다운 패턴을 찾아내는 예술임을 보여줍니다.

기술 요약

논문 요약: k-규칙적 단어를 이용한 피보나치 수열의 패턴 회피

1. 연구 배경 및 문제 정의

이 논문은 이산수학 및 이론 컴퓨터과학 분야에서 패턴 회피 (Pattern Avoidance) 문제를 다루며, 특히 **k-규칙적 단어 (k-regular words)**와 피보나치 수열의 일반화 사이의 관계를 규명하는 것을 목표로 합니다.

• k-규칙적 단어: $[n] = \{1, 2, \dots, n\}$의 각 기호가 정확히 $k$번씩 등장하는 길이 $kn$의 단어를 의미합니다.
• 패턴 회피: 단어 내의 부분열이 특정 패턴 (예: $121, 123$ 등) 의 상대적 순서와 일치하지 않도록 하는 조건입니다.
• 주요 대상: 두 가지 일반화된 피보나치 수열을 정의하고, 이들이 특정 패턴을 회피하는 k-규칙적 단어의 개수와 일치하는지 증명합니다.
  • Fibonacci-k 수열 ($a_k(n)$): $a_k(n) = a_k(n-1) + k \cdot a_k(n-2)$, 초기값 $a_k(0)=a_k(1)=1$.
  • k-Fibonacci 수열 ($b_k(n)$): $b_k(n) = k \cdot b_k(n-1) + b_k(n-2)$, 초기값 $b_k(0)=b_k(1)=1$.

2. 주요 기여 및 결과

저자들은 세 가지 주요 정리를 통해 패턴 회피와 수열 계수 간의 대응 관계를 증명했습니다.

가. Fibonacci-k 단어에 대한 정리 (Theorem 1)

• 명제: $k \ge 1$인 모든 $n$에 대해, 패턴 $\{121, 123, 132, 213\}$을 회피하는 $k$-규칙적 단어의 개수는 Fibonacci-k 수열 $a_k(n)$과 일치합니다.
  • $|Av^k_n(121, 123, 132, 213)| = a_k(n)$
• 의미:
  • $k=1$일 때, 이는 Simion 과 Schmidt 의 고전적인 결과 (피보나치 수열) 를 포함합니다.
  • $k=2$일 때, 이는 Jacobsthal 수열 (A001045) 을 생성하며, Kuba 와 Panholzer 가 Stirling 순열의 맥락에서 증명한 바를 단순한 조합론적 증명으로 재확인합니다.
• 증명 방법: $n$이 가장 큰 기호일 때, 단어의 구조를 재귀적으로 분해하여 $a_k(n-1)$과 $a_k(n-2)$ 항으로 나누는 직접적인 조합론적 증명 (bijection) 을 제시했습니다.

나. k-Fibonacci 단어에 대한 정리 (Theorem 2)

• 명제: $k \ge 2$인 모든 $n$에 대해, 패턴 $\{122, 213\}$을 회피하는 $k$-규칙적 단어의 개수는 k-Fibonacci 수열 $b_k(n)$과 일치합니다.
  • $|Av^k_n(122, 213)| = b_k(n)$
• 의미:
  • $k=1$일 때 이 결과는 성립하지 않음 (Catalan 수열이 됨). 이는 $k \ge 2$일 때만 유효한 새로운 결과입니다.
  • $k=2$일 때, 이는 Pell 수열과 유사한 구조를 가지며 OEIS A001333 에 해당합니다.
• 증명 방법: Lemma 2 와 Lemma 3 을 통해 $k$-규칙적 단어 내에서 특정 기호의 위치 제약 조건을 규명하고, 이를 바탕으로 단어의 선두 구조를 분류하여 재귀식을 유도했습니다.

다. 제곱 피보나치 수열에 대한 정리 (Theorem 5)

• 명제: $n \ge 0$에 대해, 패턴 $\{121, 123, 132, 213\}$을 회피하는 2-규칙적 단어 중, 패턴 $121$이 **연속적 (consecutive/vincular)**으로 나타나지 않는 경우의 수는 **제곱 피보나치 수열$c(n) = a_1(n)^2$**과 일치합니다.
  • $|Av^2_n(\text{consecutive } 121, 123, 132, 213)| = a_1(n)^2$
• 의미:
  • 기존 Jacobsthal 수열 결과에 '연속 패턴 (vincular pattern)' 조건을 추가함으로써, 수열이 Jacobsthal 에서 제곱 피보나치 (OEIS A007598) 로 변환됨을 보였습니다.
  • $n=3$일 때, 일반 Jacobsthal 은 5 개이지만, 연속 $121$을 회피하는 조건을 추가하면 9 개 ($3^2$) 가 됩니다.
• 증명 방법: 단어의 '기저 (base)'와 '첨부 (annex)'로 분해하는 표준 분할 (standard partition) 개념을 도입하고, 이를 접두사 트리 (prefix-tree) 구조와 연결하여 재귀식 $c''(n) = c''(n-1) + 3c''(n-2) + 2\sum c''(n-i)$를 유도했습니다.

3. 방법론 (Methodology)

1. 조합론적 분해 (Combinatorial Decomposition):
   • 단어의 가장 큰 기호 ($n$) 의 위치와 반복 횟수를 분석하여, 전체 단어 집합을 더 작은 $n-1$ 또는 $n-2$ 크기의 부분 집합으로 분할합니다.
   • Lemma 1 과 Lemma 2 를 통해 패턴 회피 조건이 단어 내 기호의 상대적 순서에 어떤 제약을 가하는지 엄밀하게 증명합니다.
2. 재귀적 구조 분석:
   • 분할된 부분 집합의 크기를 통해 수열의 재귀식 (Recurrence relation) 을 유도하고, 이것이 정의된 피보나치 수열과 일치함을 보입니다.
3. 비연속 및 연속 패턴 (Vincular Patterns):
   • Theorem 5 에서는 패턴의 인접성 (consecutiveness) 을 고려하여, 기존 패턴 회피 이론을 비연속 패턴에서 연속 패턴으로 확장했습니다.
4. 트리 구조 매핑:
   • 제곱 피보나치 수열의 증명을 위해 '접두사 트리 (Prefix-tree)'를 정의하고, 단어의 접두사 (annex) 가 이 트리 위의 경로와 일대일 대응됨을 보였습니다.

4. 의의 및 결론

• 이론적 확장: Kuba 와 Panholzer 의 기존 결과 (Stirling 순열 맥락) 를 단순하고 직접적인 조합론적 증명으로 재해석하여, $k$-규칙적 단어의 패턴 회피 이론을 정립했습니다.
• 새로운 발견: $k \ge 2$인 경우에만 유효한 새로운 패턴 회피 결과 (Theorem 2) 를 제시하여, 피보나치 수열의 일반화와 패턴 회피 사이의 풍부한 관계를 보여주었습니다.
• 비연속 패턴의 통합: Vincular 패턴 (연속 패턴) 을 도입하여 Jacobsthal 수열에서 제곱 피보나치 수열로의 전환을 설명함으로써, 패턴 회피 연구의 새로운 방향성을 제시했습니다.
• 향후 연구: 이 논문은 k-규칙적 단어에서의 패턴 회피 연구가 Catalan 수열, Pell 수열 등 다른 수열 가족으로 확장될 수 있음을 시사하며, Table 5 에서 제시된 미해결 문제 (Conjecture 1) 를 통해 향후 연구 과제를 제시했습니다.

요약하자면, 이 논문은 k-규칙적 단어라는 구조를 통해 피보나치 수열의 다양한 일반화를 체계적으로 분류하고 증명함으로써, 조합론적 패턴 회피 이론의 지평을 넓힌 중요한 연구입니다.