Меню Главная Случайная статья Настройки Числа Лаха Материал из https://ru.wikipedia.org Числа Лаха, открытые математиком из Словении Иво Лахом в 1955[1] — это коэффициенты, выражающие возрастающие факториалы через убывающие факториалы. Беззнаковые числа Лаха имеют интересное значение в комбинаторике — они отражают число способов, каким множество из n элементов может быть разбито на k непустых упорядоченных подмножеств. Числа Лаха связаны с числами Стирлинга. Беззнаковые числа Лаха (последовательность A105278 в OEIS): ${\displaystyle L(n,k)={n-1 \choose k-1}{\frac {n!}{k!}}.}$ Числа Лаха со знаками (последовательность A008297 в OEIS): ${\displaystyle L'(n,k)=(-1)^{n}{n-1 \choose k-1}{\frac {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)} При использовании обозначения Карамата — Кнута для чисел Стирлинга было предложено использовать следующее альтернативное обозначение чисел Лаха: ${\displaystyle L(n,k)=\left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor .}$ Содержание 1 Возрастающие и убывающие факториалы 2 Тождества и связи 3 Таблица значений 4 Современное практическое применение 5 См. также 6 Примечания 7 Литература Возрастающие и убывающие факториалы Пусть ${\displaystyle x^{(n)}}$ обозначает возрастающий факториал ${\displaystyle x(x+1)(x+2)\cdots (x+n-1)}$, а ${\displaystyle (x)_{n}}$ — убывающий факториал ${\displaystyle x(x-1)(x-2)\cdots (x-n+1)}$. Тогда ${\displaystyle x^{(n)}=\sum _{k=1}^{n}L(n,k)(x)_{k}}$ and ${\displaystyle (x)_{n}=\sum _{k=1}^{n}(-1)^{n-k}L(n,k)x^{(k)}.}$ Например, ${\displaystyle x(x+1)(x+2)={\color {red}6}x+{\color {red}6}x(x-1)+{\color {red}1}x(x-1)(x-2).}$ Сравните с третьей строкой таблицы значений. Тождества и связи ${\displaystyle L(n,k)={n-1 \choose k-1}{\frac {n!}{k!}}={n \choose k}{\frac {(n-1)!}{(k-1)!}}={n \choose k}{n-1 \choose k-1}(n-k)!}$ ${\displaystyle L(n,k)={\frac {n!(n-1)!}{k!(k-1)!}}\cdot {\frac {1}{(n-k)!}}=\left({\frac {n!}{k!}}\right)^{2}{\frac {k}{n(n-k)!}}}$ ${\displaystyle L(n,k+1)={\frac {n-k}{k(k+1)}}L(n,k).}$ ${\displaystyle L(n,k)=\sum _{j}\left[{n \atop j}\right]\left\{{j \atop k}\right\},}$ где ${\displaystyle \left[{n \atop j}\right]}$ — числа Стирлинга первого рода, а ${\displaystyle \left\{{j \atop k}\right\}}$ — числа Стирлинга второго рода. Если принять, что ${\displaystyle L(0,0)=1}$ и ${\displaystyle L(n,k)=0}$ при ${\displaystyle k>n}$. ${\displaystyle L(n,1)=n!}$ ${\displaystyle L(n,2)=(n-1)n!/2}$ ${\displaystyle L(n,3)=(n-2)(n-1)n!/12}$ ${\displaystyle L(n,n-1)=n(n-1)}$ ${\displaystyle L(n,n)=1}$ ${\displaystyle \sum _{n\geq k}L(n,k){\frac {x^{n}}{n!}}={\frac {1}{k!}}\left({\frac {x}{1-x}}\right)^{k}}$ Таблица значений Таблица значений чисел Лаха: ${\displaystyle _{n}\!\!\diagdown \!\!^{k}}$ 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 10 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1 11 39916800 199584000 299376000 199584000 69854400 13970880 1663200 11880 4950 110 1 12 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1 Современное практическое применение В последние годы числа Лаха используются в стеганография для сокрытия данных в изображениях. По сравнению с такими альтернативами, как DCT, DFT и DWT, они имеют меньшую сложность—${\displaystyle O(n\log n)}$—вычисления их целочисленных коэффициентов.[2][3] Преобразования Лаха и Лагерра естественно возникают при пертурбативном описании хроматической дисперсии.[4] [5] В оптика Лаха-Лагерра такой подход значительно ускоряет решение задач оптимизации. См. также Числа Стирлинга Матрица Паскаля Примечания Riordan, 1958. Ghosal, Sudipta Kr; Mukhopadhyay, Souradeep; Hossain, Sabbir; Sarkar, Ram (2020). Application of Lah Transform for Security and Privacy of Data through Information Hiding in Telecommunication. Transactions on Emerging Telecommunications Technologies. 32 (2). doi:10.1002/ett.3984. S2CID 225866797. Image Steganography-using-Lah-Transform  (неопр.). MathWorks. Дата обращения: 4 марта 2023. Архивировано 4 марта 2023 года. Литература