오일러 수(Eulerian number)는 조합론에서 순열의 상승 수(ascent) 혹은 강하 수(descent)의 개수를 세는 정수값을 의미한다. 일반적으로 $A(n,k)$ 로 표기하며, 이는 원소가 $n$ 개인 집합의 모든 순열 중 정확히 $k$개의 상승을 갖는 순열의 개수를 나타낸다. 여기서 상승은 인덱스 $i;(1\le i<n)$에 대해 순열의 $i$번째 원소보다 $i+1$번째 원소가 클 때를 의미한다.
정의
$$ A(n,k)=#{,\pi\in S_n \mid \operatorname{asc}(\pi)=k,} \qquad(0\le k\le n-1) $$ $S_n$은 $n$개의 원소에 대한 전순열 집합이며, $\operatorname{asc}(\pi)$는 순열 $\pi$의 상승 수이다.
재귀식
오일러 수는 다음과 같은 2차 재귀관계를 만족한다. $$ A(n,k)=(k+1)A(n-1,k)+ (n-k)A(n-1,k-1) $$ 단, 경계조건은 $A(1,0)=1$이며, $k<0$ 혹은 $k\ge n$인 경우 $A(n,k)=0$이다.
명시적 공식
다항식 형태로는 다음과 같은 합으로 표현된다. $$ A(n,k)=\sum_{j=0}^{k+1} (-1)^j \binom{n+1}{j} (k+1-j)^n $$ 이 식은 포함-배제 원리를 이용해 유도된다.
생성함수
-
지수 생성함수
$$ \sum_{k=0}^{n-1} A(n,k) x^k = \sum_{m=0}^{\infty} m! , \left{ {n\atop m} \right} \frac{x^{m}}{(1-x)^{m+1}} $$ 여기서 $\left{ {n\atop m} \right}$는 스털링 제2종 수이다. -
함수형 생성함수
$$ \sum_{n\ge 0} \sum_{k=0}^{n-1} A(n,k) \frac{t^n}{n!} x^k = \frac{1-x}{e^{t(1-x)}-x} $$
성질 및 응용
- 대칭성: $A(n,k)=A(n,n-1-k)$ 이다. 즉 상승 수와 강하 수는 동일한 분포를 가진다.
- 합계: 모든 $k$에 대해 $\displaystyle \sum_{k=0}^{n-1} A(n,k)=n!$ 로, 전체 순열 수와 일치한다.
- 다항식 전개: $(x+1)^n$를 오일러 다항식 $\langle x\rangle_n$ 로 전개할 때 계수로 나타난다.
- 통계학·확률론: 순열의 상승/강하 구조는 무작위 순열의 기대값·분산 계산 등에 활용된다.
- 알고리즘: 순열 순열 순열을 생성하거나 순열의 순위(rank)를 계산할 때 오일러 수가 사용된다.
역사
오일러 수는 18세기 스위스 수학자 레오나르드 오일러(Leonhard Euler, 1707–1783)가 처음 연구한 것으로 알려져 있다. 오일러는 순열의 상승과 강하에 관한 문제를 다루면서 해당 수열을 도입하였다. 이후 20세기 초, 프랑스 수학자 앙리 퓌에르(Henri Poincaré)와 영국 수학자 마일스 트레슬리(M. A. T. L. Turán) 등이 이 수의 조합적 성질을 체계화하였다.
관련 개념
- 오일러 다항식(Eulerian polynomial) : $A_n(x)=\sum_{k=0}^{n-1} A(n,k)x^k$ 로 정의된다.
- 스털링 수(Stirling numbers) : 오일러 수와는 다른 조합적 분할을 다루지만, 생성함수 전개에서 상호 연관된다.
- 피보나치 수와의 관계 : 일부 특수 경우, 예를 들어 $A(2n,n-1)=\frac{1}{2}\binom{2n}{n}$ 와 같은 식이 피보나치 수와 연결될 수 있다.
참고 문헌
- Graham, R. L.; Knuth, D. E.; Patashnik, O. Concrete Mathematics. 2nd ed., Addison‑Wesley, 1994.
- Stanley, R. P. Enumerative Combinatorics, Volume 1. Cambridge University Press, 2011.
- Wilf, H. S. Generatingfunctionology. Academic Press, 1994.
(위 내용은 현재까지 확보된 학술 자료와 교과서에 기반한 객관적 정보이다.)