В комбинаторике числом Эйлера I рода из n по k, обозначаемым
или
, называется количество перестановок порядка n с k подъёмами, то есть таких перестановок
, что существует ровно k индексов j, для которых
.
Числа Эйлера I рода обладают также геометрической и вероятностной интерпретацией — число
выражает:
- объём части n-мерного гиперкуба, ограниченного гиперплоскостями
и
; - вероятность того, что сумма n независимых равномерно распределённых в отрезке
переменных лежит между k-1 и k.
Пример
Перестановки
четвертого порядка, имеющие ровно два подъёма, должны удовлетворять одному из трёх неравенств:
,
или
. Таких перестановок ровно 11:
- 1324, 1423, 2314, 2413, 3412, 1243, 1342, 2341, 2134, 3124, 4123.
Поэтому
.
Свойства
Для заданного натурального числа
существует единственная перестановка без подъёмов, то есть
. Также существует единственная перестановка, которая имеет n-1 подъёмов, то есть
. Таким образом,
для всех натуральных
.
Зеркальным отражением перестановки с m подъёмами является перестановка с n-m-1 подъёмами. Таким образом,
![{\displaystyle \left\langle {n \atop m}\right\rangle =\left\langle {n \atop n-m-1}\right\rangle .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71ee48386e5fce5580284c2bf1c7ea8d7ebf3c8a)
Треугольник чисел Эйлера первого рода
Значение чисел Эйлера
для малых значений 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 |
Легко понять, что значения на главной диагонали матрицы задаются формулой:
Треугольник Эйлера, как и треугольник Паскаля, симметричен слева и справа. Но в этом случае закон симметрии несколько отличен:
при n > 0.
То есть перестановка имеет n-1-k подъёмов тогда и только тогда, когда её «отражение» имеет k подъёмов.
Рекуррентная формула
Каждая перестановка
из набора
приводит к
перестановкам из
, если мы вставляем новый элемент n всеми возможными способами. Вставляя
в
-ю позицию, получаем перестановку
. Количество подъёмов в
равняется количеству подъёмов в
, если
или если
; и оно больше количества подъёмов в
, если
или если
. Следовательно,
в сумме имеет
способов построения перестановок из
, которые имеют
подъёмов, плюс
способов построения перестановок из
, которые имеют
подъёмов. Тогда искомая рекуррентная формула для целых
имеет вид:
![{\displaystyle \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 .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e1f5c1d42b8babececb225bafa94ef06737e489)
Положим также, что
(для целых
),
и при
:
![{\displaystyle \left\langle {n \atop k}\right\rangle =0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef80b197336da54f5de2b7bf7939a6059d4b7635)
Явные формулы
Явная формула для чисел Эйлера I рода:
![{\displaystyle \left\langle {n \atop m}\right\rangle =\sum _{k=0}^{m}{n+1 \choose k}(m+1-k)^{n}(-1)^{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/098a0c8b6068c9a3587c9fda651938ac2a14e184)
позволяет получить относительно простые выражения при малых значениях m:
![{\displaystyle \left\langle {n \atop 0}\right\rangle =1;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa02654b9d2e2769ba1fa4602d5168f3c024698c)
![{\displaystyle \left\langle {n \atop 1}\right\rangle =2^{n}-n-1;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f22f8096e9b2c697c06d7d9d24b4a9366ded0aa1)
![{\displaystyle \left\langle {n \atop 2}\right\rangle =3^{n}-(n+1)2^{n}+{n+1 \choose 2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b3140c2d910bbec46ddbc567599b21133c14e0a)
Формулы суммирования
Из комбинаторного определения очевидно, что сумма чисел Эйлера I рода, расположенных в n-й строке, равна
, так как она равна количеству всех перестановок порядка
:
![{\displaystyle \sum _{m=0}^{n}\left\langle {n \atop m}\right\rangle =n!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/297cc884e7e1f0b6ee2085030e65317299431833)
Знакопеременные суммы чисел Эйлера I рода при фиксированном значении n связаны с числами Бернулли
:
![{\displaystyle \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}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc86a40ccae8d070a4227c352c0825353dfdb1d0)
![{\displaystyle \sum _{m=0}^{n}(-1)^{m}\left\langle {n \atop m}\right\rangle {n \choose m}^{-1}=(n+1)B_{n},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/78738ff9c1fcebeebd48625e842c34f447c2194a)
![{\displaystyle \sum _{m=0}^{n}(-1)^{m}\left\langle {n \atop m}\right\rangle {n-1 \choose m}^{-1}=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f90faf0441b008faa1966ba299e7058b7ee3b9e5)
Также справедливы следующие тождества, связывающие числа Эйлера I рода с числами Стирлинга II рода:
![{\displaystyle \sum _{k=n-m}^{n}\left\langle {n \atop k}\right\rangle {k \choose n-m}=m!\left\{{n \atop m}\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4ce3b79d0821cde70514a776824dc4cce6d6efc)
![{\displaystyle \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\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5af6ed1ceb380a86ac429f8cc969edd21a670dec)
![{\displaystyle \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}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e67e1b2dcf30ec15e76f0aeef8f63b6114c59c08)
Производящая функция
Производящая функция чисел Эйлера I рода имеет вид:
![{\displaystyle {\frac {1-w}{e^{(w-1)z}-w}}=\sum _{m,n\geq 0}\left\langle {n \atop m}\right\rangle w^{m}{\frac {z^{n}}{n!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9653650347ef3a3589c9117583faf3833429ad6e)
Числа Эйлера I рода связаны также с производящей функцией последовательности
-х степеней (полилогарифм целого отрицательного порядка):
![{\displaystyle \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}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c566f44b1017f479216f50d92b6b07aa1f710f4a)
Кроме того, Z-преобразование из
![{\displaystyle \left\{n^{k}\right\}_{k=1}^{N}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cfbcdd1732b027a4cdce14f968913002ff960247)
является генератором первых N строк треугольник чисел Эйлера, когда знаменатель
-й элемента преобразования сокращается умножением на
:
![{\displaystyle 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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f518370f0d85e8e87cc190394bc7dc211a0b2bc1)
Тождество Ворпицкого
Тождество Ворпицкого выражает степенную функцию в виде суммы произведений чисел Эйлера I рода и обобщённых биномиальных коэффициентов:
![{\displaystyle x^{n}=\sum _{m=0}^{n-1}\left\langle {n \atop m}\right\rangle {x+m \choose n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00ee20c083d5f78e6cb9358b40537123666b5431)
В частности:
![{\displaystyle x^{2}={x \choose 2}+{x+1 \choose 2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd9d4ceaa78a78253ea68d348071d2a60f824c2f)
![{\displaystyle x^{3}={x \choose 3}+4{x+1 \choose 3}+{x+2 \choose 3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e58aa391996152342ae201e56cf3f285bef5e80)
![{\displaystyle x^{4}={x \choose 4}+11{x+1 \choose 4}+11{x+2 \choose 4}+{x+3 \choose 4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6040432b4ce5d198cc7ac8bab8cda326db964e79)
и т. д. Эти тождества легко доказываются по индукции.
Тождество Ворпицкого даёт ещё один способ вычисления суммы первых
квадратов:
![{\displaystyle \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}=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9dd44cfd9ea70b6946c326d7847f8fc721d5ba5)
![{\displaystyle =\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)=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7208d1ea428b0c9a1f7808270065d7d093d1b6d1)
![{\displaystyle ={n+1 \choose 3}+{n+2 \choose 3}={\frac {n(n+1)(2n+1)}{6}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/38fef06ade1acead6a35df9f52f24f98b03a3d9c)
Литература
| Имеется викиучебник по теме «Программное вычисление чисел Эйлера первого рода» |