Числа Ейлера I роду

Шаблон:Otheruses В комбінаториці числом Ейлера I роду із $n$ по $k$ , що позначається $⟨ \binom{n}{k} ⟩$ чи $E (n, k)$ , називається кількість перестановок порядку $n$ з $k$ , тобто таких перестановок $π = (π_{1}, π_{2}, \dots, π_{n})$ , що існує рівно $k$ індексів $j$ , для яких $π_{j} < π_{j + 1}$ .

Числа Ейлера I роду мають також геометричну і імовірнісну інтерпретацію: число $\frac{1}{n!} ⟨ \binom{n}{k} ⟩$ виражає $n$ -мірний об'єм частини $n$ -мірного гіперкуба, обмеженого $(n - 1)$ -мірними гіперплощинами $x_{1} + x_{2} + \dots + x_{n} = k$ і $x_{1} + x_{2} + \dots + x_{n} = k - 1$ ; воно виражає імовірність того, що сума n незалежних змінних з рівномірним розподілом на відрізку $[0, 1]$ лежить між $k - 1$ $k$ .

Приклад

Перестановки $π$ четвертого порядку, повинні задовільняти одній із двох нерівностей: $π_{1} < π_{2} < π_{3} > π_{4}$ чи $π_{1} > π_{2} < π_{3} < π_{4}$ . Таких перестановок рівно 11 штук:

1324 1423 2314 2413 3412 1243 1342 2341 2134 3124 4123

Тому $⟨ \binom{4}{2} ⟩ = 11$ .

Властивості

Для заданого натурального числа $n$ існує єдина перестановка тобто $(n, n - 1, n - 2, \dots, 1)$ . Також існує єдина перестановка, яка має $n - 1$ тобто $(1, 2, 3, \dots, n - 1)$ . Таким чином,

⟨ \binom{n}{0} ⟩ = ⟨ \binom{n}{n - 1} ⟩ = 1

для всіх натуральних

n

.

Дзеркальним відображенням перестановки з $m$ є перестановка з $n - m - 1$ . Таким чином,

⟨ \binom{n}{m} ⟩ = ⟨ \binom{n}{n - m - 1} ⟩ .

Трикутник чисел Ейлера першого роду

Значення чисел Ейлера $⟨ \binom{n}{k} ⟩$ для малих значень $n$ і $k$ наведені в наступній таблиці (Шаблон:OEIS):

n/k	0	1	2	3	4	5	6	7	8	9
0	1
1	1	0
2	1	1	0
3	1	4	1	0
4	1	11	11	1	0
5	1	26	66	26	1	0
6	1	57	302	302	57	1	0
7	1	120	1191	2416	1191	120	1	0
8	1	247	4293	15619	15619	4293	247	1	0
9	1	502	14608	88234	156190	88234	14608	502	1	0

Легко зрозуміти, що значення на головній діагоналі матриці задаються формулою: $⟨ \binom{n}{n} ⟩ = [n = 0] .$

Трикутник Ейлера, як і трикутник Паскаля, симетричний зліва і справа. Але в цьому випадку закон симетрії відмінний:

$⟨ \binom{n}{k} ⟩ = ⟨ \binom{n}{n - 1 - k} ⟩$

при $n > 0$ . Тобто перестановка має $n - 1 - k$ тоді і тільки тоді, коли її «відображення» має $k$ .

Рекурентна формула

Кожна перестановка $ρ = ρ_{1} \dots ρ_{n - 1}$ із набору ${1, 2, 3, n - 1}$ приводить до $n$ перестановок вигляду ${1, 2, 3, n}$ , якщо ми вставляємо новий елемент n всіма можливими способами. Вставляючи $n$ в $j$ -ту позицію, отримуємо перестановку $π = ρ_{1} \dots ρ_{j - 1} n ρ_{j} \dots ρ_{n - 1}$ . Кількість підйомів в $ρ$ дорівнює кількості підйомів в $ρ$ , якщо $j = 1$ чи, якщо $π_{j - 1} < π_{j}$ ; і воно більше кількості підйомів в $ρ$ , якщо $j = n$ чи, якщо $ρ_{j - 1} > ρ_{j}$ . Тому, $π$ в сумі має

$(k + 1) ⟨ \binom{n - 1}{k} ⟩$

способів побудови перестановок із $ρ$ , які мають $k$ підйомів, плюс

$((n - 2) - (k - 1) + 1) ⟨ \binom{n - 1}{k - 1} ⟩$

способів побудови перестановок із $ρ$ , які мають $k - 1$ підйомів. Тоді рекурентна формула для цілих $n > 0$ має вигляд:

⟨ \binom{n}{k} ⟩ = (k + 1) ⟨ \binom{n - 1}{k} ⟩ + (n - k) ⟨ \binom{n - 1}{k - 1} ⟩ .

Покладемо також, що

$⟨ \binom{0}{k} ⟩ = [k = 0]$

(для цілих $k$ ), і припустимо, що при $k < 0$ .

Зв'язок з біноміальними коефіцієнтами і степеневими формулами

Зв'язок між звичайними степенями та узагальненими біноміальними коефіцієнтами:

x^{n} = \sum_{k} ⟨ \binom{n}{k} ⟩ (\binom{x + k}{n})

для цілих $n \geq 0$ .

x^{2} = (\binom{x}{2}) + (\binom{x + 1}{2})

x^{3} = (\binom{x}{3}) + 4 (\binom{x + 1}{3}) + (\binom{x + 2}{3})

x^{4} = (\binom{x}{4}) + 11 (\binom{x + 1}{4}) + 11 (\binom{x + 2}{4}) + (\binom{x + 3}{4})

і т. д. Ці тотожності легко доводяться методом математичної індукції.

Варто зазначити, що ця формула представляє ще один спосіб знаходження суми перших $n$ квадратів:

\sum_{k = 1}^{n} k^{2} = \sum_{k = 1}^{n} ⟨ \binom{2}{0} ⟩ (\binom{k}{2}) + ⟨ \binom{2}{1} ⟩ (\binom{k + 1}{2}) = \sum_{k = 1}^{n} (\binom{k}{2}) + (\binom{k + 1}{2}) =

= ((\binom{1}{2}) + (\binom{2}{2}) + \dots + (\binom{n}{2})) + ((\binom{2}{2}) + (\binom{3}{2}) + \dots + (\binom{n + 1}{2})) =

= (\binom{n + 1}{3}) + (\binom{n + 2}{3}) = \frac{n (n + 1) (2 n + 1)}{6} .

Явні формули для чисел Ейлера

Оскільки рекурентність для чисел Ейлера достатньо складна, вони задовільняють лише небагатьом властивостям:

⟨ \binom{n}{m} ⟩ = \sum_{k = 0}^{m} (\binom{n + 1}{k}) (m + 1 - k)^{n} (- 1)^{k}

m! {\binom{n}{m}} = \sum_{k} ⟨ \binom{n}{k} ⟩ (\binom{k}{n - m})

домножуючи першу тотожність на $z^{n - m}$ і сумуючи по $m$ , отримуємо:

\sum_{m} {\binom{n}{m}} m! z^{n - m} = \sum_{k} ⟨ \binom{n}{k} ⟩ (z + 1)^{k} .

Заміняючи $z$ на $z + 1$ і прирівнюючи коефіцієнти при $z^{k}$ , отримуємо другу тотожність. Таким чином, ці дві тотожності еквівалентні. Перша тотожність застосовується при малих значеннях $m$ :

{\binom{n}{0}} = 1;

{\binom{n}{1}} = 2^{n} - n - 1;

{\binom{n}{2}} = 3^{n} - (n + 1) 2^{n} + (\binom{n + 1}{2}) .

Сумування чисел Ейлера I роду

Із комбінаторного визначення очевидно, що сума чисел Ейлера I роду, розміщених в n-му рядку дорівнює $n!$ , оскільки вона дорівнює кількості всіх перестановок порядку $n$ :

\sum_{m = 0}^{n} ⟨ \binom{n}{m} ⟩ = n!

Знакозмінні суми чисел Ейлера I роду при фіксованому значенні n зв'язані з числами Бернуллі $B_{n + 1}$ :

\sum_{m = 0}^{n} (- 1)^{m} ⟨ \binom{n}{m} ⟩ = \frac{2^{n + 1} (2^{n + 1} - 1) B_{n + 1}}{n + 1},

\sum_{m = 0}^{n} (- 1)^{m} ⟨ \binom{n}{m} ⟩ {(\binom{n}{m})}^{- 1} = (n + 1) B_{n},

\sum_{m = 0}^{n} (- 1)^{m} ⟨ \binom{n}{m} ⟩ {(\binom{n - 1}{m})}^{- 1} = 0 .

Також справедливі такі тотожності:

\sum_{k = 0}^{n} 2^{k} ⟨ \binom{n}{k} ⟩ = \sum_{k = 1}^{\infty} \frac{k^{n}}{2^{k}} = \sum_{k = 1}^{n} k! {\binom{n}{k}}

\sum_{k = 0}^{n} 3^{k} ⟨ \binom{n}{k} ⟩ = 2^{n + 1} \sum_{k = 1}^{\infty} \frac{k^{n}}{3^{k}}

Генератриса і тотожність Ворпицького

Генератриса чисел Ейлера I роду має вигляд:

\frac{1 - w}{e^{(w - 1) z} - w} = \sum_{m, n \geq 0} ⟨ \binom{n}{m} ⟩ w^{m} \frac{z^{n}}{n!}

Числа Ейлера I роду зв'язані також з генератрисою послідовності $n$ -х степенів:

\sum_{k = 1}^{\infty} k^{n} x^{k} = \frac{\sum_{m = 0}^{n - 1} ⟨ \binom{n}{m} ⟩ x^{m + 1}}{(1 - x)^{n + 1}} .

Крім того, Z-перетворення із

{n^{k}}_{k = 1}^{N}

є генератором перших N рядків трикутник чисел Ейлера, коли знаменник $n$ -й елемента перетворення скорочується множенням на $(z - 1)^{j + 1}$ :

Z [{n^{k}}_{k = 1}^{3} = {\frac{z}{(z - 1)^{2}}, \frac{z + z^{2}}{(z - 1)^{3}}, \frac{z + 4 z^{2} + z^{3}}{(z - 1)^{4}}}]

Тотожність Ворпицького виражає $x^{n}$ як суму узагальнених біноміальних коефіцієнтів:

x^{n} = \sum_{m = 0}^{n - 1} ⟨ \binom{n}{m} ⟩ (\binom{x + m}{n}) .

Програми на PARI/GP для обчислення чисел Ейлера

\\ рекурентна формула{ E(n, k) = if(k<1|k>n, 0, if(n==1, 1, k*E(n-1,k) + (n-k+1)*E(n-1,k-1) ) ) } \\ явна формула { E(n, k) = sum(j=0, k, (-1)^j * (k-j)^n * binomial(n+1,j) ) }

Література

Шаблон:Книга
Д. Кнут. Искусство программирования. Т.1: Основные алгоритмы — М.: Вильямс — 2006 г.
Eric W. Weisstein, Eulerian Number at MathWorld
Eric W. Weisstein, Worpitzky’s Identity at MathWorld
Eulerian Numbers at MathPages

Числа Ейлера I роду

Зміст

Приклад

Властивості

Трикутник чисел Ейлера першого роду

Рекурентна формула

Зв'язок з біноміальними коефіцієнтами і степеневими формулами

Явні формули для чисел Ейлера

Сумування чисел Ейлера I роду

Генератриса і тотожність Ворпицького

Програми на PARI/GP для обчислення чисел Ейлера

Література

Навігаційне меню

Числа Ейлера I роду

Приклад

Властивості

Трикутник чисел Ейлера першого роду

Рекурентна формула

Зв'язок з біноміальними коефіцієнтами і степеневими формулами

Явні формули для чисел Ейлера

Сумування чисел Ейлера I роду

Генератриса і тотожність Ворпицького

Програми на PARI/GP для обчислення чисел Ейлера

Література

Навігаційне меню

Пошук