← 목록으로 돌아가기
이산화된 포물선 경계 아래의 격자 경로를 세는 수열 A392303이 OEIS에 정식 등록되었습니다.
1. 시작: 하나의 질문
"대각선 대신 포물선 아래로 제한하면 격자 경로가 몇 개나 될까?"
조합론에서 가장 유명한 수 중 하나인 카탈란 수(Catalan number)
$C_n$은 $(0,0)$에서 $(n,n)$까지 대각선 $y \leq x$ 아래를 지나는
북-동(NE) 격자 경로의 개수입니다.
이 문제는 수백 년의 역사를 가지고 있고,
닫힌 공식도 잘 알려져 있습니다.
$$C_n = \frac{1}{n+1}\binom{2n}{n}$$
그런데 경계를 직선이 아닌 포물선으로 바꾸면 어떻게 될까요?
$$y \;\leq\; \left\lfloor \frac{x^2}{n} \right\rfloor$$
이 질문에서 출발한 연구가 하나의 논문이 되고, 새로운 정수 수열로 OEIS에 등록되기까지의 과정을 정리해 봅니다.
2. 문제 정의
정수 $n \geq 1$에 대해, $(0,0)$에서 $(n,n)$까지의 NE 격자 경로 중
모든 꼭짓점이 이산화된 포물선 경계 아래에 머무는 경로의 수를 $p_n$이라 정의합니다.
정의. 이산화된 포물선 경계:
$$\hat{f}_n(x) = \left\lfloor \frac{x^2}{n} \right\rfloor, \quad 0 \leq x \leq n$$
이 경계 아래에 머무는 NE 격자 경로의 수: $p_n = N_n(n,n)$
이 문제가 고전적인 카탈란 경로 문제와 결정적으로 다른 점은 두 가지입니다:
- 경계가 곡선이다 — 직선이 아닌 포물선
- 경계가 $n$에 의존한다 — 끝점이 바뀌면 경계 자체가 변한다
이 두 번째 성질 때문에, 전이행렬(transfer-matrix)이나 커널 방법(kernel method)
같은 표준 기법이 곧바로 적용되지 않습니다.
3. 주요 결과
논문에서 증명한 핵심 결과들은 다음과 같습니다:
주요 정리 요약
- 기본 점화식: $N_n(x,y) = N_n(x-1,y) + N_n(x,y-1)$, 경계 조건 포함
- 효율적 계산: $O(n^2)$ 시간, $O(n)$ 공간의 DP 알고리즘
- 카탈란 수와의 비교: 모든 $n \geq 2$에 대해 $1 \leq p_n < C_n$
- P-recursive 탐색: 500개 항에서 차수 $\leq 6$, 계수 차수 $\leq 5$인 P-recursive 관계 없음
수열의 처음 몇 항은 다음과 같습니다:
| $n$ |
0 | 1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 | 9 | 10 |
| $p_n$ |
0 | 1 | 1 | 1 | 2 |
5 | 7 | 19 | 56 | 174 | 392 |
예시 ($n=4$)
각 $x$ 좌표에서의 경계 높이: $(0,\, 0,\, 1,\, 2,\, 4)$
이 경계 아래를 지나는 경로: 정확히 5개
4. OEIS 등록 과정
2026년 3월 9일 — 제출
논문의 핵심 수열을 OEIS에 제출했습니다. 처음 제출한 내용에는 10개의 항과 Python 구현, 수학적 설명이 포함되어 있었습니다.
2026년 3월 10일 — 편집자 리뷰
제출 후 하루 만에 OEIS 편집자 Hugo Pfoertner가 리뷰를 시작했고,
Alois P. Heinz가 Maple 코드를 작성하여 수열을 검증하고 대폭 확장했습니다.
2026년 3월 10일경 — 승인
리뷰와 검증을 거쳐 수열은 A392303으로 정식 승인되었습니다.
A392303: Number of NE lattice paths from (0,0) to (n,n)
staying weakly below the discretized parabolic boundary $y = \lfloor x^2/n \rfloor$.
5. 등록된 OEIS 항목의 내용
현재 OEIS A392303 페이지에는 다음이 수록되어 있습니다:
1,830
전체 계산 항 (A.P. Heinz)
- Maple 프로그램 (Alois P. Heinz 작성)
- Python 프로그램 (저자 원본)
- 카탈란 수 A000108과의 교차 참조
- $n$에 의존하는 경계의 특수성에 대한 해설
6. 열린 문제들
이 수열에는 여전히 풀리지 않은 문제들이 남아 있습니다:
- 점근 공식: $p_n$의 성장률은? $p_n \sim\; ?$ as $n \to \infty$
- 닫힌 공식: 카탈란 수처럼 깔끔한 공식이 존재하는가?
- D-유한성(D-finiteness): 생성함수가 미분 유한 함수인가?
- 확률론적 해석: 이산 브라운 브릿지와의 연결?
이 문제들 중 하나라도 해결된다면, 그것 자체로 하나의 논문이 될 수 있을 것입니다.
7. 되돌아보며
독립 연구자로서 OEIS에 새로운 수열을 등록하는 과정은 논문 투고와는 또 다른 경험이었습니다.
제출한 지 하루 만에 전문 편집자들이 코드를 검증하고, 항을 1,830개까지 확장해 주는 것을 보면서
OEIS 커뮤니티의 놀라운 역량과 헌신을 실감할 수 있었습니다.
수학 연구의 결과물이 공개 데이터베이스에 영구히 기록된다는 것 — 그 자체가 연구의 보람입니다.
- OEIS 수열: A392303
- 논문: "Enumeration of North-East Lattice Paths Under a Discretized Parabolic Boundary" (Integers 저널 심사 중)
- 저자: 이상열 (Sang Yeol Lee), iWorkMath Research Institute