Число Лах

Математическая последовательность

Иллюстрация беззнаковых чисел Лаха для n и k от 1 до 4

В математике (знаковые и беззнаковые) числа Лаха являются коэффициентами , выражающими растущие факториалы через падающие факториалы и наоборот. Они были открыты Иво Лахом в 1954 году. ^{[1] [2]} Явно, беззнаковые числа Лаха задаются формулой, включающей биномиальный коэффициент ${\displaystyle L(n,k)}$

$${\displaystyle L(n,k)={n-1 \choose k-1}{\frac {n!}{k!}}}$$

для . ${\displaystyle n\geq k\geq 1}$

Беззнаковые числа Лаха имеют интересное значение в комбинаторике : они подсчитывают количество способов, которыми набор элементов может быть разделен на непустые линейно упорядоченные подмножества . ^[3] Числа Лаха связаны с числами Стирлинга . ^[4] ${\textstyle n}$ ${\textstyle k}$

Для , число Lah равно факториалу в интерпретации выше, единственное разбиение на 1 множество может иметь свой набор, упорядоченный 6 способами: равно 6, потому что существует шесть разбиений на две упорядоченные части: всегда равно 1, потому что единственный способ разбиения на непустые подмножества приводит к подмножествам размера 1, которые могут быть переставлены только одним способом. В более поздней литературе ^{[5] [6]} взяла верх нотация в стиле Карамата – Кнута . Числа Lah теперь часто записываются как ${\textstyle n\geq 1}$ ${\textstyle L(n,1)}$ ${\textstyle n!}$ ${\textstyle \{1,2,3\}}$ $${\displaystyle \{(1,2,3)\},\{(1,3,2)\},\{(2,1,3)\},\{(2,3,1)\},\{(3,1,2)\},\{(3,2,1)\}}$$ ${\textstyle L(3,2)}$ ${\textstyle \{1,2,3\}}$ $${\displaystyle \{1,(2,3)\},\{1,(3,2)\},\{2,(1,3)\},\{2,(3,1)\},\{3,(1,2)\},\{3,(2,1)\}}$$ ${\textstyle L(n,n)}$ ${\textstyle \{1,2,\ldots ,n\}}$ ${\displaystyle n}$ $${\displaystyle L(n,k)=\left\lfloor {n \atop k}\right\rfloor }$$

Таблица значений

Ниже приведена таблица значений чисел Лаха:

Суммы строк (последовательность A000262 в OEIS ). ${\textstyle 1,1,3,13,73,501,4051,37633,\dots }$

Растущие и падающие факториалы

Пусть представляет собой растущий факториал , а пусть представляет собой падающий факториал . Числа Лаха являются коэффициентами, которые выражают каждое из этих семейств полиномов через другое. Явно, и Например, и ${\textstyle x^{(n)}}$ ${\textstyle x(x+1)(x+2)\cdots (x+n-1)}$ ${\textstyle (x)_{n}}$ ${\textstyle x(x-1)(x-2)\cdots (x-n+1)}$ $${\displaystyle x^{(n)}=\sum _{k=0}^{n}L(n,k)(x)_{k}}$$ $${\displaystyle (x)_{n}=\sum _{k=0}^{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 x(x-1)(x-2)={\color {red}6}x-{\color {red}6}x(x+1)+{\color {red}1}x(x+1)(x+2),}$$

где коэффициенты 6, 6 и 1 — это в точности числа Лаха , и . ${\displaystyle L(3,1)}$ ${\displaystyle L(3,2)}$ ${\displaystyle L(3,3)}$

Идентичности и отношения

Числа Лаха удовлетворяют множеству тождеств и отношений.

В нотации Караматы – Кнута для чисел Стирлинга , где – беззнаковые числа Стирлинга первого рода , а – числа Стирлинга второго рода . $${\displaystyle L(n,k)=\sum _{j=k}^{n}\left[{n \atop j}\right]\left\{{j \atop k}\right\}}$$ ${\textstyle \left[{n \atop j}\right]}$ ${\textstyle \left\{{j \atop k}\right\}}$

${\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 k(k+1)L(n,k+1)=(n-k)L(n,k)}$, для . ${\displaystyle k>0}$

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

Числа Лаха удовлетворяют рекуррентным соотношениям, где , символ Кронекера , и для всех . $${\displaystyle {\begin{aligned}L(n+1,k)&=(n+k)L(n,k)+L(n,k-1)\\&=k(k+1)L(n,k+1)+2kL(n,k)+L(n,k-1)\end{aligned}}}$$ ${\displaystyle L(n,0)=\delta _{n}}$ ${\displaystyle L(n,k)=0}$ ${\displaystyle k>n}$

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

${\displaystyle \sum _{n\geq k}L(n,k){\frac {x^{n}}{n!}}={\frac {1}{k!}}\left({\frac {x}{1-x}}\right)^{k}}$

Производная exp(1/х)

Производную n -го порядка функции можно выразить с помощью чисел Лаха следующим образом ^[7] Например, ${\displaystyle e^{\frac {1}{x}}}$ $${\displaystyle {\frac {{\textrm {d}}^{n}}{{\textrm {d}}x^{n}}}e^{\frac {1}{x}}=(-1)^{n}\sum _{k=1}^{n}{\frac {L(n,k)}{x^{n+k}}}\cdot e^{\frac {1}{x}}.}$$

${\displaystyle {\frac {\textrm {d}}{{\textrm {d}}x}}e^{\frac {1}{x}}=-{\frac {1}{x^{2}}}\cdot e^{\frac {1}{x}}}$

${\displaystyle {\frac {{\textrm {d}}^{2}}{{\textrm {d}}x^{2}}}e^{\frac {1}{x}}={\frac {\textrm {d}}{{\textrm {d}}x}}\left(-{\frac {1}{x^{2}}}e^{\frac {1}{x}}\right)=-{\frac {-2}{x^{3}}}\cdot e^{\frac {1}{x}}-{\frac {1}{x^{2}}}\cdot {\frac {-1}{x^{2}}}\cdot e^{\frac {1}{x}}=\left({\frac {2}{x^{3}}}+{\frac {1}{x^{4}}}\right)\cdot e^{\frac {1}{x}}}$

${\displaystyle {\frac {{\textrm {d}}^{3}}{{\textrm {d}}x^{3}}}e^{\frac {1}{x}}={\frac {\textrm {d}}{{\textrm {d}}x}}\left(\left({\frac {2}{x^{3}}}+{\frac {1}{x^{4}}}\right)\cdot e^{\frac {1}{x}}\right)=\left({\frac {-6}{x^{4}}}+{\frac {-4}{x^{5}}}\right)\cdot e^{\frac {1}{x}}+\left({\frac {2}{x^{3}}}+{\frac {1}{x^{4}}}\right)\cdot {\frac {-1}{x^{2}}}\cdot e^{\frac {1}{x}}=-\left({\frac {6}{x^{4}}}+{\frac {6}{x^{5}}}+{\frac {1}{x^{6}}}\right)\cdot e^{\frac {1}{x}}}$

Ссылка на полиномы Лагерра

Обобщенные полиномы Лагерра связаны с числами Лаха при установке Эта формула является полиномом Лагерра по умолчанию в соглашении об исчислении Умбрального . ^[8] ${\displaystyle L_{n}^{(\alpha )}(x)}$ ${\displaystyle \alpha =-1}$ $${\displaystyle n!L_{n}^{(-1)}(x)=\sum _{k=0}^{n}L(n,k)(-x)^{k}}$$

Практическое применение

В последние годы числа Лаха использовались в стеганографии для сокрытия данных в изображениях. По сравнению с альтернативами, такими как DCT , DFT и DWT , они имеют меньшую сложность вычисления — —их целочисленных коэффициентов. ^{[9] [10]} Преобразования Лаха и Лагерра естественным образом возникают в пертурбативном описании хроматической дисперсии . ^{[11] [12]} В оптике Лаха-Лагерра такой подход значительно ускоряет задачи оптимизации. ${\displaystyle O(n\log n)}$

Смотрите также

• числа Стерлинга
• Матрица Паскаля

Ссылки

1. Ла, Иво (1954). «Новый вид чисел и его применение в актуарной математике». Boletim do Instituto dos Actuários Portugals . 9 :7–15.
2. Джон Риордан, Введение в комбинаторный анализ, Princeton University Press (1958, переиздание 1980) ISBN 978-0-691-02365-6 (повторное переиздание в 2002 году издательством Dover Publications). 
3. Петковсек, Марко; Писански, Томаз (осень 2007 г.). «Комбинаторная интерпретация беззнаковых чисел Стирлинга и Лаха». Журнал Pi Mu Epsilon . 12 (7): 417–424. JSTOR  24340704.
4. Конте, Луи (1974). Продвинутая комбинаторика. Дордрехт, Голландия: Reidel. стр. 156. ISBN 9789027703804.
5. Шаттак, Марк (2014). «Обобщенные числа r-Lah». arXiv : 1412.8721 [math.CO].
6. Nyul, Gábor; Rácz, Gabriella (2015-10-06). "Числа r-Lah". Дискретная математика . Седьмой чешско-словацкий международный симпозиум по теории графов, комбинаторике, алгоритмам и приложениям, Кошице, 2013. 338 (10): 1660–1666. doi :10.1016/j.disc.2014.03.029. hdl : 2437/213886 . ISSN  0012-365X.
7. Дабул, Сиад; Мангалдан, Ян; Спайви, Майкл З.; Тейлор, Питер Дж. (2013). «Числа Лаха и n-я производная ». Mathematics Magazine . 86 (1): 39–47. doi :10.4169/math.mag.86.1.039. JSTOR  10.4169/math.mag.86.1.039. S2CID  123113404. ${\displaystyle e^{1 \over x}}$
8. Рота, Джан-Карло; Каханер, Д; Одлыжко, А (1 июня 1973 г.). «Об основах комбинаторной теории. VIII. Конечно-операторное исчисление». Журнал математического анализа и приложений . 42 (3): 684–760. doi : 10.1016/0022-247X(73)90172-8 . ISSN  0022-247X.
9. Ghosal, Sudipta Kr; Mukhopadhyay, Souradeep; Hossain, Sabbir; Sarkar, Ram (2020). «Применение преобразования Lah для обеспечения безопасности и конфиденциальности данных посредством сокрытия информации в телекоммуникациях». Transactions on Emerging Telecommunications Technologies . 32 (2). doi :10.1002/ett.3984. S2CID  225866797.
10. "Image Steganography-using-Lah-Transform". MathWorks . 5 июня 2020 г.
11. Попминчев, Димитар; Ван, Сыян; Сяоши, Чжан; Стоев, Венцислав; Попминчев, Тенио (2022-10-24). «Аналитический оптический формализм Ла-Лагерра для пертурбативной хроматической дисперсии». Optics Express . 30 (22): 40779–40808. Bibcode : 2022OExpr..3040779P. doi : 10.1364/OE.457139 . PMID  36299007.
12. Попминчев, Димитар; Ван, Сиянг; Сяоши, Чжан; Стоев, Венцислав; Попминчев, Тенио (30 августа 2020 г.). «Возвращение к теории хроматической дисперсии». arXiv : 2011.00066 [физика.оптика].

Внешние ссылки

• Знаковые и беззнаковые числа Lah равны соответственно (последовательность A008297 в OEIS ) и (последовательность A105278 в OEIS )