오일러 수 (조합론) 문서 원본 보기

{{위키데이터 속성 추적}}
{{다른 뜻|오일러 수|[[조합론]]의 오일러 수(Eulerian number) <math>\left\langle\textstyle{n\atop m}\right\rangle</math>|[[베르누이 수]]와 관련된 [[수열]]}}

[[조합론]]에서 '''오일러 수'''(Euler數, {{llang|en|Eulerian number}})는 주어진 개수의 역행을 가지는 [[순열]]을 세는 수이다.

== 정의 ==
'''오일러 수'''는 다음과 같다.
:<math>\left\langle{n\atop m}\right\rangle=\sum_{k=0}^m(-1)^k \binom{n+1}{k} (m+1-k)^n</math>
이를 <math>A(n,m)</math>이나 <math>E(n,m)</math>으로 쓰기도 한다.

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

'''오일러 다항식''' <math>A_n(x)</math>은 오일러 수를 계수로 하는 [[다항식]]이다.
:<math>A_n(x)=\sum_{m=0}^n\left\langle{n\atop m}\right\rangle x^m</math>

== 역사 ==
[[파일:EulerianPolynomialsByEuler1755.png|섬네일|오른쪽|400px|오일러의 《미분학의 기초》]]
오일러 수와 오일러 다항식은 1755년에 [[레온하르트 오일러]]의 책 《미분학의 기초 및 유한 해석과 급수에 대한 응용》({{llang|la|Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum}})<ref>{{서적 인용|성=Eulerus|이름=Leonardus|저자링크=레온하르트 오일러|날짜=1755|제목=Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum|출판사=Academia imperialis scientiarum Petropolitana|언어=la}}</ref>에 최초로 등장한다. 여기서 등장하는 다항식 <math>\alpha_1(x)</math>, <math>\alpha_2(x)</math> 등은 오늘날 오일러 다항식와 약간의 차이를 보이지만 기본적으로 같은 대상이다.

== 표 ==
낮은 차수의 오일러 수는 다음과 같다. {{OEIS|id=A008292}} 이러한 표를 '''오일러 삼각형'''이라고 하며, [[파스칼 삼각형]]과 여러 유사한 성질을 가진다. ''n''번째 행의 수들의 합은 <math>n!</math>이다.
:{| class="wikitable"
|-
! ''n''&nbsp;\&nbsp;''m''
! width="50" | 0
! width="50" | 1
! width="50" | 2
! width="50" | 3
! width="50" | 4
! width="50" | 5
! width="50" | 6
! width="50" | 7
! width="50" | 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|언어=en}}

== 외부 링크 ==
* {{매스월드|title=Eulerian Number|id=EulerianNumber}}
* {{매스월드|title=Euler's Number Triangle|id=EulersNumberTriangle}}
* {{매스월드|title=Worpitzky's Identity|id=WorpitzkysIdentity}}

{{전거 통제}}

[[분류:계승과 이항식 주제]]
[[분류:정수열]]
[[분류:열거조합론]]