오일러 수

조합학에서, 오일러 숫자 A(n, m)는 정확히 m 원소가 이전 원소보다 큰 숫자 1에서 n의 순열 수입니다(m "ascents"를 사용한 순열).이 계수는 오일러 다항식의 계수다.

${\displaystyle A_{n}(t)=\sum _{m=0}^{n}A(n,m)\ t^{m}.}$

오일러 다항식은 지수 생성 함수에 의해 정의된다.

${\displaystyle \sum _{n=0}^{\inflt }A_{n}(t)\cdot {\frac{x^{n}}{n}}{n!}}}={\frac {t-1}{t-\mathrm {e}^{{(t-1)x}}}}$

오일러 다항식은 반복에 의해 계산될 수 있다.

${\displaystyle A_{0}(t)=1,}$

${\displaystyle A_{n}(t)=t(1-t)\cdot A_{n-1}'(t)+A_{n-1}(t)\cdot(1+(n-1)t),\quad n\geq 1.}$

이 정의를 쓰는 동등한 방법은 을러어 다항식을 다음과 같이 유도적으로 설정하는 것이다.

${\displaystyle A_{0}(t)=1,}$

${\displaystyle A_{n}(t)=\sum _{k=0}^{n-1}{\binom {n}{k}}}}A_{k}(t)\cdot(t-1)^{n-1-k},\quad n\geq 1.}$

A(n, m)에 대한 다른 표기법은 E(n, m) 및${\displaystyle andn\genfrac{}{}{0ex}{}{}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{m}{}}$⟩ ${\$n$\atop$ m$}\right\rangle }$이다$.$

역사

1755년, 리온하르트 오일러는 그의 저서에서 다항식 α₁(x) = 1, α₂(x) = 1, α(x) = x 1, α₃(x) = x + α²(x) = x + 4x + 1 등을 조사했다(팩시밀리 참조).이 다항식들은 현재 오일러 다항식 A_n(x)라고 불리는 것의 이동된 형태다.

기본 속성

주어진 n > 0의 경우, A(n, m)의 지수 m은 0부터 n - 1까지의 값을 취할 수 있다.고정 n의 경우 (n, n - 1, n - 2, ..., 1)의 오름차이가 0인 순열이 있다.또한 n - 1의 상승이 있는 단일 순열도 있다; 이것은 상승 순열이다. (1, 2, 3, ..., n.따라서 A(n, 0)와 A(n, n - 1)는 n의 모든 값에 대해 1이다.

m ascents로 순열을 반대로 하면 n - m - 1 ascent가 있는 또 다른 순열이 생성된다.따라서 A(n, m) = A(n, n - m - 1)

A(n, m)의 값은 n과 m의 작은 값에 대해 "수동으로" 계산할 수 있다.예를 들어,

n	m	순열	A(n, m)
1	0	(1)	A(1,0) = 1
2	0	(2, 1)	A(2,0) = 1
	1	(1, 2)	A(2,1) = 1
3	0	(3, 2, 1)	A(3,0) = 1
	1	(1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2)	A(3,1) = 4
	2	(1, 2, 3)	A(3,2) = 1

n보다 큰 값의 경우 A(n, m)는 재귀 공식을 사용하여 계산할 수 있다.

$[\displaystyle A(n,m)=(n-m)A(n-1,m-1)+(m+1)A(n-1,m)A(n-1,m)]}$

예를 들어,

$[\displaystyle A(4,1)=(4-1)A(3,0)+(1+1)A(3,1)=3\time 1+2\time 4=11]}$

0 ≤ n ≤ 9에 대한 A(n, m) (OEIS에서 순서 A008292)의 값은 다음과 같다.

m n	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

위의 삼각 배열을 오일러 삼각형 또는 오일러의 삼각형이라고 하며, 파스칼의 삼각형과 몇 가지 공통된 특징을 공유한다.n행의 합은 요인 n!이다.

명시식

A(n, m)에 대한 명시적 공식은^[1]

${\displaystyle A(n,m)=\sum _{k=0}^{m+1}(-1)^{k}{\binom {n+1}{k}{k+1-k)^{n}}}$

One can see from this formula, as well as from the combinatorial interpretation, that ${\displaystyle A(n,n)=0}$ for ${\displaystyle n>0}$, so that ${\displaystyle A_{n}(t)}$ is a polynomial of degree ${\displaystyle n-1}$ for ${\displaystyle n>0}$.

합계 속성

조합적 정의에서 볼 때, 고정값 n에 대한 오일러 숫자의 합은 숫자 1에서 n까지의 순열의 총수이므로,

${\displaystyle \sum _{m=0}^{n-1A(n,m)=n!{\text{{{}n\geq 1.}$

n의 고정 값에 대한 오일러 숫자의 교대 합은 베르누이 숫자 B와_n+1 관련이 있다.

${\displaystyle \sum _{m=0}^{n-1(-1)^{m(n,m)A({\frac {2^{n+1}-1)={\frac {2^{n+1}-1)B_{n+1}:{n+1}:{n+1}:{\text{{{}n\geq 1.}의 경우$

오일러 숫자의 기타 합계 특성은 다음과 같다.

${\displaystyle \sum _{m=0}^{n-1(-1)^{{m}{\frac {A(n,m)}{\binom{n-1}}}}{m}=0{\text{{}}}}}}{}}}}}}}}}$

${\displaystyle \sum _{m=0}^{n-1(-1)^{m}{\frac {A(n,m)}{\binom{n}}}={m+1)B_{n}{n}{n}{n\geck 2,}}$

여기서 B는_n 베르누이 n번이다^th.

정체성

오일러 번호는 n^th 파워의 순서에 대한 생성 함수에 포함된다.

${\displaystyle \sum _{k=0}^{\infty }k^{n}x^{k}={\frac {\sum _{m=0}^{n-1}A(n,m)x^{m+1}}{(1-x)^{n+1}}}={\frac {x\cdot A_{n}(x)}{(1-x)^{n+1}}}}$

$n{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 0}$ ${\displaystyle n\geq$ 0$}$의 경우$.$이는 0⁰ = 0과 A(0,0) = 1로 가정한다(원소가 없는 순열이 하나 있고 상승이 없기 때문이다).

우피츠키의 정체성은^[2] x를ⁿ 이항계수를 가진 오일러 숫자의 선형 결합으로 표현한다.

${\displaystyle x^{n}=\sum _{m=0}^{n-1A(n,m){\binom {x+m}{n}}.}$

라고 하는 것은 월피츠키의 정체에서 따온 것이다.

${\displaystyle \sum \sum \{k=1}^{{n}k^{n}=\sum _{m=0}^{n-1}A(n,m){\binom {N+1+m}{n+1}.}$

또 다른 흥미로운 정체성은

${\displaystyle {\frac {e}{1-ex}=\sum _{n=0}^{\n=0}^{\frac {A_{n}(x)}{n!(1-x)^{n+1}.}$

오른쪽의 분자는 오일러 다항식이다.

${\displaystyle \mathrm{f}}$${\displaystyle }$:${\displaystyle }$${\displaystyle R\mathbb{}}$→ ${\displaystyle C\mathbb{}}$ ${\$ f$:\mathb {R} \rightarrow \mathb {C}$에 통합 가능한 고정$$ 함수 f : ($0{\displaystyle }$${\displaystyle }$,${\displaystyle n}$ )$${\$displaystyle (0,n)$에 대해 우리는$$ 통합 공식을 가지고 있다.

${\displaystyle \int _{0}^{1}\cdots \int _{0}^{1}f\left(\left\lfloor x_{1}+\cdots +x_{n}\right\rfloor \right)dx_{1}\cdots dx_{n}=\sum _{k}A(n,k){\frac {f(k)}{n!}}.}$

두 번째 순서의 오일러 번호

각 k에 대해 순열에서 k의 두 발생 사이에 나타나는 모든 숫자가 k보다 크다는 속성을 갖는 다중 집합 {1, 1, 2, ···n}의 순열은 이중 요인 번호(2n-1)로 계수된다.second ${\displaystyle ⟨}$ n ${\displaystyle \genfrac{}{}{0ex}{}{m}{}⟩}$ { { { $\\$displaystyle $\script style$\left\$langle \!\langle {$n$$\n \$atop m}\rigle \!\rigle }$로 표시된 두 번째 주문의 오일리언 번호는 정확히 m ascention을 가진 모든 순열의 수를 센트한다$.$예를 들어, n = 3의 경우 등고기가 없는 순열은 15개, 등고기가 없는 순열은 1개, 등고기가 1개, 등고기가 2개인 순열이 8개, 등고기가 6개 있다.

332211,

221133, 221331, 223311, 233211, 113322, 133221, 331122, 331221,

112233, 122133, 112332, 123321, 133122, 122331.

두 번째 순서의 오일러 번호는 위의 정의에서 직접 이어지는 재발 관계를 만족시킨다.

$\displaystyle \left\langle \!\!\left\langle {n \atop m}\rigle \!\!\right\angle =(2n-m-1)\왼쪽\langle \!\!\left\langle {n-1 \atop m-1}\right\angle \!\!\right\rangle +(m+1)\왼쪽\langle \!\!\left\langle {n-1 \atop m}\rigle \!\!\right\rangele ,}$

iverson 대괄호 표기법으로 표현된 n = 0에 대한 초기 조건:

$\displaystyle \left\langle \!\!\left\langle {0 \atop m}\rigle \!\!\right\rangele =[m=0]}$

이에 상응하여, 2차 순서의 오일러 다항식, 여기서 P로_n 표기(그들에 대한 표준 표기법은 존재하지 않음)는 다음과 같다.

${\displaystyle P_{n}(x):=\sum _{m=0}^{n}\왼쪽\langle \!\!\left\langle {n \atop m}\rigle \!\!\rigle x^{m}}$

위의_n 반복 관계는 P(x) 시퀀스에 대한 반복 관계로 변환된다.

${\displaystyle P_{n+1}(x)=(2nx+1)P_{n}(x)-x(x-1)P_{n}^{\premy }(x)}$

초기 상태로

${\displaystyle P_{0}(x)=1.}$

후자의 재발은 통합 인자에 의해 다소 더 컴팩트한 형태로 쓰여질 수 있다.

${\displaystyle (x-1)^{-2n-2}P_{n+1}(x)=\좌측(1-x)^{-2n-1}P_{n(x)\우측)^{\prime }}}}}}}}}}}}}{\premyme }}}}}}}}}}$

그래서 이성적인 기능이

${\displaystyle u_{n}(x):=(x-1)^{-2n}P_{n}(x)}$

단순한 자율적 재발을 만족한다.

${\displaystyle u_{n+1}=\좌측값\frac {x}{1-x}u_{n}\우측)^{\premium u_{0}=1,}$

P_n(x) = (1-x)²ⁿ u_n(x)로 2차 순서의 오일러 다항식 및 계수로서 2차 순서의 오일러 숫자를 구한다.

다음은 두 번째 오일러 숫자의 값이다.

m n	0	1	2	3	4	5	6	7	8
1	1
2	1	2
3	1	8	6
4	1	22	58	24
5	1	52	328	444	120
6	1	114	1452	4400	3708	720
7	1	240	5610	32120	58140	33984	5040
8	1	494	19950	195800	644020	785304	341136	40320
9	1	1004	67260	1062500	5765500	12440064	11026296	3733920	362880

또한_n 값 P(1)인 n번째 행의 합은 (2n - 1)!!

2차 오일레리안 숫자를 지수화하는 것은 리오르단, 콤테트에 이어 (OEIS에서 순서 A008517), 그레이엄, 크누스, 파타쉬닉에 이어 (OEIS에서 순서 A201637), (시퀀스 A340556)의 3가지 맛으로 나타나게 되며, 게셀과 스탠리의 정의를 확장한다.

참조

• 오일러스, 레오나르두스 [레온하르트 오일러](1755).기관: 분석 피니토리움 ac 교조적 세리움[미분적분학의 발견, 유한 분석 및 직렬에 적용됨]에서 미분적분 누적 eius usu.학계는 사이언톨리움 페트로폴리타나; 베롤리니: 오피리나 미카엘리스.
• Carlitz, L. (1959). "Eulerian Numbers and polynomials". Math. Mag. 32 (5): 247–260. doi:10.2307/3029225. JSTOR 3029225.
• Gould, H. W. (1978). "Evaluation of sums of convolved powers using Stirling and Eulerian Numbers". Fib. Quart. 16 (6): 488–497.
• Desarmenien, Jacques; Foata, Dominique (1992). "The signed Eulerian numbers". Discrete Math. 99 (1–3): 49–58. doi:10.1016/0012-365X(92)90364-L.
• Lesieur, Leonce; Nicolas, Jean-Louis (1992). "On the Eulerian Numbers M=max (A(n,k))". Europ. J. Combinat. 13 (5): 379–399. doi:10.1016/S0195-6698(05)80018-6.
• Butzer, P. L.; Hauss, M. (1993). "Eulerian numbers with fractional order parameters". Aequationes Mathematicae. 46 (1–2): 119–142. doi:10.1007/bf01834003. S2CID 121868847.
• Koutras, M.V. (1994). "Eulerian numbers associated with sequences of polynomials". Fib. Quart. 32 (1): 44.
• Graham; Knuth; Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley. pp. 267–272.
• Hsu, Leetsch C.; Jau-Shyong Shiue, Peter (1999). "On certain summation problems and generalizations of Eulerian polynomials and numbers". Discrete Math. 204 (1–3): 237–247. doi:10.1016/S0012-365X(98)00379-3.
• Boyadzhiev, Khristo N. (2007). "Apostol-Bernoulli functions, derivative polynomials and Eulerian polynomials". arXiv:0710.1124 [math.CA].
• Petersen, T. Kyle (2015). "Eulerian Numbers". Birkhäuser Advanced Texts Basler Lehrbücher. Birkhäuser. pp. 3–18. doi:10.1007/978-1-4939-3091-3_1. ISBN 978-1-4939-3090-6. {{cite book}}:누락 또는 비어 있음 title=(도움말)

인용구

외부 링크

• OEIS 위키에서 오일러니안 다항식.
• "Eulerian Numbers". MathPages.com.
• Weisstein, Eric W. "Eulerian Number". MathWorld.
• Weisstein, Eric W. "Euler's Number Triangle". MathWorld.
• Weisstein, Eric W. "Worpitzky's Identity". MathWorld.
• Weisstein, Eric W. "Second-Order Eulerian Triangle". MathWorld.
• 오일러 매트릭스(일반화된 행 색인, 분산 합계)