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

Шаблон:Плохой перевод Чи́сла Э́йлера II ро́да обозначаются $⟨ ⟨ \binom{n}{m} ⟩ ⟩ = ⟨ ⟨ n, m ⟩ ⟩ = T (n, m + 1)$ и определяются как количество перестановок мультимножества ${1, 1, 2, 2, ..., n, n}$ , обладающих тем свойством, что для каждого $k$ подсчитываются все числа, большие чем $k$ , встречающиеся между двумя вхождениями $k$ в перестановке (таких перестановок $(2 n - 1)!!$ , где !! обозначает двойной факториал), и имеющих ровно $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} ⟩ ⟩

,

с начальным условием для $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 рода

Значения чисел Эйлера II рода $⟨ ⟨ \binom{n}{m} ⟩ ⟩$ для малых значений Шаблон:Math и Шаблон:Math приведены в следующей таблице (Шаблон: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)$ , равна $(2 n - 1)!!$ .

См. также

Ссылки

Шаблон:Примечания

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

Содержание

Пример

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

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

См. также

Ссылки

Навигация

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

Пример

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

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

См. также

Ссылки

Навигация

Поиск