Математика / Дискретная математика

Эйлеровы числа: перестановки с заданным числом спусков

Эйлерово число A(n,k) считает перестановки n различных чисел с ровно k спусками между соседними позициями. Рекурсия строит распределение по k вставкой нового наибольшего элемента.

Опубликовано: Обновлено:

Формула

$$A(n,k)=(k+1)A(n-1,k)+(n-k)A(n-1,k-1)$$
Схема Спуски в перестановках пяти элементов
1k=026k=166k=226k=31k=4

Точное распределение 1,26,66,26,1 симметрично. Сумма 120 равна числу всех перестановок пяти различных элементов.

Обозначения

$n$
число различных элементов перестановки, шт.
$k$
число спусков между соседними элементами, шт.
$A(n,k)$
число перестановок с ровно k спусками, шт.
$A(0,0)$
начальное значение для пустой перестановки: 1, шт.

Условия применения

Переставляются n различных, линейно упорядоченных элементов. Спуском считается индекс i от 1 до n−1, для которого πᵢ>πᵢ₊₁. Начало A(0,0)=1, значения за допустимыми границами полагают нулевыми. Для n≥1 возможны k=0,…,n−1. Для вероятностей все n! перестановок должны быть равновероятны.

Ограничения

При повторяющихся элементах требуется иная версия подсчёта с явным правилом для равенств. Число спусков не равно числу инверсий и не определяет его однозначно. В справочниках встречается индексировка по числу серий или по возрастаниям; перед использованием таблицы нужно проверить определение k.

Подробное объяснение

В перестановке 3,1,4,2 есть два спуска: 3>1 и 4>2. Пара 3>2 тоже является инверсией, но не спуском, потому что элементы не соседние. Эйлеровы числа распределяют перестановки по числу локальных падений. Сумма одной строки по k равна n!, поскольку каждая перестановка имеет ровно одно определённое число спусков.

Чтобы получить перестановку n элементов, вставляют наибольший элемент n в один из n промежутков перестановки длины n−1, включая начало и конец. Если исходно k спусков, вставка в любой из них заменяет один спуск одним, а вставка в конец тоже сохраняет число спусков. Получается k+1 позиций и первое слагаемое рекурсии.

Если исходно k−1 спусков, новые k получаются вставкой в начало или в промежуток с возрастанием. Таких позиций n−k. Обе группы исходных перестановок не пересекаются, а удаление наибольшего элемента однозначно восстанавливает происхождение. Поэтому рекурсия не пропускает и не дублирует вариантов.

Для n=4 строка равна 1,11,11,1. Симметрия A(n,k)=A(n,n−1−k) объясняется заменой каждого значения v на n+1−v: каждый спуск превращается в возрастание и наоборот. Крайние единицы соответствуют строго возрастающему и строго убывающему порядкам. Эти свойства удобно использовать для независимой проверки динамической таблицы.

Как пользоваться формулой

  1. Определите спуск как сравнение соседних различных значений и проверьте, что k обозначает именно число таких падений.
  2. Начните таблицу с A(0,0)=1 и при каждом обращении за границы допустимой строки используйте нулевое значение.
  3. Вычисляйте следующую строку по двум предыдущим коэффициентам, применяя множители k+1 и n−k без сдвига индексов.
  4. Проверьте симметрию, крайние единицы и сумму n!; для вероятности разделите нужный коэффициент на факториал n.

Историческая справка

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

В цифровом справочнике NIST DLMF раздел 26.14 описывает порядковую запись перестановок и соседние спуски, а также соответствующие числа. Современные учебные методы строят таблицу через вставку наибольшего элемента, сохраняя комбинаторный смысл каждого множителя. Такой вывод объясняет и точные значения малых строк, и отличие от чисел Стирлинга, считающих циклы или разбиения. Здесь используется индекс k, равный числу спусков, а не числу возрастающих серий.

Историческая линия формулы

Общепринятое название — эйлеровы числа. Даты первого появления конкретной современной рекурсии здесь не устанавливаются. Запись A(n,k) явно привязана к числу спусков; в других источниках тот же треугольник может быть обозначен скобками или индексирован с другим началом.

Пример

Четыре карточки с числами 1,2,3,4 перемешивают равновероятно. Нужно найти число порядков с ровно одним спуском и вероятность такого результата. Спуски сравнивают только у соседних карточек, а не у всех возможных пар. При n=3 строка A(3,k) равна 1,4,1. Рекурсия даёт A(4,1)=2·A(3,1)+3·A(3,0)=2·4+3·1=11. Полная строка для n=4 равна 1,11,11,1, её сумма 24=4!. Поэтому вероятность одного спуска 11/24≈0,45833. Перестановка (1,3,2,4) подходит, потому что единственное падение 3>2; (3,1,4,2) не подходит — падений два. Проверка симметрией даёт также 11 порядков с двумя спусками.

Частая ошибка

Не нужно сравнивать несоседние элементы при подсчёте спусков: это уже инверсии. В рекурсии множитель второго члена равен n−k, а не n−k−1. Для n=1 существует одна перестановка с нулём спусков; условие k≥1 потеряло бы её. Нельзя использовать таблицу, индексированную по сериям возрастания, без сдвига k.

Практика

Задачи с решением

Пять элементов

Условие. Найдите A(5,1), зная A(4,0)=1 и A(4,1)=11.

Решение. A(5,1)=2·11+4·1=26. Вероятность 26/120=13/60.

Ответ. 26 перестановок; вероятность 13/60.

Центр строки

Условие. Найдите A(5,2) из строки 1,11,11,1 при n=4.

Решение. A(5,2)=3·11+3·11=66. Строка 1,26,66,26,1 в сумме даёт 120.

Ответ. 66 перестановок.

Дополнительные источники

  • https://dlmf.nist.gov/26.14
  • https://math.mit.edu/~fgotti/docs/Courses/C.%20Combinatorial%20Analysis/13.%20Permutatios%20III/Permutations%20III.pdf

Связанные формулы

Математика

Распределение числа совпадений в перестановке

$D_{n,k}=\binom nk !(n-k)$

Число перестановок с ровно k неподвижными точками получается выбором совпавших мест и беспорядком на остальных позициях. Деление на n! даёт вероятность ровно k совпадений в случайной перестановке.

Математика

Ладейный многочлен: назначения с запретами

$N(B)=\sum_{k=0}^{n}(-1)^k r_k(B)(n-k)!,\qquad r_0(B)=1$

Ладейные числа считают совместимые наборы запрещённых назначений. Чередующаяся сумма с факториалами затем даёт число перестановок, которые избегают всех запрещённых клеток таблицы.

Математика

Лемма Бёрнсайда: число объектов с учётом симметрий

$|X/G|=\frac1{|G|}\sum_{g\in G}|\operatorname{Fix}(g)|$

Число классов объектов относительно конечной группы симметрий равно среднему числу объектов, неподвижных при её элементах. Лемма Бёрнсайда учитывает симметричные объекты с меньшими орбитами.

Математика

Число перестановок без повторений

$P_n=n!$

Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.