오일러 수 (조합론)

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

정의

오일러 수는 다음과 같다.

$⟨\genfrac{}{}{0ex}{}{n}{m}⟩=\sum _{k=0}^m(-1{)}^k(\genfrac{}{}{0ex}{}{n+1}{k})(m+1-k{)}^n$

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

오일러 수 $⟨\genfrac{}{}{0ex}{}{n}{m}⟩$는 정수의 집합 $\{1,2,\dots ,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⟨\genfrac{}{}{0ex}{}{n}{m}⟩x^m$

역사

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

오일러 수와 오일러 다항식은 1755년에 레온하르트 오일러의 책 《미분학의 기초 및 유한 해석과 급수에 대한 응용》(틀:Llang)에 최초로 등장한다. 여기서 등장하는 다항식 ${\alpha }_1(x)$, ${\alpha }_2(x)$ 등은 오늘날 오일러 다항식와 약간의 차이를 보이지만 기본적으로 같은 대상이다.

표

낮은 차수의 오일러 수는 다음과 같다. 틀:OEIS 이러한 표를 오일러 삼각형이라고 하며, 파스칼 삼각형과 여러 유사한 성질을 가진다. 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

참고 문헌

• 틀:서적 인용

외부 링크

• 틀:매스월드
• 틀:매스월드
• 틀:매스월드