Числа Эйлера II рода

Числа Эйлера II рода (англ. Eulerian numbers of the second kind) — количество перестановок мультимножества $\text{[math]}$ $\text{[math]}$ $\{1,1,2,2,...,n,n\}$ $\{1,1,2,2,...,n,n\}$ , обладающие тем свойством, что для каждого $\text{[math]}$ $\text{[math]}$ $k$ $k$ подсчитываются все числа, встречающиеся между двумя вхождениями $\text{[math]}$ $\text{[math]}$ $k$ $k$ в перестановке, больше, чем $\text{[math]}$ $\text{[math]}$ $k$ $k$ по двойному факториальному числу $\text{[math]}$ $\text{[math]}$ $({\text{2n-1}})!!$ $({\text{2n-1}})!!$ .

ПримерПравить

Число Эйлера второго рода, обозначаемое $\text{[math]}$ $\text{[math]}$ $\left\langle {\left\langle {n \atop m}\right\rangle }\right\rangle$ , подсчитывает количество всех таких перестановок, которые имеют ровно $\text{[math]}$ $\text{[math]}$ $m$ восхождений. Например, для $\text{[math]}$ $\text{[math]}$ $n=3$ существует $\text{[math]}$ $\text{[math]}$ $15$ таких перестановок, $\text{[math]}$ $\text{[math]}$ $1$ без подъемов, $\text{[math]}$ $\text{[math]}$ $8$ с одним подъемом и $\text{[math]}$ $\text{[math]}$ $6$ с двумя подъемами:

$\text{[math]}$ $\text{[math]}$ $332211,$

$\text{[math]}$ $\text{[math]}$ $221133,221331,223311,233211,113322,133221,331122,331221,$

$\text{[math]}$ $\text{[math]}$ $112233,122133,112332,123321,133122,122331.$

Рекуррентное соотношениеПравить

Числа Эйлера второго рода удовлетворяют рекуррентному соотношению, которое непосредственно следует из приведенного выше определения:

$\text{[math]}$ $\text{[math]}$ $\left\langle {\left\langle {n \atop m}\right\rangle }\right\rangle =(2n-m-1)\left\langle {\left\langle {n-1 \atop m-1}\right\rangle }\right\rangle +(m+1)\left\langle {\left\langle {n-1 \atop m}\right\rangle }\right\rangle$ ,

c начальным условием для $\text{[math]}$ $\text{[math]}$ $n=0$ , выраженным в скобках Иверсона:

$\text{[math]}$ $\text{[math]}$ $\left\langle {\left\langle {0 \atop m}\right\rangle }\right\rangle =[m=0]$ .

Соответственно, полином Эйлера второго рода, обозначаемый здесь $\text{[math]}$ $\text{[math]}$ $P_{n}$ (для них не существует стандартных обозначений) $\text{[math]}$ $\text{[math]}$ $P_{n}(x)=\sum _{m=0}^{n}{\left\langle {\left\langle {n \atop m}\right\rangle }\right\rangle }x^{m}$ и вышеупомянутые рекуррентные отношения переводятся в рекуррентное отношение для последовательности $\text{[math]}$ $\text{[math]}$ $P_{n}(x)$ :

$\text{[math]}$ $\text{[math]}$ $P_{n+1}(x)=(2nx+1)P_{n}(x)-x(x-1)P'_{n}(x)$

С начальным условием $\text{[math]}$ $\text{[math]}$ $P_{0}(x)=1$ .

Последнее повторение может быть записано в несколько более компактной форме с помощью интегрирующего фактора:

$\text{[math]}$ $\text{[math]}$ $(x-1)^{-2n-2}P_{n+1}(x)=(x(1-x)^{-2n-1}P_{n}(x)')$

так что рациональная функция

\text{[math]}

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

удовлетворяет простой автономный рецидив:

\text{[math]}

u_{n+1}=\left({\frac {x}{1-x}}u_{n}\right)'

,

\text{[math]}

u_{0}=1

,

откуда можно получить эйлеровы многочлены в виде $\text{[math]}$ $\text{[math]}$ $P_{n}(x)=(1-x)^{2n}$ и $\text{[math]}$ $\text{[math]}$ $u_{n}(x)$ и числа Эйлера второго рода в качестве их коэффициентов.

Треугольник чисел Эйлера II родаПравить


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

Сумма $\text{[math]}$ $\text{[math]}$ $n$ –ой строки, которая также является значением $\text{[math]}$ $\text{[math]}$ $P_{n}(1)$ , равна $\text{[math]}$ $\text{[math]}$ $({\text{2n-1}})!!$ .

См. такжеПравить

СсылкиПравить

Eulerian number — Wikipedia
Weisstein, Eric W. Euler's Number Triangle (англ.) на сайте Wolfram MathWorld.
Числа Эйлера
Weisstein, Eric W. Треугольник чисел Эйлера II рода (англ.) на сайте Wolfram MathWorld.