Математика / Дискретная математика
Эйлеровы числа: перестановки с заданным числом спусков
Эйлерово число A(n,k) считает перестановки n различных чисел с ровно k спусками между соседними позициями. Рекурсия строит распределение по k вставкой нового наибольшего элемента.
Формула
Точное распределение 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: каждый спуск превращается в возрастание и наоборот. Крайние единицы соответствуют строго возрастающему и строго убывающему порядкам. Эти свойства удобно использовать для независимой проверки динамической таблицы.
Как пользоваться формулой
- Определите спуск как сравнение соседних различных значений и проверьте, что k обозначает именно число таких падений.
- Начните таблицу с A(0,0)=1 и при каждом обращении за границы допустимой строки используйте нулевое значение.
- Вычисляйте следующую строку по двум предыдущим коэффициентам, применяя множители k+1 и n−k без сдвига индексов.
- Проверьте симметрию, крайние единицы и сумму 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
Связанные формулы
Математика
Распределение числа совпадений в перестановке
Число перестановок с ровно k неподвижными точками получается выбором совпавших мест и беспорядком на остальных позициях. Деление на n! даёт вероятность ровно k совпадений в случайной перестановке.
Математика
Ладейный многочлен: назначения с запретами
Ладейные числа считают совместимые наборы запрещённых назначений. Чередующаяся сумма с факториалами затем даёт число перестановок, которые избегают всех запрещённых клеток таблицы.
Математика
Лемма Бёрнсайда: число объектов с учётом симметрий
Число классов объектов относительно конечной группы симметрий равно среднему числу объектов, неподвижных при её элементах. Лемма Бёрнсайда учитывает симметричные объекты с меньшими орбитами.
Математика
Число перестановок без повторений
Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.