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

Шаблон:Не путать В комбинаторике числом Эйлера 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-мерного гиперкуба, ограниченного гиперплоскостями $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}$ или $π_{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, n)$ . Таким образом,

⟨ \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$ :

⟨ \binom{n}{k} ⟩ = 0 .

Явные формулы

Явная формула для чисел Эйлера I рода:

⟨ \binom{n}{m} ⟩ = \sum_{k = 0}^{m} (\binom{n + 1}{k}) (m + 1 - k)^{n} (- 1)^{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 рода, расположенных в 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 .

Также справедливы следующие тождества, связывающие числа Эйлера I рода с числами Стирлинга II рода:

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

\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}}}]

Тождество Ворпицкого

Тождество Ворпицкого выражает степенную функцию в виде суммы произведений чисел Эйлера I рода и обобщённых биномиальных коэффициентов:

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

В частности:

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} .

Литература

Шаблон:Викиучебник

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

Содержание

Пример

Свойства

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

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

Явные формулы

Формулы суммирования

Производящая функция

Тождество Ворпицкого

Литература

Навигация

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

Пример

Свойства

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

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

Явные формулы

Формулы суммирования

Производящая функция

Тождество Ворпицкого

Литература

Навигация

Поиск