Эйлера числа


Эйлера числа

В комбинаторике числом Эйлера 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, для которых πj < πj + 1.

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

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

Свойства

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

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

Зеркальным отражением перестановки с m подъёмами является перестановка с nm − 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}. Количество подъёмов в ρ равняется количеству подъёмов в ρ, если j = 1 или если πj − 1 < πj; и оно больше количества подъёмов в ρ, если j = n или если ρj − 1 > ρj. Следовательно, π в сумме имеет (k+1)\left\langle{n-1\atop k}\right\rangle способов построения перестановок из ρ, которые имеют k подъёмов, плюс ((n-2)-(k-1)+1)\left\langle{n-1\atop k-1}\right\rangle способов построения перестановок из ρ, которые имеют 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.

Связь с биномиальными коэффициентами и степенными функциями

Применение чисел Эйлера главным образом состоит в предоставлении замечательной связи между обычными степенями и последовательными биномиальными коэффициентами:

x^n = \sum_k \left\langle{n\atop k}\right\rangle {x+k\choose n}

для целых n\geq0. (Это тождество также известно под названием тождества Верпинского). В частности:

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

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

Поскольку рекуррентность для чисел Эйлера достаточно сложная, они удовлетворяют лишь немногим свойствам:

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

Умножая первое тождество на znm и суммируя по m, получаем:

\sum_m \left\{ {n\atop m} \right\} m!z^{n-m} = \sum_{k} \left\langle{n\atop k}\right\rangle (z+1)^k.

Заменяя z на z + 1 и уравнивая коэффициенты при zk, получаем второе тождество. Таким образом, эти два тождества эквивалентны. Первое тождество применяется при малых значениях m:

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

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

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

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

Знакопеременные суммы чисел Эйлера I рода при фиксированном значении n связаны с числами Бернулли Bn + 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.

Также справедливы следующие тождества:

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

Тождество Ворпицкого выражает xn как сумму обобщенных биномиальных коэффициентов:

x^n=\sum_{m=0}^{n-1} \left\langle{n\atop m}\right\rangle {x+m\choose 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) ) }

Литература


Wikimedia Foundation. 2010.

Смотреть что такое "Эйлера числа" в других словарях:

  • Эйлера числа —         в математике, целые числа Еп, являющиеся коэффициентами при tn/n!, в разложении функции 1/cht (см. Гиперболические функции) в степенной ряд:                   Введены Л. Эйлером в 1755. Э. ч. связаны рекуррентным соотношением (Е+1)… …   Большая советская энциклопедия

  • Числа Ферма — числа вида , где n неотрицательное целое число. Последовательность чисел Ферма начинается так: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, … (последовательность A000215 в OEIS) Содержание 1 История 2 …   Википедия

  • Числа Эйлера I рода — В комбинаторике числом Эйлера I рода из n по k, обозначаемым или , называется количество перестановок порядка n с k подъёмами, то есть таких перестановок , что существует ровно k индексов j, для которых . Числа Эйлера I рода обладают также… …   Википедия

  • Эйлера число — e математическая константа, основание натурального логарифма, иррациональное и трансцендентное число. Иногда число e называют числом Эйлера (не путать с т. н. числами Эйлера I рода) или числом Непера. Обозначается строчной латинской буквой «e».… …   Википедия

  • ЭЙЛЕРА МЕТОД — простейший конечно разностный метод численного решения обыкновенных дифференциальных уравнений. Пусть дано дифференциальное уравнение с начальным условием y(x0) = y0. Выбирается достаточно малый шаг hпо оси х, строятся точки x;=x0+ih, i=0, 1, 2 …   Математическая энциклопедия

  • Числа с собственными именами — В этот список включены числа, имеющие собственные названия, не являющиеся стандартными сложносоставными названиями чисел. Именные названия степеней тысячи приводятся, только если у них есть иные названия. Содержание 1 Натуральные числа 1.1… …   Википедия

  • Эйлера функция —         число φ(а) натуральных чисел, меньших, чем а, и взаимно простых с а:                  где p1,..., pk простые делители числа а. Введена Л. Эйлером в 1760 61. Если числа а и b взаимно просты, тоφ(ab) = φ(а) φ(b). При т> 1 и наибольшем общем …   Большая советская энциклопедия

  • Эйлера уравнение —         1) дифференциальное уравнение вида                  где ao,..., an постоянные числа; при х>0 уравнение (*) подстановкой х = et сводится к линейному дифференциальному уравнению (См. Линейные дифференциальные уравнения) с постоянными… …   Большая советская энциклопедия

  • ЭЙЛЕРА - МАКЛОРЕНА ФОРМУЛА — формула суммирования, связывающая частные суммы ряда с интегралом и производными его общего члена: где Бернулли числа, Rn остаточный член. С помощью Бернулли многочленов Bn(t), В n(0)=В п остаточный член записывается в виде: Для n=2sостаточный… …   Математическая энциклопедия

  • Числа в десятичной системе: от 10 до гуголплекса — Именные названия степеней тысячи в порядке возрастания Название Значение Американская система Европейская система тысяча 10³ 10³ миллион 106 106 миллиард 109 109 биллион 109 1012 триллион 1012 …   Википедия

Книги

Другие книги по запросу «Эйлера числа» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.