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

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

Пример

Число Эйлера второго рода, обозначаемое $⟨ ⟨ \binom{n}{m} ⟩ ⟩$ , подсчитывает количество всех таких перестановок, которые имеют ровно $m$ восхождений. Например, для $n = 3$ существует $15$ таких перестановок, $1$ без подъемов, $8$ с одним подъемом и $6$ с двумя подъемами:

$332211,$

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

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

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

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

$⟨ ⟨ \binom{n}{m} ⟩ ⟩ = (2 n - m - 1) ⟨ ⟨ \binom{n - 1}{m - 1} ⟩ ⟩ + (m + 1) ⟨ ⟨ \binom{n - 1}{m} ⟩ ⟩$ ,

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

$⟨ ⟨ \binom{0}{m} ⟩ ⟩ = [m = 0]$ .

Соответственно, полином Эйлера второго рода, обозначаемый здесь $P_{n}$ (для них не существует стандартных обозначений) $P_{n} (x) = \sum_{m = 0}^{n} ⟨ ⟨ \binom{n}{m} ⟩ ⟩ x^{m}$ и вышеупомянутые рекуррентные отношения переводятся в рекуррентное отношение для последовательности $P_{n} (x)$ :

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

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

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

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

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

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

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

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

,

u_{0} = 1

,

откуда можно получить эйлеровы многочлены в виде $P_{n} (x) = (1 - x)^{2 n}$ и $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

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

См. также

Ссылки

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