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

Чи́сла Э́йлера II ро́да обозначаются $\left\langle {\left\langle {n \atop m}\right\rangle }\right\rangle =\left\langle {\left\langle n,m\right\rangle }\right\rangle =T(n,m+1)$ и определяются как количество перестановок мультимножества $\{1,1,2,2,...,n,n\}$, обладающих тем свойством, что для каждого $k$ подсчитываются все числа, большие чем $k$, встречающиеся между двумя вхождениями $k$ в перестановке (таких перестановок $(2n-1)!!$, где !! обозначает двойной факториал), и имеющих ровно $m$ «подъёмов» (элементов, бо́льших предыдущего элемента).

Пример

Например, для $n=3$ существует 15 таких перестановок, 1 без подъёмов, 8 с одним подъёмом и 6 с двумя подъёмами:

$332211,$

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

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

Рекуррентное соотношение

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

$\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$,

с начальным условием для $n=0$, выраженным в скобках Айверсона:

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

Соответственно, полином Эйлера второго рода, обозначаемый здесь $P_{n}$ (для них не существует стандартных обозначений)

$P_{n}(x)=\sum _{m=0}^{n}{\left\langle {\left\langle {n \atop m}\right\rangle }\right\rangle }x^{m}$ и вышеупомянутые рекуррентные отношения переводятся в рекуррентное отношение для последовательности $P_{n}(x)$:

$P_{n+1}(x)=(2nx+1)P_{n}(x)-x(x-1)P'_{n}(x)$

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

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

$(x-1)^{-2n-2}P_{n+1}(x)=(x(1-x)^{-2n-1}P_{n}(x)')$,

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

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

удовлетворяет простому автономному рекуррентному соотношению:

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

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

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

Значения чисел Эйлера II рода $\left\langle {\left\langle {n \atop m}\right\rangle }\right\rangle$ для малых значений n и m приведены в следующей таблице (последовательность A008517 в OEIS):

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

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

См. также

• Эйлер, Леонард
• Числа Эйлера I рода
• Рекуррентная формула

Ссылки

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