Числа Лаха, открытые математиком из Словении Иво Лахом в 1955 — это коэффициенты, выражающие возрастающие факториалы через убывающие факториалы.
Беззнаковые числа Лаха имеют интересное значение в комбинаторике — они отражают число способов, каким множество из n элементов может быть разбито на k непустых упорядоченных подмножеств. Числа Лаха связаны с числами Стирлинга.
Беззнаковые числа Лаха ():
Числа Лаха со знаками ():
L(n, 1) всегда равно n!. В вышеупомянутой интерпретации разбиения множества {1, 2, 3} на 1 множество может быть осуществлено 6 способами:
{(1, 2, 3)}, {(1, 3, 2)}, {(2, 1, 3)}, {(2, 3, 1)}, {(3, 1, 2)}, {(3, 2, 1)}
L(3, 2) соответствует 6 разбиениям на два упорядоченных множества:
{(1), (2, 3)}, {(1), (3, 2)}, {(2), (1, 3)}, {(2), (3, 1)}, {(3), (1, 2)} or {(3), (2, 1)}
L(n, n) всегда равно 1, поскольку, например, разбиение множества {1, 2, 3} на 3 непустых подмножества приводит к подмножествам длины 1.
{(1), (2), (3)}
При использовании обозначения Карамата — Кнута для чисел Стирлинга было предложено использовать следующее альтернативное обозначение чисел Лаха:
Возрастающие и убывающие факториалы
Пусть обозначает возрастающий факториал , а — убывающий факториал .
Тогда and
Например,
Сравните с третьей строкой таблицы значений.
Тождества и связи
где — числа Стирлинга первого рода, а — числа Стирлинга второго рода. Если принять, что и при .
Таблица значений Таблица значений чисел Лаха: 1 2 3 4 5 6 7 8 9 10 11 12 1 1 2 2 1 3 6 6 1 4 24 36 12 1 5 120 240 120 20 1 6 720 1800 1200 300 30 1 7 5040 15120 12600 4200 630 42 1 8 40320 141120 141120 58800 11760 1176 56 1 9 362880 1451520 1693440 846720 211680 28224 2016 72 1 1036288001632960021772800127008003810240635040604803240901 1139916800199584000299376000199584000698544001397088016632001188049501101 12479001600263450880043908480003293136000131725440030735936043908480392040021780072601321
Современное практическое применение В последние годы числа Лаха используются в стеганография для сокрытия данных в изображениях. По сравнению с такими альтернативами, как DCT, DFT и DWT, они имеют меньшую сложность——вычисления их целочисленных коэффициентов. Преобразования Лаха и Лагерра естественно возникают при пертурбативном описании хроматической дисперсии.
В оптика Лаха-Лагерра такой подход значительно ускоряет решение задач оптимизации.
См. также Числа Стирлинга Матрица Паскаля
Примечания
Литература
Статья переиздана в 1980, и ещё один раз в 2002 (Dover Publications)
Категория:Факториалы и биномиальные коэффициенты Категория:Целочисленные последовательности Категория:Треугольники чисел