Editing Lah number

{{Short description|Mathematical sequence}}
{{Use American English|date = March 2019}}
[[File:Lah numbers.svg|thumb|upright=1.35|Illustration of the unsigned Lah numbers for ''n'' and ''k'' between 1 and 4]]
In [[mathematics]], the '''(signed and unsigned) Lah numbers''' are [[coefficient]]s expressing [[rising factorial]]s in terms of [[falling factorial]]s and vice versa.  They were discovered by [[Ivo Lah]] in 1954.<ref>{{cite journal | first=Ivo | last=Lah | title=A new kind of numbers and its application in the actuarial mathematics | journal=Boletim do Instituto dos Actuários Portugueses | volume=9 | year=1954 | pages=7–15}}</ref><ref>[https://books.google.com/books?id=zWgIPlds29UC John Riordan, ''Introduction to Combinatorial Analysis''], Princeton University Press (1958, reissue 1980) {{isbn|978-0-691-02365-6}} (reprinted again in 2002 by Dover Publications).</ref>  Explicitly, the unsigned Lah numbers <math>L(n, k)</math> are given by the formula involving the [[binomial coefficient]] 

<math display="block"> L(n,k) = {n-1 \choose k-1} \frac{n!}{k!}</math>

for <math>n \geq k \geq 1</math>.

Unsigned Lah numbers have an interesting meaning in [[combinatorics]]: they count the number of ways a [[Set (mathematics)|set]] of ''<math display="inline">n</math>'' elements can be [[Partition of a set|partition]]ed into ''<math display="inline">k</math>'' nonempty linearly ordered [[subset]]s.<ref>{{cite journal | title=Combinatorial Interpretation of Unsigned Stirling and Lah Numbers | first1=Marko | last1=Petkovsek | first2=Tomaz | last2=Pisanski | journal=Pi Mu Epsilon Journal | volume=12 | number=7 | date = Fall 2007 | pages=417–424 | jstor=24340704}}</ref> Lah numbers are related to [[Stirling number]]s.<ref>{{cite book | first=Louis | last=Comtet | title=Advanced Combinatorics | publisher=Reidel | location=Dordrecht, Holland | year=1974 | url=https://archive.org/details/Comtet_Louis_-_Advanced_Coatorics | page=[https://archive.org/details/Comtet_Louis_-_Advanced_Coatorics/page/n83 156]| isbn=9789027703804 }}</ref>

For <math display="inline">n \geq 1</math>, the Lah number <math display="inline">L(n, 1)</math> is equal to the [[factorial]] <math display="inline">n!</math> in the interpretation above, the only partition of <math display="inline">\{1, 2, 3 \}</math> into 1 set can have its set ordered in 6 ways:<math display="block">\{(1, 2, 3)\}, \{(1, 3, 2)\}, \{(2, 1, 3)\}, \{(2, 3, 1)\}, \{(3, 1, 2)\}, \{(3, 2, 1)\}</math><math display="inline">L(3, 2)</math> is equal to 6, because there are six partitions of <math display="inline">\{1, 2, 3 \}</math> into two ordered parts:<math display="block">\{1, (2, 3) \}, \{1, (3, 2) \}, \{2, (1, 3) \}, \{2, (3, 1) \}, \{3, (1, 2) \}, \{3, (2, 1) \}</math><math display="inline">L(n, n)</math> is always 1 because the only way to partition <math display="inline">\{1, 2, \ldots, n\}</math> into <math>n</math> non-empty subsets results in subsets of size 1, that can only be permuted in one way.
In the more recent literature,<ref>{{cite arXiv |eprint=1412.8721 |first=Mark |last=Shattuck |title=Generalized r-Lah numbers |date=2014|class=math.CO }}</ref><ref>{{Cite journal |last1=Nyul |first1=Gábor |last2=Rácz |first2=Gabriella |date=2015-10-06 |title=The r-Lah numbers |url=https://www.sciencedirect.com/science/article/pii/S0012365X14001241 |journal=Discrete Mathematics |series=Seventh Czech-Slovak International Symposium on Graph Theory, Combinatorics, Algorithms and Applications, Košice 2013 |language=en |volume=338 |issue=10 |pages=1660–1666 |doi=10.1016/j.disc.2014.03.029 |issn=0012-365X|hdl=2437/213886 |hdl-access=free }}</ref> [[Jovan Karamata|Karamata]]–[[Donald Knuth|Knuth]] style notation has taken over. Lah numbers are now often written as<math display="block">L(n,k) = \left\lfloor {n \atop k} \right\rfloor</math>

==Table of values==
Below is a table of values for the Lah numbers:
{| class="wikitable" style="text-align:right;" 
|-
! {{diagonal split header|{{mvar|n}}&nbsp;|&nbsp;{{mvar|k}}}} 
!0!! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10
|-
!0
|1
|-
! 1
|0
| 1
|-
! 2
|0
| 2
| 1
|-
! 3
|0
| 6
| 6
| 1
|-
! 4
|0
| 24
| 36
| 12
| 1
|-
! 5
|0
| 120
| 240
| 120
| 20
| 1
|-
! 6
|0
| 720
| 1800
| 1200
| 300
| 30
| 1
|-
! 7
|0
| 5040
| 15120
| 12600
| 4200
| 630
| 42
| 1
|-
! 8
|0
| 40320
| 141120
| 141120
| 58800
| 11760
| 1176
| 56
| 1
|-
! 9
|0
| 362880
| 1451520
| 1693440
| 846720
| 211680
| 28224
| 2016
| 72
| 1
|-
! 10
|0
|3628800
|16329600
|21772800
|12700800
|3810240
|635040
|60480
|3240
|90
|1
|}

The row sums are <math display="inline">1, 1, 3, 13, 73, 501, 4051, 37633, \dots</math> {{OEIS|A000262}}.

==Rising and falling factorials==


Let <math display="inline">x^{(n)}</math> represent the [[rising factorial]] <math display="inline">x(x+1)(x+2) \cdots (x+n-1)</math> and let <math display="inline">(x)_n</math> represent the [[falling factorial]] <math display="inline">x(x-1)(x-2) \cdots (x-n+1)</math>.  The Lah numbers are the coefficients that express each of these families of polynomials in terms of the other.  Explicitly,<math display="block">x^{(n)} = \sum_{k=0}^n L(n,k) (x)_k</math>and<math display="block">(x)_n = \sum_{k=0}^n (-1)^{n-k} L(n,k)x^{(k)}.</math>For example,<math display="block">x(x+1)(x+2) = {\color{red}6}x + {\color{red}6}x(x-1) + {\color{red}1}x(x-1)(x-2)</math>and<math display="block">x(x-1)(x-2) = {\color{red}6}x - {\color{red}6}x(x+1) + {\color{red}1}x(x+1)(x+2),</math>

where the coefficients 6, 6, and 1 are exactly the Lah numbers <math>L(3, 1)</math>, <math>L(3, 2)</math>, and <math>L(3, 3)</math>.

==Identities and relations==
The Lah numbers satisfy a variety of identities and relations.

In [[Jovan Karamata|Karamata]]–[[Donald Knuth|Knuth]] notation for [[Stirling numbers]]<math display="block"> L(n,k) = \sum_{j=k}^n \left[{n\atop j}\right] \left\{{j\atop k}\right\}</math>where <math display="inline">\left[{n\atop j}\right]</math> are the [[Stirling numbers of the first kind|unsigned Stirling numbers of the first kind]] and <math display="inline">\left\{{j\atop k}\right\}</math> are the [[Stirling numbers of the second kind]].
:<math> 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)!</math>

:<math> 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)!}</math>

:<math> k(k+1) L(n,k+1) = (n-k) L(n,k)</math>, for <math>k>0</math>.
=== Recurrence relations ===
The Lah numbers satisfy the recurrence relations<math display="block">
\begin{align} L(n+1,k) &= (n+k) L(n,k) + L(n,k-1) \\
&= k(k+1) L(n, k+1) + 2k L(n, k) + L(n, k-1)
\end{align}
</math>where <math>L(n,0)=\delta_n</math>, the [[Kronecker delta]], and <math>L(n,k)=0</math> for all <math>k > n</math>.

=== Exponential generating function ===

:<math>\sum_{n\geq k} L(n,k)\frac{x^n}{n!} = \frac{1}{k!}\left( \frac{x}{1-x} \right)^k</math>

=== Derivative of exp(1/''x'') ===

The ''n''-th [[derivative]] of the function <math>e^\frac1{x}</math> can be expressed with the Lah numbers, as follows<ref>{{cite journal |last1=Daboul |first1=Siad |last2=Mangaldan |first2=Jan |last3=Spivey |first3=Michael Z. |last4=Taylor |first4=Peter J. |year=2013 |title=The Lah Numbers and the nth Derivative of <math>e^{1\over x}</math> |journal=Mathematics Magazine |volume=86 |pages=39–47 |doi=10.4169/math.mag.86.1.039 |jstor=10.4169/math.mag.86.1.039 |s2cid=123113404 |number=1}}</ref><math display="block"> \frac{\textrm d^n}{\textrm dx^n} e^\frac1x = (-1)^n \sum_{k=1}^n \frac{L(n,k)}{x^{n+k}} \cdot e^\frac1x.</math>For example,

<math> \frac{\textrm d}{\textrm dx} e^\frac1x = - \frac{1}{x^2} \cdot e^{\frac1x}</math>

<math> \frac{\textrm d^2}{\textrm dx^2}e^\frac1{x} = \frac{\textrm d}{\textrm dx} \left(-\frac1{x^2} e^{\frac1x} \right)= -\frac{-2}{x^3} \cdot e^{\frac1x} - \frac1{x^2} \cdot \frac{-1}{x^2} \cdot e^{\frac1x}= \left(\frac2{x^3} + \frac1{x^4}\right) \cdot e^{\frac1x}</math>

<math> \frac{\textrm d^3}{\textrm dx^3}  e^\frac1{x} = \frac{\textrm d}{\textrm dx} \left( \left(\frac2{x^3} + \frac1{x^4}\right) \cdot e^{\frac1x} \right) = \left(\frac{-6}{x^4} + \frac{-4}{x^5}\right) \cdot e^{\frac1x} + \left(\frac2{x^3} + \frac1{x^4}\right) \cdot \frac{-1}{x^2} \cdot e^{\frac1x} =-\left(\frac6{x^4} + \frac6{x^5} + \frac1{x^6}\right) \cdot e^{\frac{1}{x}}</math>

== Link to Laguerre polynomials ==
Generalized [[Laguerre polynomials]] <math>L^{(\alpha)}_n(x)</math> are linked to Lah numbers upon setting <math>\alpha = -1</math><math display="block"> n! L_n^{(-1)}(x) =\sum_{k=0}^n L(n,k) (-x)^k</math>This formula is the default [[Laguerre polynomials|Laguerre polynomial]] in [[Umbral calculus]] convention.<ref>{{Cite journal |last1=Rota |first1=Gian-Carlo |last2=Kahaner |first2=D |last3=Odlyzko |first3=A |date=1973-06-01 |title=On the foundations of combinatorial theory. VIII. Finite operator calculus |journal=Journal of Mathematical Analysis and Applications |language=en |volume=42 |issue=3 |pages=684–760 |doi=10.1016/0022-247X(73)90172-8 |issn=0022-247X|doi-access=free }}</ref>

== Practical application ==
In recent years, Lah numbers have been used in [[steganography]] for hiding data in images. Compared to alternatives such as [[Discrete cosine transform|DCT]], [[Discrete Fourier transform|DFT]] and [[Discrete wavelet transform|DWT]], it has lower complexity of calculation&mdash;<math>O(n \log n)</math>&mdash;of their integer coefficients.<ref>{{Cite journal |last1=Ghosal |first1=Sudipta Kr |last2=Mukhopadhyay |first2=Souradeep |last3=Hossain |first3=Sabbir |last4=Sarkar |first4=Ram |year=2020 |title=Application of Lah Transform for Security and Privacy of Data through Information Hiding in Telecommunication |journal=Transactions on Emerging Telecommunications Technologies |volume=32 |issue=2 |doi=10.1002/ett.3984|s2cid=225866797 }}</ref><ref>{{Cite web |title=Image Steganography-using-Lah-Transform |url=https://in.mathworks.com/matlabcentral/fileexchange/78751-image-steganography-using-lah-transform |website=MathWorks|date=5 June 2020 }}</ref>
The Lah and Laguerre transforms naturally arise in the perturbative description of the [[chromatic dispersion]].<ref>{{Cite journal|last1=Popmintchev|first1=Dimitar|last2=Wang|first2=Siyang|last3=Xiaoshi |first3=Zhang |last4=Stoev|first4=Ventzislav|last5=Popmintchev|first5=Tenio|date=2022-10-24 |title=Analytical Lah-Laguerre optical formalism for perturbative chromatic dispersion|journal=[[Optics Express]]|volume=30|issue=22|pages=40779–40808|doi=10.1364/OE.457139|doi-access=free|pmid=36299007 |bibcode=2022OExpr..3040779P}}</ref><ref>{{cite arXiv|last1=Popmintchev|first1=Dimitar|last2=Wang|first2=Siyang|last3=Xiaoshi|first3=Zhang |last4=Stoev|first4=Ventzislav|last5=Popmintchev|first5=Tenio|date=2020-08-30|title= Theory of the Chromatic Dispersion, Revisited |class=physics.optics |eprint=2011.00066}}</ref>
In [[Lah-Laguerre optics]], such an approach tremendously speeds up optimization problems.

== See also ==
* [[Stirling number]]s
* [[Pascal matrix]]

== References ==
<references />

== External links ==
* The signed and unsigned Lah numbers are respectively {{OEIS|A008297}} and {{OEIS|A105278}} 

{{Classes of natural numbers}}

{{DEFAULTSORT:Lah Number}}
[[Category:Factorial and binomial topics]]
[[Category:Integer sequences]]
[[Category:Triangles of numbers]]