오일러 수 (조합론)

이 문서는 조합론의 오일러 수(Eulerian number) ${\displaystyle \left\langle \textstyle {n \atop m}\right\rangle }$에 관한 것입니다. 베르누이 수와 관련된 수열에 대해서는 오일러 수 문서를 참고하십시오.

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

정의

오일러 수는 다음과 같다.

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

이를 ${\displaystyle A(n,m)}$이나 ${\displaystyle E(n,m)}$으로 쓰기도 한다.

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

오일러 다항식 ${\displaystyle A_{n}(x)}$은 오일러 수를 계수로 하는 다항식이다.

${\displaystyle A_{n}(x)=\sum _{m=0}^{n}\left\langle {n \atop m}\right\rangle x^{m}}$

역사

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

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

표

낮은 차수의 오일러 수는 다음과 같다. (OEIS의 수열 A008292) 이러한 표를 오일러 삼각형이라고 하며, 파스칼 삼각형과 여러 유사한 성질을 가진다. n번째 행의 수들의 합은 ${\displaystyle 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