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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В комбинаторике числом Эйлера I рода из n по k, обозначаемым \left\langle{n\atop k}\right\rangle или E(n,k), называется количество перестановок порядка n с k подъёмами, то есть таких перестановок \pi = (\pi_1, \pi_2, \dots, \pi_n), что существует ровно k индексов j, для которых \pi_j<\pi_{j+1}.

Числа Эйлера I рода обладают также геометрической и вероятностной интерпретацией — число \frac{1}{n!}\left\langle{n\atop k}\right\rangle выражает:

Пример[править | править вики-текст]

Перестановки \pi четвертого порядка, имеющие ровно два подъёма, должны удовлетворять одному из трёх неравенств: \pi_1<\pi_2>\pi_3<\pi_4, \pi_1<\pi_2<\pi_3>\pi_4 или \pi_1>\pi_2<\pi_3<\pi_4. Таких перестановок ровно 11 штук:

1324, 1423, 2314, 2413, 3412, 1243, 1342, 2341, 2134, 3124, 4123.

Поэтому \left\langle{4\atop 2}\right\rangle=11.

Свойства[править | править вики-текст]

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

\left\langle{n\atop 0}\right\rangle = \left\langle{n\atop n-1}\right\rangle = 1 для всех натуральных n.

Зеркальным отражением перестановки с m подъёмами является перестановка с n-m-1 подъёмами. Таким образом,

\left\langle{n\atop m}\right\rangle = \left\langle{n\atop n-m-1}\right\rangle.

Треугольник чисел Эйлера первого рода[править | править вики-текст]

Значение чисел Эйлера \left\langle{n\atop k}\right\rangle для малых значений n и k приведены в следующей таблице (последовательность A008292 в 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

Легко понять, что значения на главной диагонали матрицы задаются формулой: \left\langle{n\atop n}\right\rangle=[n=0].

Треугольник Эйлера, как и треугольник Паскаля, симметричен слева и справа. Но в этом случае закон симметрии несколько отличен:

\left\langle{n\atop k}\right\rangle = \left\langle{n\atop n-1-k}\right\rangle при n > 0.

То есть, перестановка имеет n-1-k подъёмов тогда и только тогда, когда её «отражение» имеет k подъёмов.

Рекуррентная формула[править | править вики-текст]

Каждая перестановка \rho=\rho_1\dots\rho_{n-1} из набора \{1,2,3,n-1\} приводит к n перестановкам из \{1,2,3,n\}, если мы вставляем новый элемент n всеми возможными способами. Вставляя n в j-ю позицию, получаем перестановку \pi=\rho_1\dots\rho_{j-1}n\rho_j\dots\rho_{n-1}. Количество подъёмов в \rho равняется количеству подъёмов в \rho, если j=1 или если \pi_{j-1}<\pi_j; и оно больше количества подъёмов в \rho, если j=n или если \rho_{j-1}>\rho_j. Следовательно, \pi в сумме имеет (k+1)\left\langle{n-1\atop k}\right\rangle способов построения перестановок из \rho, которые имеют k подъёмов, плюс ((n-2)-(k-1)+1)\left\langle{n-1\atop k-1}\right\rangle способов построения перестановок из \rho, которые имеют k-1 подъёмов. Тогда искомая рекуррентная формула для целых n>0 имеет вид:

\left\langle{n\atop k}\right\rangle = (k+1)\left\langle{n-1\atop k}\right\rangle + (n-k) \left\langle{n-1\atop k-1}\right\rangle.

Положим также, что

\left\langle{0\atop k}\right\rangle = [k=0] (для целых k),

и при k<0:

\left\langle{n\atop k}\right\rangle = 0.

Явные формулы[править | править вики-текст]

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

\left\langle{n\atop m}\right\rangle = \sum_{k=0}^{m} {n+1\choose k} (m+1-k)^n(-1)^k

позволяет получить относительно простые выражения при малых значениях m:

\left\langle {n\atop 0} \right\rangle = 1;
\left\langle {n\atop 1} \right\rangle = 2^n-n-1;
\left\langle {n\atop 2} \right\rangle = 3^n-(n+1)2^n + {n+1\choose 2}.

Формулы суммирования[править | править вики-текст]

Из комбинаторного определения очевидно, что сумма чисел Эйлера I рода, расположенных в n-й строке равна n!, так как она равна количеству всех перестановок порядка n:

\sum_{m=0}^n \left\langle{n\atop m}\right\rangle = n!

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

\sum_{m=0}^n (-1)^m \left\langle{n\atop m}\right\rangle = \frac{2^{n+1}(2^{n+1}-1)B_{n+1}}{n+1},
\sum_{m=0}^n (-1)^m \left\langle{n\atop m}\right\rangle {n\choose m}^{-1} = (n+1)B_n,
\sum_{m=0}^n (-1)^m \left\langle{n\atop m}\right\rangle {n-1\choose m}^{-1} = 0.

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

\sum_{k=n-m}^n \left\langle{n\atop k}\right\rangle {k\choose n-m} = m!\left\{ {n\atop m} \right\}
\sum_{k=0}^n 2^k \left\langle{n\atop k}\right\rangle = \sum_{k=1}^{\infty} \frac{k^n}{2^k} = \sum_{k=1}^{n} k! \left\{ {n\atop k}\right\}
\sum_{k=0}^n 3^k \left\langle{n\atop k}\right\rangle = 2^{n+1} \sum_{k=1}^{\infty} \frac{k^n}{3^k}

Производящая функция[править | править вики-текст]

Производящая функция чисел Эйлера I рода имеет вид:

\frac{1-w}{e^{(w-1)z}-w} = \sum_{m,n\geq0} \left\langle{n\atop m}\right\rangle w^m \frac{z^n}{n!}

Числа Эйлера I рода связаны также с производящей функцией последовательности n-х степеней:

\sum_{k=1}^{\infty} k^n x^k = \frac{\sum_{m=0}^{n-1} \left\langle{n\atop m}\right\rangle x^{m+1}}{(1-x)^{n+1}}.

Кроме того, Z-преобразование из

\left\{ n^k \right\}_{k=1}^N

является генератором первых N строк треугольник чисел Эйлера, когда знаменатель n-й элемента преобразования сокращается умножением на (z-1)^{j+1}:

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

Тождество Ворпицкого[править | править вики-текст]

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

x^n=\sum_{m=0}^{n-1} \left\langle{n\atop m}\right\rangle {x+m\choose n}.

В частности:

x^2 = {x\choose 2} + {x+1\choose 2}
x^3 = {x\choose 3} + 4{x+1\choose 3} + {x+2\choose 3}
x^4 = {x\choose 4} + 11{x+1\choose 4} + 11{x+2\choose 4} + {x+3\choose 4}

и т. д. Эти тождества легко доказываются по индукции.

Тождество Ворпицкого даёт ещё один способ вычисления суммы первых n квадратов:

\sum_{k=1}^n k^2 = \sum_{k=1}^n \left\langle{2\atop 0}\right\rangle {k\choose 2} + \left\langle{2\atop 1}\right\rangle {k+1\choose 2} = \sum_{k=1}^n  {k\choose 2} + {k+1\choose 2} =
= \left( {1\choose 2} + {2\choose 2} + \dots + {n\choose 2}\right) + \left( {2\choose 2} + {3\choose 2} + \dots + {n+1\choose 2}\right) =
= {n+1\choose 3} + {n+2\choose 3} = \frac{n(n+1)(2n+1)}{6}.

Литература[править | править вики-текст]