Числа Эйлера

Числа Эйлера первого рода

Возьмём перестановку $\sigma = (\sigma_1, \sigma_2, \dotsc, \sigma_n)$ множества $\{1, 2, \dotsc, n\}$ . Если мы пройдёмся по ней слева направо, то на каждом шаге между двумя соседними позициями увидим либо «взлёт», либо «падение». Точнее, для каждого индекса $j$ от $1$ до $n-1$ мы сравниваем соседей $\sigma_j$ и $\sigma_{j+1}$ . Если $\sigma_j < \sigma_{j+1}$ , то мы говорим, что здесь подъём; а если $\sigma_i > \sigma_{i+1}$ , то мы говорим, что здесь спад. Равенства быть не может — все элементы различны.

Очень часто приходится считать число подъёмов в перестановке $\sigma$ . Например, в перестановке $(3,1,4,2)$ подъёмы находятся между 1 и 4, то есть на позиции 2, так что количество подъемов в перестановке $(3,1,4,2)$ равно $1$ . А в тождественной перестановке $(1, 2, \dotsc, n)$ их $n-1$ — она монотонно возрастает.

Давайте зададимся естественным вопросом: «Сколько перестановок длины $n$ имеют ровно $k$ подъёмов?»

Числа Эйлера первого рода

Числом Эйлера первого рода называется целое число, обозначаемое $\left\langle {n \atop k} \right\rangle$ и равное количеству перестановок множества $\{1,\dotsc,n\}$ с ровно $k$ подъёмами.

По определению, $\left\langle {0 \atop 0} \right\rangle = 1$ , а при $n \ge 1$ значение $k$ может принимать значения от $0$ до $n-1$ включительно.

Например, $\eulerI{4}{2} = 11$ , потому что ровно $11$ перестановок множества $\{ 1, 2, 3, 4 \}$ содержат по $2$ подъема:

\align{ 1324,~ 1423,~ 2314,~ 2413,~ 3412 &\quad\text{--- перестановки с}~ \sigma_1 < \sigma_2 > \sigma_3 < \sigma_4 \\ 1243,~ 1342,~ 2341 &\quad\text{--- перестановки с}~ \sigma_1 < \sigma_2 < \sigma_3 > \sigma_4 \\ 2134,~ 3124,~ 4123 &\quad\text{--- перестановки с}~ \sigma_1 > \sigma_2 < \sigma_3 < \sigma_4 }

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

\begin{array}{c|cccccc} n & \displaystyle \eulerI{n}{0} & \displaystyle \eulerI{n}{1} & \displaystyle \eulerI{n}{2} & \displaystyle \eulerI{n}{3} & \displaystyle \eulerI{n}{4} & \displaystyle \eulerI{n}{5} & \displaystyle \eulerI{n}{6} & \displaystyle \eulerI{n}{7} & \displaystyle \eulerI{n}{8} & \displaystyle \eulerI{n}{9}\\[0.8em]\hline\\[-0.75em] 0 & 1 \\ 1 & 1 \\ 2 & 1 & 1 \\ 3 & 1 & 4 & 1 \\ 4 & 1 & 11 & 11 & 1 \\ 5 & 1 & 26 & 66 & 26 & 1 \\ 6 & 1 & 57 & 302 & 302 & 57 & 1 \\ 7 & 1 & 120 & 1191 & 2416 & 1191 & 120 & 1 \\ 8 & 1 & 247 & 4293 & 15619 & 15619 & 4293 & 247 & 1 \\ 9 & 1 & 502 & 14608 & 88234 & 156190 & 88234 & 14608 & 502 & 1 \\ 10 & 1 & 1013 & 47840 & 455192 & 1310354 & 1310354 & 455192 & 47840 & 1013 & 1 \\ \end{array}

Из этой таблицы можно заметить симметрию и пару приятных свойств.

Симметрия. Для всех целых $n \ge 1$ и $0 \le k \le n-1$ выполняется тождество

\eulerI{n}{k} = \eulerI{n}{n-1-k}

В любой перестановке длины $n$ ровно $n-1$ позиций между соседними элементами. Каждая из них — либо подъём, либо спад. Следовательно, если перестановка имеет $k$ подъёмов, то она имеет $n-1-k$ спадов.

Развернув перестановку, то есть сопоставив перестановке $\sigma = (\sigma_1, \sigma_2, \dotsc, \sigma_n)$ перестановку $\sigma' = (\sigma_n, \dotsc, \sigma_2, \sigma_1)$ , мы переведём все подъемы в спады и все спады в подъемы. Разворот перестановки является биекцией на множестве всех перестановок. Значит, количество перестановок с $k$ подъемами равно количеству перестановок с $n-1-k$ спадами, и числа Эйлера симметричны.

Полная сумма. Сумма чисел Эйлера в одной строке треугольника Эйлера равна $n!$

\sum\limits_{k=0}^{n-1} \eulerI{n}{k} = n!

Каждая перестановка имеет какое-то количество подъемов от $0$ до $n-1$ . Значит, все перестановки $n$ элементов можно явно поделить на классы по числу подъемов. В классе перестановок с $k$ подъемами будет $\eulerI{n}{k}$ перестановок, а сумма мощностей всех классов как раз равна количеству перестановок — $n!$ .

Рекуррентное соотношение.

\eulerI{n}{k} = (k+1) \cdot \eulerI{n-1}{k} + (n - k) \cdot \eulerI{n-1}{k-1} \quad\text{с начальным условием}~ \eulerI{0}{k} = [k=0]

Чтобы получить перестановку длины $n$ с ровно $k$ подъёмами, вставим число $n$ в перестановку длины $n-1$ одним из двух способов.

Во-первых, можно взять перестановку с $k$ подъёмами и вставить $n$ в одну из $k+1$ позиций, где число подъёмов не увеличится: это в конец или сразу после любого из $k$ подъёмов.

Во-вторых, можно взять перестановку с $k-1$ подъёмами и вставить $n$ в одну из $n - k$ позиций, где число подъёмов увеличится на единицу: это в начало или сразу после любого из $n-k-1$ спадов.

Суммируя оба вклада, получаем рекуррентное соотношение.

Зачастую при работе с комбинаторикой задачи не ограничиваются базовыми вычислениями количества возможных размещений или перестановок. В реальной жизни часто приходится рассматривать частные случаи комбинаторных задач, включающие в себя ограничения или условия на размещение элементов.

Глобально все задачи подобного рода можно свести к рассмотрению отношений между парами элементов. Возьмем базовый случай, где нам надо сравнить пару близлежащих элементов на соответствие заданному неравенству.

Подъём

Пусть $\sigma = (\sigma_1, \sigma_2, \dotsc, \sigma_n)$ — перестановка множества $\N = \{1, 2, \dotsc, n\}$ . Восходящей последовательностью (англ. ascent) или подъёмом в перестановке $\sigma$ называется индекс $i \in \{1, 2, \dotsc, n-1\}$ такой, что $\sigma_i < \sigma_{i+1}$

Число восходящих последовательностей в перестановке $\sigma$ обозначим через $\operatorname{asc}(\sigma)$ .

Число Эйлера первого рода

Число Эйлера первого рода — это целое число, обозначаемое как

\eulerI{n}{k}

и равное количеству перестановок множества $\N$ , содержащих ровно $k$ подъёмов. По определению, $\eulerI{0}{0} = 1$ , а при $n > 0$ значения $k$ лежат в диапазоне $0 \le k \le n-1$ .

Посчитаем значения чисел Эйлера первого рода для малых $n$ :

\begin{array}{c|cccccc} n \backslash k & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 1 \\ 1 & 1 \\ 2 & 1 & 1 \\ 3 & 1 & 4 & 1 \\ 4 & 1 & 11 & 11 & 1 \\ 5 & 1 & 26 & 66 & 26 & 1 \end{array}

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

Симметрия чисел Эйлера первого рода

Для любых целых $n \ge 1$ и $0 \le k \le n-1$ выполняется

\left\langle \begin{array}{c} n \\ k \end{array} \right\rangle = \eulerI{n}{n-1-k}

В перестановке длины $n$ имеется ровно $n-1$ позиций между соседними элементами. Каждая такая позиция является либо подъёмом ( $\sigma_i < \sigma_{i+1}$ ), либо спадом ( $\sigma_i > \sigma_{i+1}$ ). Следовательно, если перестановка $\sigma$ содержит $k$ подъёмов, то она содержит ровно $(n-1) - k$ спадов.

Рассмотрим отображение, сопоставляющее перестановке $\sigma$ её обратную перестановку $\sigma^*$ , определяемую формулой

\sigma^*_i = n + 1 - \sigma_{n+1-i}

Это отображение является биекцией на множестве всех перестановок $n$ . Более того, оно переводит каждый подъём в $\sigma$ в спад в $\sigma^*$ , и наоборот — каждый спад в $\sigma$ становится подъёмом в $\sigma^*$ . Получается, если $\sigma_i < \sigma_{i+1}$ , то

\sigma^*_{n-i} = n + 1 - \sigma_{i+1} < n + 1 - \sigma_i = \sigma^*_{n+1-i}

то есть в $\sigma^*$ на позиции $n-i$ является спадом.

Таким образом, число подъёмов в $\sigma^*$ равно числу спадов в $\sigma$ , то есть $(n-1) - \operatorname{asc}(\sigma)$ .

Отсюда следует, что перестановки с $k$ подъёмами взаимно однозначно соответствуют перестановкам с $n-1-k$ подъёмами. Следовательно, их количества совпадают:

\eulerI{n}{k} = \eulerI{n}{n-1-k}

Когда мы находим такое полезное число, возникает закономерный вопрос — а как его вычислять? Перебирать при больших $n$ все возможные перестановки явно недопустимо долго, поэтому воспользуемся рекурентным свойством чисел Эйлера.

Рекуррентное соотношение

Для всех $n \ge 1$ и $0 \le k \le n$ справедливо

\eulerI{n}{k} = (k+1)\, \left\langle \begin{array}{c} n-1 \\ k \end{array} \right\rangle + (n-k-1)\, \left\langle \begin{array}{c} n-1 \\ k- 1 \end{array} \right\rangle

где считается, что $\eulerI{n}{k} = 0$ при $k < 0$ или $k \ge n$ .

Рассмотрим, как получить все перестановки длины $n$ из перестановок длины $n-1$ , вставляя число $n$ в одну из $n$ возможных позиций.

Рассмотрим перестановку $\tau$ длины $n-1$ с $k$ подъёмами. При вставке максимального элемента $n$ в одну из $n$ возможных позиций возможны два случая:

Если вставить $n$ в конец или сразу после одного из $k$ подъёмов, то общий подъём между соседними элементами заменяется на подъём–спад с участием $n$ . В результате число подъёмов не изменяется. Таких позиций $k+1$ .
Если вставить $n$ в любую другую позицию (то есть в начало или сразу после одного из $n-1-k$ спадов), то появляется новый подъём слева от $n$ , а справа появляется спад. Старого подъёма в этом месте не было, поэтому общее число подъёмов увеличивается на $1$ . Таких позиций — $n - (k + 1) = n - k - 1$ .

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

Зафиксируем $n \ge 0$ и рассмотрим обычную производящую функцию по параметру $k$ :

A_n(x) = \sum\limits_{k=0}^{n-1} \eulerI{n}{k} x^k

Эта функция — многочлен степени $n-1$ , который называется Эйлеровым многочленом. А из найденной ранее симметрии чисел Эйлера следует

A_n(x) = x^{n-1} A_n\left(\frac{1}{x}\right)

Формула для Эйлерова многочлена

Для любого целого $n \ge 0$ выполняется

A_n(x) = \sum\limits_{j=0}^{n} (-1)^j \binom{n+1}{j} (x - j)^n

Рассмотрим функцию

f(t) = \frac{1 - t}{1 - t e^{(1 - t) z}}

и разложим её в ряд по

z

. С одной стороны, коэффициент при

z^n / n!

в этом разложении равен

A_n(t)

, что можно проверить прямым вычислением первых членов.

С другой стороны, используя геометрический ряд и биномиальную теорему, получаем:

\frac{1 - t}{1 - t e^{(1 - t) z}} = (1 - t) \sum\limits_{m=0}^{\infty} t^m e^{m(1 - t) z} = \sum\limits_{m=0}^{\infty} (t^m - t^{m+1}) \sum\limits_{n=0}^{\infty} \frac{(m(1 - t))^n}{n!} z^n

Приравнивая коэффициенты при $z^n$ и упрощая сумму по $m$ , приходим к формуле, эквивалентной утверждению теоремы.

Производящие функции чисел Эйлера связаны с суммами степеней, например, рассмотрим сумму $\sum\limits_{m=0}^{N-1} m^n$ . Известно, что она выражается через числа Бернулли, но эквивалентно её можно записать с помощью Эйлеровых многочленов:

\sum\limits_{m=0}^{N-1} m^n = \frac{1}{n+1} \sum\limits_{k=0}^{n} \left\langle \begin{array}{c} n+1 \\ k \end{array} \right\rangle \binom{N + k}{n+1}

Разложение степени через числа Эйлера

Одним из самых частых применений чисел Эйлера первого рода в математике является разложение степени переменной $x^n$ в линейную комбинацию биномиальных коэффициентов.

Формула Эйлера для степеней

Для любого целого $n \ge 0$ и любого комплексного $x$ выполняется тождество

x^n = \sum\limits_{k=0}^{n-1} \eulerI{n}{k} \binom{x + k}{n}

Рассмотрим правую часть как функцию от $x$ . Поскольку $\binom{x + k}{n}$ — полином степени $n$ их линейная комбинация также является полиномом степени не выше $n$ . Достаточно проверить равенство на $n+1$ различных значениях $x$ .

Возьмём $x = m \in \NN$ . Тогда левая часть — это просто $m^n$ . Правая часть интерпретируется как число функций из множества из $n$ элементов в множество из $m$ элементов.

Используем комбинаторную интерпретацию биномиального коэффициента: $\binom{m + k}{n}$ равно числу способов выбрать неубывающую последовательность длины $n$ из чисел $0, 1, \dotsc, m + k - 1$ . Но каждая такая последовательность однозначно соответствует перестановке с $k$ подъёмами, в которой элементы распределены по $m$ уровням.

Альтернативно, можно вывести формулу из производящей функции. Умножим обе части на $t^n / n!$ и просуммируем по $n \ge 0$ :

\sum\limits_{n=0}^{\infty} x^n \frac{t^n}{n!} = e^{xt} = \sum\limits_{n=0}^{\infty} \left( \sum\limits_{k=0}^{n-1} \eulerI{n}{k} \binom{x + k}{n} \right) \frac{t^n}{n!}

С другой стороны, мы уже знаем, что

\sum\limits_{n=0}^{\infty} A_n(x) \frac{t^n}{n!} = \frac{1 - x}{1 - x e^{t(1 - x)}}

Подстановка $x \mapsto 1/(1 - u)$ приводит к разложению, эквивалентному утверждению теоремы. Однако наиболее прямой путь — это использовать тождество

\sum\limits_{j=0}^{n} (-1)^j \binom{n+1}{j} (x - j)^n = \sum\limits_{k=0}^{n-1} \left\langle \begin{array}{c} n \\ k \end{array} \right\rangle x^k

а затем заметить, что биномиальные коэффициенты образуют базис пространства полиномов степени $\le n$ , и коэффициенты разложения в этом базисе именно и есть числа Эйлера.

Я привел несколько различных способов доказательства этой формулы, для того, чтобы вы прочувствовали, что числа Эйлера можно рассматривать как с точки зрения комбинаторики, так и с точки зрения математического анализа.

В частности, из этой формулы следует, что числа Эйлера могут быть использованы для вычисления сумм вида $\sum\limits_{m=0}^{N-1} m^n$ :

\sum\limits_{m=0}^{N-1} m^n = \sum\limits_{k=0}^{n-1} \left\langle \begin{array}{c} n \\ k \end{array} \right\rangle \sum\limits_{m=0}^{N-1} \binom{m + k}{n} = \sum\limits_{k=0}^{n-1} \eulerI{n}{k} \binom{N + k}{n + 1}

где мы использовали классическое тождество

\sum\limits_{m=0}^{N-1} \binom{m + k}{n} = \binom{N + k}{n + 1}

Я хочу обратить ваше внимание на то, как удобно числа Эйлера связывают работу со степенями и вычисление биномиальных коэффициентов.

Геометрическая интерпретация

Рассмотрим единичный гиперкуб $I^n = [0,1]^n \subset \mathbb{R}^n$ и для целого $k \in \{0, 1, \dotsc, n-1\}$ определим множество

\Xi_n^k = \left\{ x \in I^n \colon k \le \sum\limits_{i=1}^n x_i \;\! \le \;\! k+1 \right\}

Это слой куба между двумя параллельными гиперплоскостями $\sum\limits x_i = k$ и $\sum\limits x_i = k+1$ .

Объём слоя и числа Эйлера

Для любого $n \ge 1$ и $0 \le k \le n-1$ выполняется

\operatorname{Vol}_n\left( \Xi_n^k \right) = \frac{1}{n!} \eulerI{n}{k}

(

\operatorname{Vol}

— объём, от англ. Volume)

Применим общую формулу для объёма среза гиперкуба:

\operatorname{Vol}_n\bigl(G^n_{\mathbf{1},\, z} \cap I^n\bigr) = \frac{1}{n!} \sum\limits_{j=0}^{n} (-1)^j \binom{n}{j} (z - j)^n_+

где $\mathbf{1} = (1, \dotsc, 1)$ — вектор всех единиц, а $(t)_+ = \max\limits(t, 0)$ . Тогда объём слоя равен разности объёмов двух срезов:

\operatorname{Vol}_n(\Xi_n^k) = \operatorname{Vol}_n(G^n_{\mathbf{1},\ , k+1} \cap I^n) - \operatorname{Vol}_n(G^n_{\mathbf{1},\, k} \cap I^n)

Подставляя формулу, получаем:

\operatorname{Vol}_n(\Xi_n^k) = \frac{1}{n!} \left( \sum\limits_{j=0}^{k+1} (-1)^j \binom{n}{j} (k+1 - j)^n - \sum\limits_{j=0}^{k} (-1)^j \binom{n}{j} (k - j)^n \right)

После перегруппировки слагаемых:

\eulerI{n}{k} = \sum\limits_{j=0}^{k+1} (-1)^j \binom{n+1}{j} (k+1 - j)^n

получаем требуемое равенство.

Эта интерпретация показывает, что числа Эйлера еще и измеряют геометрическую сложность сечений гиперкуба. Например, для $n = 3$ объёмы слоёв $\Xi_3^0, \Xi_3^1, \Xi_3^2$ равны $1/6, 4/6, 1/6$ , что соответствует числам Эйлера $\langle 3 \atop 0 \rangle = 1$ $\langle 3 \atop 1 \rangle = 4$ $\langle 3 \atop 2 \rangle = 1$

Геометрический взгляд также объясняет симметрию чисел Эйлера: отображение $x \mapsto 1 - x$ переводит слой $\Xi_n^k$ в слой $\Xi_n^{n-1-k}$ , сохраняя объём, и тем самым устанавливает биекцию между соответствующими перестановками.

Разложение через $\sec$ и $\tan$

Еще одни Числа Эйлера — целочисленная последовательность $E_n$ , определяемая разложением суммы секанса и тангенса в степенной ряд:

\sec x + \tan x = \sum\limits_{n=0}^{\infty} E_n \frac{x^n}{n!}

Эквивалентно, чётные и нечётные члены разделяются:

\sec x = \sum\limits_{n=0}^{\infty} \frac{E_{2n}}{(2n)!} x^{2n}, \quad \tan x = \sum\limits_{n=1}^{\infty} \frac{E_{2n-1}}{(2n-1)!} x^{2n-1}

Функция $\sec x$ чётна, поэтому все нечётные коэффициенты равны нулю; $\tan x$ нечётна, поэтому все чётные коэффициенты равны нулю. Первые значения:

E_0 = 1,\ E_1 = 1,\ E_2 = 1,\ E_3 = 2,\ E_4 = 5,\ E_5 = 16,\ E_6 = 61,\ \dotsc

Связь с числами Эйлера первого рода

Для всех $n \ge 0$ выполняются равенства:

E_{2n} = \left\langle \begin{array}{c} 2n \\ n-1 \end{array} \right\rangle

E_{2n-1} = \frac{1}{2} \sum\limits_{k=0}^{2n-1} \left\langle \begin{array}{c} 2n-1 \\ k \end{array} \right\rangle

Рассмотрим экспоненциальную производящую функцию Эйлеровых многочленов:

\sum\limits_{n=0}^{\infty} A_n(x) \frac{z^n}{n!} = \frac{1 - x}{1 - x e^{z(1 - x)}}

Подставим $x = -1$ , тогда:

\sum\limits_{n=0}^{\infty} A_n(-1) \frac{z^n}{n!} = \frac{2}{1 + e^{2z}} = \frac{1}{\cosh z} = \sec(i z)

С другой стороны, из разложения $\sec z = \sum\limits E_{2n} z^{2n}/(2n)!$ следует:

\frac{1}{\cosh z} = \sum\limits_{n=0}^{\infty} (-1)^n \frac{E_{2n}}{(2n)!} z^{2n}

Приравнивая коэффициенты и используя симметрию $A_n(-1) = (-1)^{n-1} E_{n-1}$ (при $n \ge 1$ ), получаем требуемую связь для чётных индексов.

Аналогично, подстановка $x = 1$ приводит к расходимости, но предельный переход даёт:

\lim\limits_{x \to 1} \frac{1 - x}{1 - x e^{z(1 - x)}} = \frac{1}{1 - z} = \sum\limits_{n=0}^{\infty} z^n

что соответствует сумме всех коэффициентов $A_n(1) = n!$

По сути геометрическая интерпретация и тригонометрические разложения вытекают из одного и того же явления: объёмы сечений куба связаны с интегралами от $\sec$ и $\tan$ , а эти интегралы выражаются через те же самые числа $\left\langle \begin{array}{c} n \\ k \end{array} \right\rangle$ .

Числа Эйлера 2-го рода

Пусть $n \ge 1$ — целое число. Рассмотрим мультимножество $M_n = \{1, 1, 2, 2, \dotsc, n, n\}$ . Перестановка $\sigma$ длины $2n$ элементов из $M_n$ называется перестановкой с повторениями. Аналогично числам Эйлера первого рода, восходящей последовательностью в $\sigma$ называется индекс $i \in \{1, \dotsc, 2n-1\}$ такой, что

\sigma_i < \sigma_{i+1}.

Обращу внимание: если $\sigma_i = \sigma_{i+1}$ , это не считается подъёмом.

Число Эйлера 2-го рода

Число Эйлера 2-го рода — это целое число, обозначаемое как

\left\langle\!\eulerI{n}{k}\!\right\rangle

и равное количеству перестановок мультимножества $M_n$ , содержащих ровно $k$ восходящих последовательностей. По определению, $\left\langle\!\left\langle \begin{array}{c} 0 \\ 0 \end{array} \right\rangle\!\right\rangle = 1$ .

Альтернативная, но эквивалентная интерпретация происходит через понятие упорядоченного разбиения.

Пусть $n = \{1, \dotsc, n\}$ .

Упорядоченное разбиение $n$ на $k+1$ непустых блоков — это последовательность непересекающихся подмножеств $B_1, B_2, \dotsc, B_{k+1}$ , таких что

\bigcup_{i=1}^{k+1} B_i = n

Тогда

\left\langle\!\eulerI{n}{k}\!\right \rangle

равно числу таких упорядоченных разбиений, в которых каждый блок

B_i

упорядочен по возрастанию, и при этом выполняется условие:

\max\limits(B_i) < \min\limits(B_{i+1})

для всех

i = 1, \dotsc, k

Эта интерпретация нужна, чтобы показать, что числа 2-го рода измеряют структуру разбиений, в отличие от чисел первого рода, которые измеряют линейный порядок в перестановках.

Посчитаем значения чисел Эйлера 2-го рода для малых $n$ :

\begin{array}{c|cccc} n \backslash k & 0 & 1 & 2 & 3 \\ \hline 0 & 1 \\ 1 & 1 \\ 2 & 1 & 2 \\ 3 & 1 & 8 & 6 \\ 4 & 1 & 22 & 58 & 24 \end{array}

В отличие от чисел первого рода, из треугольника видно, что для чисел 2-го рода симметрия отсутствует.

Рекуррентное соотношение

Числа Эйлера 2-го рода, подобно числам первого рода, удовлетворяют рекуррентному соотношению, которое позволяет вычислять их без перебора всех перестановок мультимножества.

Рекуррентное соотношение

Для всех целых $n \ge 1$ и $0 \le k \le n-1$ справедливо

\left\langle\!\left\langle \begin{array}{c} n \\ k \end{array} \right\rangle\!\right\rangle = (2k + 1) \left\langle\!\left\langle \begin{array}{c} n - 1 \\ k \end{array} \right\rangle\!\right\rangle + (2n - 2k) \left\langle\!\eulerI{n - 1}{k - 1}\!\right\rangle

где считается, что $\left\langle\!\left\langle \begin{array}{c} n \\ k \end{array} \right\rangle\!\right\rangle = 0$ при $k < 0$ или $k \ge n$ .

Рассмотрим, как получить все перестановки мультимножества $M_n = \{1,1,\dotsc,n,n\}$ из перестановок $M_{n-1}$ , добавляя две копии числа $n$ . Пусть $\tau$ — перестановка длины $2n-2$ с $k$ подъёмами.

Всего существует $2n-1$ позиций для вставки первого элемента $n$ , и после этого — $2n$ позиций для второго. Однако, чтобы избежать двойного подсчёта, будем рассматривать вставку пары $(n,n)$ .

Ключевое наблюдение: при вставке двух копий числа $n$ в перестановку $\tau$ , число подъёмов может увеличиться на $0$ , $1$ или $2$ , в зависимости от того, куда они помещаются.

Точнее:

Если обе копии $n$ вставляются в одну и ту же позицию, или одна сразу после другой, то они образуют подстроку $\{\dotsc n,n \dotsc\}$ , которая не создаёт подъём. Количество способов сделать это так, чтобы не увеличить число подъёмов, пропорционально $2k+1$ .
Если копии вставляются в разные позиции, и хотя бы одна из них размещается после подъёма или в начало, то может появиться один или два новых подъёма. Подсчёт показывает, что число способов увеличить число подъёмов с $k-1$ до $k$ равно $2n - 2k$ .

Сумма этих двух случаев даёт рекуррентную формулу.

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

Зафиксируем $n \ge 0$ и определим Эйлеров многочлен 2-го рода как

B_n(x) = \sum\limits_{k=0}^{n-1} \left\langle\!\left\langle \begin{array}{c} n \\k \end{array} \right\rangle\!\right\rangle x^k

В отличие от Эйлеровых многочленов первого рода, эти многочлены не обладают свойством симметрии, что отражает отсутствие симметрии в самих числах.

Более информативной оказывается двухпараметрическая экспоненциальная производящая функция.

Экспоненциальная производящая функция

Для всех $|x| < 1$ и $|t|$ достаточно малых справедливо тождество:

\sum\limits_{n=0}^{\infty} B_n(x) \frac{t^n}{n!} = \frac{1}{1 - x(e^t - 1)}

Рассмотрим правую часть как геометрический ряд:

\frac{1}{1 - x(e^t - 1)} = \sum\limits_{m=0}^{\infty} x^m (e^t - 1)^m

Разложим $(e^t - 1)^m$ с помощью формулы включения-исключения:

(e^t - 1)^m = \sum\limits_{n=m}^{\infty} m! \, S(n, m) \frac{t^n}{n!}

где $S(n, m)$ — числа Стирлинга второго рода. Подставляя это в ряд, получаем:

\sum\limits_{m=0}^{\infty} x^m \sum\limits_{n=m}^{\infty} m! \, S(n, m) \frac{t^n}{n!} = \sum\limits_{n=0}^{\infty} \left( \sum\limits_{m=0}^{n} m! \, S(n, m) x^m \right) \frac{t^n}{n!}

Сравнивая коэффициенты при $t^n / n!$ с левой частью, замечаем, что

B_n(x) = \sum\limits_{m=0}^{n} m! \, S(n, m) x^m

Но из комбинаторной интерпретации чисел 2-го рода известно, что коэффициент при $x^k$ в этом многочлене в точности равен $\left\langle\!\eulerI{n}{k}\!\right\rangle$ . Действительно, каждое упорядоченное разбиение на $k+1$ блоков можно построить, сначала выбрав разбиение на $k+1$ непустых подмножеств ( $S(n, k+1)$ способов), а затем упорядочив блоки ( $(k+1)!$ способов). Отсюда

\left\langle\!\left\langle\begin{array}{c} n \\ k \end{array} \right\rangle\!\right\rangle = (k+1)! \, S(n, k+1)

Связь с числами Стирлинга и разложениями степеней

Как мы могли заметить выше, производящая функция чисел Эйлера 2-го рода напрямую связана с числами Стирлинга второго рода. Эта связь позволяет выразить сами числа 2-го рода через $S(n,k)$ — количество способов разбить $n$ элементов на $k$ непустых подмножеств.

Связь с числами Стирлинга

Для всех целых $n \ge 1$ и $0 \le k \le n-1$ выполняется

\left\langle\!\left\langle \begin{array}{c} n \\ k \end{array} \right\rangle\!\right\rangle = (k+1)! \, S(n, k+1)

Рассмотрим комбинаторную интерпретацию чисел 2-го рода как упорядоченные разбиения множества $n$ на $k+1$ блоков, где блоки упорядочены по возрастанию их минимальных элементов. Чтобы построить такое разбиение, можно сначала разбить $n$ на $k+1$ непустых подмножеств — это можно сделать $S(n, k+1)$ способами, а затем упорядочить эти подмножества, что можно сделать $(k+1)!$ способами, так как порядок блоков в упорядоченном разбиении фиксирован только их относительным расположением, а не внутренней структурой. Следовательно, общее число таких объектов равно $(k+1)! \, S(n, k+1)$ , что и требовалось доказать.

Эта формула даёт альтернативный способ вычисления чисел 2-го рода и ещё раз объясняет отсутствие симметрии: числа Стирлинга $S(n,k)$ не симметричны по $k$ , и факториальный множитель только усиливает эту асимметрию.

Более глубокую связь устанавливает разложение степенной функции через числа 2-го рода. В отличие от чисел первого рода, которые разлагают $x^n$ в базис биномиальных коэффициентов $\binom{x + k}{n}$ , числа 2-го рода естественно возникают в более сложных конструкциях, например в разложении в базис падающих факториалов.

Разложение степени

Для любого целого $n \ge 0$ и любого комплексного $x$ справедливо тождество

x^n = \sum\limits_{k=0}^{n-1} \left\langle\!\left\langle \begin{array}{c} n \\ k \end{array} \right\rangle\!\right\rangle \binom{x}{k+1}

Известно, что степенную функцию можно разложить по базису биномиальных коэффициентов:

x^n = \sum\limits_{m=0}^{n} c_{n,m} \binom{x}{m}

где коэффициенты $c_{n,m}$ выражаются через числа Стирлинга второго рода: $c_{n,m} = m! \, S(n, m)$ . Действительно, это стандартное разложение в конечных разностях. Теперь заменим индекс суммирования: возьмем $m = k+1$ . Тогда

x^n = \sum\limits_{k=0}^{n-1} (k+1)! \, S(n, k+1) \binom{x}{k+1}

По предыдущей теореме $(k+1)! \, S(n, k+1) = \left\langle\!\left\langle \begin{array}{c} n \\ k \end{array} \right\rangle\!\right\rangle$ , откуда и следует утверждение.

Геометрическая и аналитическая интерпретация

В отличие от чисел первого рода, числа 2-го рода не связаны с свойствами гиперплоскостей, но они появляются в других геометрических и аналитических контекстах. В частности, они возникают при интегрировании полиномов по симплексам, а также как коэффициенты в разложениях функций, связанных с распределениями сумм независимых случайных величин.

Рассмотрим независимые случайные величины $X_1, \dotsc, X_n$ , где каждая $X_i$ равномерно распределена на отрезке $[0,1]$ . Пусть $Y = X_1 + \dotsb + X_n$ . Известно, что плотность распределения $Y$ является кусочно-полиномиальной функцией, и на интервале $[k, k+1]$ (для целого $0 \le k \le n-1$ ) она выражается через числа первого рода:

f_Y(t) = \frac{1}{(n-1)!} \sum\limits_{j=0}^{k} (-1)^j \binom{n}{j} (t - j)^{n-1}

Эта формула напрямую связана с объёмом сечения куба и числами $\eulerI{n}{k}$ .

В случае, когда переменные имеют неодинаковые распределения или интерпретируются как индикаторы принадлежности блокам разбиения, естественным образом возникают числа $\left\langle\!\left\langle \begin{array}{c} n \\ k \end{array} \right\rangle\!\right\rangle$ . Например, если $Z_i$ — индикатор того, что элемент $i$ попал в один из первых $k+1$ блоков случайного упорядоченного разбиения, то совместное распределение $(Z_1, \dotsc, Z_n)$ поддерживается на симплексе $\{ x \in [0,1]^n \colon x_1 \le \dotsb \le x_n \}$ , и объём его подмножеств выражается через числа Стирлинга и, следовательно, через числа 2-го рода. Вот такая вот хитрая цепочка взаимосвязей.

Аналитически, числа Эйлера 2-го рода появляются в разложениях рациональных функций вида

\frac{1}{(1 - e^{-t})^m} = \sum\limits_{n=0}^{\infty} \left( \sum\limits_{k=0}^{n} \left\langle\!\eulerI{n}{k}\!\right\rangle \binom{m-1}{k} \right) \frac{t^n}{n!}

что связано с полиномами Бернулли и теорией конечных разностей.

Числа Эйлера

Числа Эйлера первого рода

Числа Эйлера первого рода

Подъём

Число Эйлера первого рода

Симметрия чисел Эйлера первого рода

Рекуррентное соотношение

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

Формула для Эйлерова многочлена

Разложение степени через числа Эйлера

Формула Эйлера для степеней

Геометрическая интерпретация

Объём слоя и числа Эйлера

Разложение через sec⁡\secsec и tan⁡\tantan

Связь с числами Эйлера первого рода

Числа Эйлера 2-го рода

Число Эйлера 2-го рода

Рекуррентное соотношение

Рекуррентное соотношение

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

Экспоненциальная производящая функция

Связь с числами Стирлинга и разложениями степеней

Связь с числами Стирлинга

Разложение степени

Геометрическая и аналитическая интерпретация

Разложение через $\sec$ и $\tan$