오일러 수 (조합론)

1. 개요

오일러 수(Eulerian number)는 조합론에서 다루어지는 수로, 순열의 성질과 관련된 여러 가지 정의와 성질을 갖는다. 오일러 수는 일반적으로 $\backslash left\backslash langle\{n\backslash atop\; m\}\backslash right\backslash rangle$으로 표기하며, 이는 집합 {1, 2, ..., n}의 순열에서 'i' > 'i+1'인 'i'가 정확히 'm'개 있는 순열들의 개수를 의미한다. 오일러 다항식은 오일러 수를 계수로 하는 다항식으로, 지수 생성 함수를 통해 정의되기도 한다. 오일러 수는 명시적인 공식을 통해 계산할 수 있으며, 재귀 관계를 이용하여 더 큰 값에 대해서도 계산이 가능하다. 오일러 수는 오일러 삼각형 또는 오일러의 삼각형이라 불리는 삼각 배열 형태로 나타낼 수 있으며, 파스칼의 삼각형과 유사한 특징을 공유한다. 또한, 오일러 수는 합 공식, Worpitzky 항등식, 교대 합 공식 등 다양한 항등식을 만족하며, 수열의 거듭제곱의 생성 함수와도 관련이 있다. 2차 오일러 수는 멀티셋의 순열에서 상승의 개수를 계산하며, 2차 오일러 다항식과 재귀 관계를 통해 정의된다.

2. 정의

오일러 수(Eulerian number)는 다음 식으로 정의된다.

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

$A(n,m)$ 또는 $E(n,m)$으로 표기하기도 한다. 오일러 수는 순열을 이용하거나, 오일러 다항식을 이용하여 정의할 수 있다.

2.1. 순열을 이용한 정의

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

2.2. 다항식을 이용한 정의

오일러 다항식 $A\_n(x)$은 오일러 수를 계수로 하는 다항식이다.
:$A\_n(x)=\backslash sum\_\{m=0\}^n\backslash left\backslash langle\{n\backslash atop\; m\}\backslash right\backslash rangle\; x^m$

오일러 다항식 $A\_n(t)$의 지수 생성 함수는 다음과 같다.
:$\backslash sum\_\{n=0\}^\{\backslash infty\}\; A\_\{n\}(t)\; \backslash ,\backslash frac\{x^n\}\{n!\}\; =\; \backslash frac\{t-1\}\{t\; -\; e^\{(t-1)\backslash ,x\}\}.$

오일러 수 $A(n,k)$는 오일러 다항식의 계수로 정의할 수 있다.
:$A\_\{n\}(t)\; =\; \backslash sum\_\{k=0\}^n\; A(n,k)\backslash ,t^k.$

$A(n,k)$에 대한 명시적 공식은 다음과 같다.
:

:$A(n,k)=\backslash sum\_\{i=0\}^\{k\}(-1)^i\; \backslash binom\{n+1\}\{i\}\; (k+1-i)^n.$

3. 역사

오일러 수와 오일러 다항식은 1755년 레온하르트 오일러의 저서 《미분학의 기초 및 유한 해석과 급수에 대한 응용》(Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum^라틴어)에서 처음 등장한다. 이 책에 나오는 다항식 $\backslash alpha\_1(x)$, $\backslash alpha\_2(x)$ 등은 오늘날의 오일러 다항식과는 약간 다르지만, 기본적으로 같은 대상이다.

4. 성질

낮은 차수의 오일러 수는 다음과 같다. 이러한 표를 오일러 삼각형이라고 하며, 파스칼 삼각형과 여러 유사한 성질을 가진다. n번째 행의 수들의 합은 $n!$이다.

$0\; \backslash le\; n\; \backslash le\; 9$에 대한 $A(n,\; k)$의 값은 위 표와 같다.

4.1. 기본 성질

* 고정된 n에 대해 상승이 0개인 순열은 (n, n-1, n-2, …, 1) 하나뿐이다. 실제로 모든 $n$에 대해 $\{\backslash tbinom\; n\; 0\}=1$이므로, $A(n,\; 0)\; =\; 1$이다. 이는 숫자들의 빈 집합($n=0$)을 형식적으로 포함한다. 따라서 $A\_0(t)=A\_1(t)=1$이다.
* $k=1$일 때, 명시적 공식은 $A(n,1)=2^n-(n+1)$이며, 이는 $n$에 대한 수열로 0, 0, 1, 4, 11, 26, 57, …로 나타난다.
* k개의 상승을 가진 순열을 완전히 뒤집으면 n-k-1개의 상승을 가진 다른 순열이 만들어진다. 따라서 $A(n,\; k)\; =\; A(n,\; n-k-1)$이다. 그러므로 n-1개의 상승을 가진 순열도 (1, 2, …, n) 하나뿐이며, $A(n,\; n-1)$ 또한 1이다.
* 과도한 상한은 $A(n,\; k)\; \backslash le\; (k+1)^n\backslash cdot(n+2)^k$이다. 방금 논의한 경계 사이에서, 값은 1을 초과한다.
* $k\backslash ge\; n\; >\; 0$일 때, 값은 형식적으로 0이다. 이는 $k$에 대한 많은 합이 상한 지수를 $n-1$까지만 쓸 수 있음을 의미한다. 또한 다항식 $A\_\{n\}(t)$가 $n>0$에 대해 실제로 차수 $n-1$임을 의미한다.

삼각 배열의 숫자 표는 오일러 삼각형 또는 오일러의 삼각형이라고 하며, 파스칼의 삼각형과 몇 가지 공통적인 특징을 공유한다. $0\; \backslash le\; n\; \backslash le\; 9$에 대한 $A(n,\; k)$의 값은 다음과 같다.

4.2. 오일러 삼각형

파스칼 삼각형과 여러 유사한 성질을 가지는 오일러 삼각형은 다음과 같다.

오일러 삼각형의 n번째 행의 수들의 합은 $n!$이다.

고정된 $n$에 대해 상승이 0개인 순열은 (n, n-1, n-2, ..., 1) 하나뿐이다. k개의 상승을 가진 순열을 뒤집으면 n-k-1개의 상승을 가진 순열이 생성되므로, $A(n,\; k)\; =\; A(n,\; n-k-1)$이다. 따라서 n-1개의 상승을 가진 순열도 (1, 2, ..., n) 하나뿐이다. $k=1$에 대한 명시적 공식은 $A(n,1)=2^n-(n+1)$이며, 이는 n에 대한 수열로 0, 0, 1, 4, 11, 26, 57, ... 로 나타낸다.

5. 계산

오일러 수 $A(n,k)$는 재귀 공식을 이용하여 계산할 수 있다. 이 공식은 조합론적 정의에서 비롯된다. 작은 값의 n과 k에 대해서는 손으로 계산할 수 있으며, 더 큰 값의 $n$에 대해서는 재귀 공식을 이용한다.

5.1. 재귀적 공식

$A(n,k)=(n-k)A(n-1,k-1)\; +\; (k+1)A(n-1,k)$의 재귀 공식을 사용하여 더 큰 $n$에 대한 $A(n,k)$를 계산할 수 있다. 이 공식은 조합론적 정의에서 비롯된다.

작은 $n$과 $k$ 값에 대해 $A(n,k)$의 값을 손으로 계산할 수 있다.

재귀 공식을 적용하면, $A(4,1)=(4-1)A(3,0)\; +\; (1+1)A(3,1)=3\; \backslash cdot\; 1\; +\; 2\; \backslash cdot\; 4\; =\; 11$을 얻을 수 있다.

오일러 다항식은 다음 재귀식으로 계산할 수 있다.

:$A\_\{0\}(t)\; =\; 1,$
:$A\_\{n\}(t)\; =\; A\_\{n-1\}\text{'}(t)\backslash cdot\; t(1-t)\; +\; A\_\{n-1\}(t)\backslash cdot\; (1+(n-1)t),\backslash text\{\; for\; \}\; n\; >\; 1.$

두 번째 공식은 귀납적 형태로 표현될 수 있다.

:$A\_\{n\}(t)\; =\; \backslash sum\_\{k=0\}^\{n-1\}\; \backslash binom\{n\}\{k\}\; A\_\{k\}(t)\backslash cdot\; (t-1)^\{n-1-k\},\; \backslash text\{\; for\; \}\; n\; >\; 1.$

5.2. 오일러 다항식의 재귀식

:$A(n,k)=(n-k)\backslash ,A(n-1,k-1)\; +\; (k+1)\backslash ,A(n-1,k)$

이 공식은 조합론적 정의에서 비롯될 수 있으며, 따라서 이론의 자연스러운 출발점을 제공한다.

작은 값의 n과 k에 대해, $A(n,k)$의 값은 손으로 계산할 수 있다. 예를 들어 아래 표와 같다.

재귀 공식을 한 예에 적용하면 다음을 얻을 수 있다.

:$A(4,1)=(4-1)\backslash ,A(3,0)\; +\; (1+1)\backslash ,A(3,1)=3\; \backslash cdot\; 1\; +\; 2\; \backslash cdot\; 4\; =\; 11.$

마찬가지로, 오일러 다항식은 다음 재귀식으로 계산할 수 있다.

:$A\_\{0\}(t)\; =\; 1,$
:$A\_\{n\}(t)\; =\; A\_\{n-1\}\text{'}(t)\backslash cdot\; t\backslash ,(1-t)\; +\; A\_\{n-1\}(t)\backslash cdot\; (1+(n-1)\backslash ,t),\backslash text\{\; for\; \}\; n\; >\; 1.$

두 번째 공식은 귀납적 형태로 표현될 수 있다.

:$A\_\{n\}(t)\; =\; \backslash sum\_\{k=0\}^\{n-1\}\; \backslash binom\{n\}\{k\}\; A\_\{k\}(t)\backslash cdot\; (t-1)^\{n-1-k\},\; \backslash text\{\; for\; \}\; n\; >\; 1.$

6. 항등식

오일러 수는 여러 항등식에서 나타난다.

* 유한 집합의 분할 성질에 의해, 오일러 수의 합은 계승이 된다.
* 보르피츠키(Worpitzky) 항등식은 xⁿ을 이항 계수와 오일러 수의 선형 결합으로 표현한다.

6.1. 합 공식

유한 집합을 유한 개의 더 작은 집합으로 분할하는 모든 속성에 대해, 더 작은 집합들의 기수의 합은 더 큰 집합의 기수와 같다. 오일러 수는 $n$개의 원소의 순열을 분할하므로, 그 합은 계승 $n!$과 같다. 즉, 다음과 같다.

:$\backslash sum\_\{k=0\}^\{n-1\}\; A(n,k)\; =\; n!,\; \backslash text\{\; for\; \}n\; >\; 0.$

그리고 $A(0,0)=0!$이다. 빈 합 규칙과의 충돌을 피하기 위해, $n>0$에 대한 정리를 서술한다.

훨씬 더 일반적으로, 구간 $(0,\; n)$에서 적분 가능한 고정 함수 $f\backslash colon\; \backslash mathbb\{R\}\; \backslash rightarrow\; \backslash mathbb\{C\}$에 대해 다음이 성립한다.

:$\backslash sum\_\{k=0\}^\{n-1\}\; A(n,\; k)\backslash ,\; f(k)\; =\; n!\backslash int\_0^1\; \backslash cdots\; \backslash int\_0^1\; f\backslash left(\backslash left\backslash lfloor\; x\_1\; +\; \backslash cdots\; +\; x\_n\backslash right\backslash rfloor\backslash right)\; \{\backslash mathrm\; d\}x\_1\; \backslash cdots\; \{\backslash mathrm\; d\}x\_n$

보르피츠키 항등식은 $x^n$을 이항 계수와 함께 오일러 수의 선형 결합으로 표현한다.

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

이로부터 다음이 유도된다.

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

6.2. Worpitzky 항등식

유한 집합을 유한 개의 더 작은 집합으로 분할하는 모든 속성에 대해, 더 작은 집합들의 기수의 합은 더 큰 집합의 기수와 같다. 오일러 수는 $n$개의 원소의 순열을 분할하므로, 그 합은 계승 $n!$과 같다. 즉, 다음이 성립한다.
:$\backslash sum\_\{k=0\}^\{n-1\}\; A(n,k)\; =\; n!,\; \backslash text\{\; for\; \}n\; >\; 0.$
그리고 $A(0,0)=0!$이다. 빈 합 규칙과의 충돌을 피하기 위해, $n>0$에 대한 정리만 나타내는 것이 편리하다.

훨씬 더 일반적으로, 구간 $(0,\; n)$에서 적분 가능한 고정 함수 $f\backslash colon\; \backslash mathbb\{R\}\; \backslash rightarrow\; \backslash mathbb\{C\}$에 대해 다음이 성립한다.
:$\backslash sum\_\{k=0\}^\{n-1\}\; A(n,\; k)\backslash ,\; f(k)\; =\; n!\backslash int\_0^1\; \backslash cdots\; \backslash int\_0^1\; f\backslash left(\backslash left\backslash lfloor\; x\_1\; +\; \backslash cdots\; +\; x\_n\backslash right\backslash rfloor\backslash right)\; \{\backslash mathrm\; d\}x\_1\; \backslash cdots\; \{\backslash mathrm\; d\}x\_n$
보르피츠키 항등식은 $x^n$을 이항 계수와 함께 오일러 수의 선형 결합으로 표현한다.
:$\backslash sum\_\{k=0\}^\{n-1\}A(n,k)\backslash binom\{x+k\}\{n\}=x^n.$
보르피츠키 항등식으로부터 다음이 유도된다.
:$\backslash sum\_\{k=1\}^\{m\}k^n=\backslash sum\_\{k=0\}^\{n-1\}\; A(n,k)\; \backslash binom\{m+k+1\}\{n+1\}.$

6.3. 교대 합 공식

유한 집합을 유한 개의 더 작은 집합으로 분할하는 모든 속성에 대해, 더 작은 집합들의 기수의 합은 더 큰 집합의 기수와 같다. 오일러 수는 $n$개의 원소의 순열을 분할하므로, 그 합은 계승 $n!$과 같다. 즉,

:$\backslash sum\_\{k=0\}^\{n-1\}\; A(n,k)\; =\; n!,\; \backslash text\{\; for\; \}n\; >\; 0.$

그리고 $A(0,0)=0!$이다. 빈 합 규칙과의 충돌을 피하기 위해, $n>0$에 대한 정리를 서술한다.

훨씬 더 일반적으로, 구간 $(0,\; n)$에서 적분 가능한 고정 함수 $f\backslash colon\; \backslash mathbb\{R\}\; \backslash rightarrow\; \backslash mathbb\{C\}$에 대해

:$\backslash sum\_\{k=0\}^\{n-1\}\; A(n,\; k)\backslash ,\; f(k)\; =\; n!\backslash int\_0^1\; \backslash cdots\; \backslash int\_0^1\; f\backslash left(\backslash left\backslash lfloor\; x\_1\; +\; \backslash cdots\; +\; x\_n\backslash right\backslash rfloor\backslash right)\; \{\backslash mathrm\; d\}x\_1\; \backslash cdots\; \{\backslash mathrm\; d\}x\_n$

보르피츠키 항등식은 $x^n$을 이항 계수와 함께 오일러 수의 선형 결합으로 표현한다.

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

이로부터 다음이 따른다.

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

고정된 $n$에 대한 오일러 수의 교대합은 베르누이 수 $B\_\{n+1\}$과 관련이 있다.

:$\backslash sum\_\{k=0\}^\{n-1\}(-1)^k\; A(n,k)\; =\; 2^\{n+1\}(2^\{n+1\}-1)\; \backslash frac\{B\_\{n+1\}\}\{n+1\},\; \backslash text\{\; for\; \}n\; >\; 0.$

또한,

:$\backslash sum\_\{k=0\}^\{n-1\}(-1)^k\; \backslash frac\{A(n,k)\}\{\backslash binom\{n-1\}\{k\}\}=0,\; \backslash text\{\; for\; \}n\; >\; 1$

그리고

:$\backslash sum\_\{k=0\}^\{n-1\}(-1)^k\; \backslash frac\{A(n,k)\}\{\backslash binom\{n\}\{k\}\}=(n+1)B\_\{n\},\; \backslash text\{\; for\; \}\; n\; >\; 1$

6.4. 다항식 관련 공식

유한 집합을 유한 개의 더 작은 집합으로 분할하는 모든 속성에 대해, 더 작은 집합들의 기수의 합은 더 큰 집합의 기수와 같습니다. 오일러 수는 $n$개의 원소의 순열을 분할하므로, 그 합은 계승 $n!$과 같습니다. 즉,
:$\backslash sum\_\{k=0\}^\{n-1\}\; A(n,k)\; =\; n!,\; \backslash text\{\; for\; \}n\; >\; 0.$
그리고 $A(0,0)=0!$입니다. 빈 합 규칙과의 충돌을 피하기 위해, $n>0$에 대한 정리를 서술합니다.

구간 $(0,\; n)$에서 적분 가능한 고정 함수 $f\backslash colon\; \backslash mathbb\{R\}\; \backslash rightarrow\; \backslash mathbb\{C\}$에 대해,
:$\backslash sum\_\{k=0\}^\{n-1\}\; A(n,\; k)\backslash ,\; f(k)\; =\; n!\backslash int\_0^1\; \backslash cdots\; \backslash int\_0^1\; f\backslash left(\backslash left\backslash lfloor\; x\_1\; +\; \backslash cdots\; +\; x\_n\backslash right\backslash rfloor\backslash right)\; \{\backslash mathrm\; d\}x\_1\; \backslash cdots\; \{\backslash mathrm\; d\}x\_n$

보르피츠키 항등식은 $x^n$을 이항 계수와 함께 오일러 수의 선형 결합으로 표현합니다.
:$\backslash sum\_\{k=0\}^\{n-1\}A(n,k)\backslash binom\{x+k\}\{n\}=x^n.$
이로부터 다음이 유도됩니다.
:$\backslash sum\_\{k=1\}^\{m\}k^n=\backslash sum\_\{k=0\}^\{n-1\}\; A(n,k)\; \backslash binom\{m+k+1\}\{n+1\}.$

오일러 다항식의 대칭성은 다음을 의미합니다.
:$A\_n(t)\; =\; t^\{n-1\}\; A\_n(t^\{-1\})$

오일러 수는 수열의 n^th 거듭제곱의 생성 함수에 포함됩니다.
:$\backslash sum\_\{i=1\}^\backslash infty\; i^n\; x^i\; =\; \backslash frac\{1\}\{(1-x)^\{n+1\}\}\backslash sum\_\{k=0\}^n\; A(n,k)\backslash ,x^\{k+1\}\; =\; \backslash frac\{x\}\{(1-x)^\{n+1\}\}A\_n(x)$

오일러 다항식에 대한 명시적인 표현은 다음과 같습니다.

$A\_n(t)\; =\; \backslash sum\_\{k=0\}^n\; \backslash left\backslash \{\; \{n\; \backslash atop\; k\}\; \backslash right\backslash \}\; k!\; (t-1)^\{n-k\}$

여기서 $\backslash left\backslash \{\; \{n\; \backslash atop\; k\}\; \backslash right\backslash \}$는 제2종 스털링 수입니다.

7. 2차 오일러 수

2차 오일러 수는 멀티셋 {1, 1, 2, 2, ..., n, n}의 순열 중, 'k'의 두 번의 출현 사이에 나타나는 모든 숫자가 'k'보다 큰 속성을 가진 순열에서, 정확히 m개의 상승을 갖는 순열의 수를 나타낸다. 2차 오일러 수와 관련된 내용은 다음 세 가지 방식으로 인덱싱되어 제공된다.

* Riordan과 Comtet를 따름
* Graham, Knuth 및 Patashnik을 따름
* Gessel과 Stanley의 정의를 확장

7.1. 정의

멀티셋 {1, 1, 2, 2, \ldots, n, n}의 순열에서, k의 두 번의 출현 사이에 나타나는 모든 숫자가 k보다 큰 속성을 가진 순열은 이중 계승 수 (2n-1)!!로 계산된다.

2차 오일러 수 $\backslash scriptstyle\; \backslash left\backslash langle\; \backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; m\}\; \backslash right\backslash rangle\; \backslash !\; \backslash right\backslash rangle$는 정확히 m개의 상승을 갖는 모든 그러한 순열의 수를 계산한다. 예를 들어, n = 3인 경우 그러한 순열은 15개이며, 상승이 없는 순열 1개, 상승이 1개인 순열 8개, 상승이 2개인 순열 6개가 있다.

: 332211,
: 221133, 221331, 223311, 233211, 113322, 133221, 331122, 331221,
: 112233, 122133, 112332, 123321, 133122, 122331.

2차 오일러 수는 다음 재귀 관계를 만족하며, 이는 위 정의에서 직접 파생된다.

:$\backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; =\; (2n-k-1)\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n-1\; \backslash atop\; k-1\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; +\; (k+1)\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n-1\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle,$

아이버슨 괄호 표기법으로 표현된 n = 0에 대한 초기 조건은 다음과 같다.

:$\backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{0\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; =\; [k=0].$

이에 따라, 2차 오일러 다항식은 P_n으로 표시된다(이에 대한 표준 표기법은 없다).

:$P\_n(x)\; :=\; \backslash sum\_\{k=0\}^n\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; x^k$

위의 재귀 관계는 수열 P_n(x)에 대한 재귀 관계로 변환된다.

:$P\_\{n+1\}(x)\; =\; (2nx+1)\; P\_n(x)\; -\; x(x-1)\; P\_n^\backslash prime(x)$

초기 조건은 $P\_0(x)\; =\; 1$이다. 후자의 재귀 관계는 적분 인수를 사용하여 약간 더 간결한 형태로 작성할 수 있다.

:$(x-1)^\{-2n-2\}\; P\_\{n+1\}(x)\; =\; \backslash left(\; x\backslash ,(1-x)^\{-2n-1\}\; P\_n(x)\; \backslash right)^\backslash prime$

따라서 유리 함수

:$u\_n(x)\; :=\; (x-1)^\{-2n\}\; P\_\{n\}(x)$

는 단순한 자율 재귀를 만족한다.

:$u\_\{n+1\}\; =\; \backslash left(\; \backslash frac\{x\}\{1-x\}\; u\_n\; \backslash right)^\backslash prime,\; \backslash quad\; u\_0=1$

여기에서 2차 오일러 다항식은 $P\_n(x)\; =\; (1-x)^\{2n\}\; u\_n(x)$로, 2차 오일러 수는 해당 계수로 얻는다.

다음 표는 처음 몇 개의 2차 오일러 수를 표시한다.

n번째 행의 합, 즉 $P\_n(1)$의 값은 $(2n-1)!!$이다.

2차 오일러 수의 인덱싱은 세 가지 방식으로 제공된다.

* Riordan과 Comtet를 따름
* Graham, Knuth 및 Patashnik을 따름
* , Gessel과 Stanley의 정의를 확장

7.2. 재귀 관계

멀티셋 $\backslash \{1,\; 1,\; 2,\; 2,\; \backslash ldots,\; n,\; n\backslash \}$의 순열에서 k의 두 번의 출현 사이에 나타나는 모든 숫자가 k보다 큰 속성을 가진 순열은 이중 계승 수 $(2n-1)!!$로 계산된다. 2차 오일러 수 $\backslash scriptstyle\; \backslash left\backslash langle\; \backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; m\}\; \backslash right\backslash rangle\; \backslash !\; \backslash right\backslash rangle$는 정확히 m개의 상승을 갖는 모든 그러한 순열의 수를 나타낸다. 예를 들어 n = 3인 경우, 그러한 순열은 15개이며, 상승이 없는 순열 1개, 상승이 1개인 순열 8개, 상승이 2개인 순열 6개가 있다.

: 332211,
: 221133, 221331, 223311, 233211, 113322, 133221, 331122, 331221,
: 112233, 122133, 112332, 123321, 133122, 122331.

2차 오일러 수는 다음 재귀 관계를 만족하며, 이는 위 정의에서 직접 유도된다.
:$\backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; =\; (2n-k-1)\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n-1\; \backslash atop\; k-1\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; +\; (k+1)\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n-1\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle,$
아이버슨 괄호 표기법으로 표현된 n = 0에 대한 초기 조건은 다음과 같다.
:$\backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{0\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; =\; [k=0].$
이에 따라, 2차 오일러 다항식은 P_n으로 표시된다(이에 대한 표준 표기법은 없다).
:$P\_n(x)\; :=\; \backslash sum\_\{k=0\}^n\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; x^k$
위의 재귀 관계는 수열 P_n(x)에 대한 다음 재귀 관계로 변환된다.
:$P\_\{n+1\}(x)\; =\; (2nx+1)\; P\_n(x)\; -\; x(x-1)\; P\_n^\backslash prime(x)$
초기 조건은 $P\_0(x)\; =\; 1$이다. 후자의 재귀 관계는 적분 인수를 사용하여 다음과 같이 더 간결한 형태로 작성할 수 있다.
:$(x-1)^\{-2n-2\}\; P\_\{n+1\}(x)\; =\; \backslash left(\; x\backslash ,(1-x)^\{-2n-1\}\; P\_n(x)\; \backslash right)^\backslash prime$
따라서 유리 함수
:$u\_n(x)\; :=\; (x-1)^\{-2n\}\; P\_\{n\}(x)$
는 다음의 자율 재귀를 만족한다.
:$u\_\{n+1\}\; =\; \backslash left(\; \backslash frac\{x\}\{1-x\}\; u\_n\; \backslash right)^\backslash prime,\; \backslash quad\; u\_0=1$
여기에서 2차 오일러 다항식은 $P\_n(x)\; =\; (1-x)^\{2n\}\; u\_n(x)$로, 2차 오일러 수는 해당 계수로 얻어진다.

다음 표는 처음 몇 개의 2차 오일러 수를 나타낸다.

n번째 행의 합, 즉 $P\_n(1)$의 값은 $(2n-1)!!$이다.

2차 오일러 수의 인덱싱은 세 가지 방식으로 제공된다.

7.3. 2차 오일러 다항식

멀티셋 \{1, 1, 2, 2, \ldots, n, n\}의 순열에서, k의 두 번의 출현 사이에 나타나는 모든 숫자가 k보다 큰 속성을 가진 순열은 이중 계승 수 (2n-1)!!로 계산된다.

2차 오일러 수 $\backslash scriptstyle\; \backslash left\backslash langle\; \backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; m\}\; \backslash right\backslash rangle\; \backslash !\; \backslash right\backslash rangle$는 정확히 m개의 상승을 갖는 모든 그러한 순열의 수를 나타낸다. 예를 들어 n = 3인 경우, 그러한 순열은 15개이며, 상승이 없는 순열 1개, 상승이 1개인 순열 8개, 상승이 2개인 순열 6개가 있다.

: 332211,
: 221133, 221331, 223311, 233211, 113322, 133221, 331122, 331221,
: 112233, 122133, 112332, 123321, 133122, 122331.

2차 오일러 수는 다음 재귀 관계를 만족하며, 이는 위 정의에서 직접 유도된다.
:$\backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; =\; (2n-k-1)\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n-1\; \backslash atop\; k-1\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; +\; (k+1)\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n-1\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle,$
아이버슨 괄호 표기법으로 표현된 n = 0에 대한 초기 조건은 다음과 같다.
:$\backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{0\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; =\; [k=0].$
이에 따라, 2차 오일러 다항식 P_n(표준 표기법은 없음)은 다음과 같이 정의된다.
:$P\_n(x)\; :=\; \backslash sum\_\{k=0\}^n\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; x^k$
위의 재귀 관계는 수열 P_n(x)에 대한 재귀 관계로 변환된다.
:$P\_\{n+1\}(x)\; =\; (2nx+1)\; P\_n(x)\; -\; x(x-1)\; P\_n^\backslash prime(x)$
초기 조건은 $P\_0(x)\; =\; 1$이다. 후자의 재귀 관계는 적분 인수를 사용하여 더 간결하게 표현할 수 있다.
:$(x-1)^\{-2n-2\}\; P\_\{n+1\}(x)\; =\; \backslash left(\; x\backslash ,(1-x)^\{-2n-1\}\; P\_n(x)\; \backslash right)^\backslash prime$
따라서 유리 함수
:$u\_n(x)\; :=\; (x-1)^\{-2n\}\; P\_\{n\}(x)$
는 단순한 자율 재귀를 만족한다.
:$u\_\{n+1\}\; =\; \backslash left(\; \backslash frac\{x\}\{1-x\}\; u\_n\; \backslash right)^\backslash prime,\; \backslash quad\; u\_0=1$
여기에서 2차 오일러 다항식은 $P\_n(x)\; =\; (1-x)^\{2n\}\; u\_n(x)$로, 2차 오일러 수는 해당 계수로 얻어진다.

다음 표는 처음 몇 개의 2차 오일러 수를 나타낸다.

n번째 행의 합, 즉 $P\_n(1)$의 값은 $(2n-1)!!$이다.

2차 오일러 수의 인덱싱은 세 가지 방식으로 제공된다.
* Riordan과 Comtet를 따름
* Graham, Knuth 및 Patashnik을 따름
* Gessel과 Stanley의 정의를 확장

7.4. 표

n번째 행의 합, 즉 $P\_n(1)$의 값은 이중 계승 $(2n-1)!!$이다.

7.5. 인덱싱

멀티셋 $\backslash \{1,\; 1,\; 2,\; 2,\; \backslash ldots,\; n,\; n\backslash \}$의 순열 중, k의 두 번의 출현 사이에 나타나는 모든 숫자가 k보다 큰 속성을 가진 순열은 이중 계승 수 $(2n-1)!!$로 계산된다. 2차 오일러 수 $\backslash scriptstyle\; \backslash left\backslash langle\; \backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; m\}\; \backslash right\backslash rangle\; \backslash !\; \backslash right\backslash rangle$는 정확히 m개의 상승을 갖는 모든 그러한 순열의 수를 계산한다. 예를 들어 n = 3인 경우, 그러한 순열은 15개이며, 상승이 없는 순열 1개, 상승이 1개인 순열 8개, 상승이 2개인 순열 6개가 있다.

: 332211,
: 221133, 221331, 223311, 233211, 113322, 133221, 331122, 331221,
: 112233, 122133, 112332, 123321, 133122, 122331.

2차 오일러 수는 다음 재귀 관계를 만족하며, 이는 위 정의에서 직접 파생된다.
:$\backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; =\; (2n-k-1)\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n-1\; \backslash atop\; k-1\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; +\; (k+1)\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n-1\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle,$
아이버슨 괄호 표기법으로 표현된 n = 0에 대한 초기 조건:
:$\backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{0\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; =\; [k=0].$
이에 따라, 2차 오일러 다항식은 P_n으로 표시된다(이에 대한 표준 표기법은 없다).
:$P\_n(x)\; :=\; \backslash sum\_\{k=0\}^n\; \backslash left\backslash langle\; \backslash !\backslash !\; \backslash left\backslash langle\; \{n\; \backslash atop\; k\}\; \backslash right\backslash rangle\; \backslash !\backslash !\; \backslash right\backslash rangle\; x^k$
위의 재귀 관계는 수열 P_n(x)에 대한 재귀 관계로 변환된다.
:$P\_\{n+1\}(x)\; =\; (2nx+1)\; P\_n(x)\; -\; x(x-1)\; P\_n^\backslash prime(x)$
초기 조건 $P\_0(x)\; =\; 1.$이다. 후자의 재귀 관계는 적분 인수를 사용하여 약간 더 간결한 형태로 작성할 수 있다.
:$(x-1)^\{-2n-2\}\; P\_\{n+1\}(x)\; =\; \backslash left(\; x\backslash ,(1-x)^\{-2n-1\}\; P\_n(x)\; \backslash right)^\backslash prime$
따라서 유리 함수
:$u\_n(x)\; :=\; (x-1)^\{-2n\}\; P\_\{n\}(x)$
는 단순한 자율 재귀를 만족한다.
:$u\_\{n+1\}\; =\; \backslash left(\; \backslash frac\{x\}\{1-x\}\; u\_n\; \backslash right)^\backslash prime,\; \backslash quad\; u\_0=1$
여기에서 2차 오일러 다항식은 $P\_n(x)\; =\; (1-x)^\{2n\}\; u\_n(x)$로, 2차 오일러 수는 해당 계수로 얻는다.

다음 표는 처음 몇 개의 2차 오일러 수를 표시한다.

n번째 행의 합, 즉 $P\_n(1)$의 값은 $(2n-1)!!$이다.

2차 오일러 수의 인덱싱은 세 가지 방식으로 제공된다.
* Riordan과 Comtet를 따름
* Graham, Knuth 및 Patashnik을 따름
* , Gessel과 Stanley의 정의를 확장