오일러 수 (조합론)

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

조합론에서 오일러 수(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$가 정확히 $m$개 있는 순열들의 개수이다. 즉, 순열을 기본적으로 증가하는 것으로 간주할 경우, "역행"이 $m$번 일어나는 $n$원소 순열의 개수이다.

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

$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)에 최초로 등장한다. 여기서 등장하는 다항식 $\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

참고 문헌

• Graham, Ronald L.; Donald E. Knuth, Oren Patashnik (1994). 《Concrete Mathematics: A Foundation for Computer Science》 (영어) 2판. Addison-Wesley.  CS1 관리 - 추가 문구 (링크)

외부 링크

• Weisstein, Eric Wolfgang. “Eulerian Number”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Euler's Number Triangle”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Worpitzky's Identity”. 《Wolfram MathWorld》 (영어). Wolfram Research.