오일러 수 (조합론)

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

조합론에서, 오일러 수(Euler數, 영어: Eulerian number)는 주어진 개수의 역행을 가지는 순열을 세는 수이다.

정의[편집]

오일러 수는 다음과 같다.

\left\langle{n\atop m}\right\rangle=\sum_{k=0}^m(-1)^k \binom{n+1}{k} (m+1-k)^n

이를 A(n,m)이나 E(n,m)으로 쓰기도 한다.

오일러 수 \textstyle\left\langle{n\atop m}\right\rangle는 정수의 집합 \{1,2,\ldots,n\}순열 a_1,a_2,\dots,a_n 가운데, a_i>a_{i+1}i가 정확히 n개 있는 순열들의 개수이다. 즉, 순열을 기본적으로 증가하는 것으로 간주할 경우, "역행"이 m번 일어나는 n원소 순열의 개수이다.

오일러 다항식 A_n(x)은 오일러 수를 계수로 하는 다항식이다.

A_n(x)=\sum_{m=0}^n\left\langle{n\atop m}\right\rangle

역사[편집]

오일러의 《미분학의 기초》

오일러 수와 오일러 다항식은 1755년에 레온하르트 오일러의 책 《미분학의 기초 및 유한 해석과 급수에 대한 응용》(라틴어: Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum)[1] 에 최초로 등장한다. 여기서 등장하는 다항식 \alpha_1(x), \alpha_2(x) 등은 오늘날 오일러 다항식와 약간의 차이를 보이지만 기본적으로 같은 대상이다.

[편집]

낮은 차수의 오일러 수는 다음과 같다. (OEIS의 수열 A008292) 이러한 표를 오일러 삼각형이라고 하며, 파스칼 삼각형과 여러 유사한 성질을 가진다. n번째 행의 수들의 합은 n!이다.

n \ m 0 1 2 3 4 5 6 7 8
1 1
2 1 1
3 1 4 1
4 1 11 11 1
5 1 26 66 26 1
6 1 57 302 302 57 1
7 1 120 1191 2416 1191 120 1
8 1 247 4293 15619 15619 4293 247 1
9 1 502 14608 88234 156190 88234 14608 502 1

참고 문헌[편집]

  1. Eulerus, Leonardus (1755). 《Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum》 (라틴어). Academia imperialis scientiarum Petropolitana. 
  • Graham, Ronald L.; Donald E. Knuth, Oren Patashnik (1994). 《Concrete Mathematics: A Foundation for Computer Science》 (영어) (2판판). Addison-Wesley. 

바깥 고리[편집]