Lah number

In mathematics, the Lah numbers, discovered by Ivo Lah in 1954,^[1][2] are coefficients expressing rising factorials in terms of falling factorials. They are also the coefficients of the ${\displaystyle n}$th derivatives of ${\displaystyle e^{1/x}}$.^[3]

Illustration of the unsigned Lah numbers for n and k between 1 and 4

Unsigned Lah numbers have an interesting meaning in combinatorics: they count the number of ways a set of n elements can be partitioned into k nonempty linearly ordered subsets.^[4] Lah numbers are related to Stirling numbers.^[5]

Unsigned Lah numbers (sequence A105278 in the OEIS):

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

Signed Lah numbers (sequence A008297 in the OEIS):

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

L(n, 1) is always n!; in the interpretation above, the only partition of {1, 2, 3} into 1 set can have its set ordered in 6 ways:

{(1, 2, 3)}, {(1, 3, 2)}, {(2, 1, 3)}, {(2, 3, 1)}, {(3, 1, 2)} or {(3, 2, 1)}

L(3, 2) corresponds to the 6 partitions with two ordered parts:

{(1), (2, 3)}, {(1), (3, 2)}, {(2), (1, 3)}, {(2), (3, 1)}, {(3), (1, 2)} or {(3), (2, 1)}

L(n, n) is always 1 since, e.g., partitioning {1, 2, 3} into 3 non-empty subsets results in subsets of length 1.

{(1), (2), (3)}

Adapting the Karamata–Knuth notation for Stirling numbers, it has been proposed to use the following alternative notation for Lah numbers:

$${\displaystyle L(n,k)=\sum _{j=0}^{n}\left[{\begin{matrix}n\\j\end{matrix}}\right]\left\{{\begin{matrix}j\\k\end{matrix}}\right\}}$$

Table of values

Below is a table of values for the Lah numbers:

k n	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

The row sums are ${\displaystyle 1,1,3,13,73,501,4051,37633,\dots }$  (sequence A000262 in the OEIS).

Rising and falling factorials

Main article: Falling and rising factorials

Let ${\displaystyle x^{(n)}}$  represent the rising factorial ${\displaystyle x(x+1)(x+2)\cdots (x+n-1)}$  and let ${\displaystyle (x)_{n}}$  represent the falling factorial ${\displaystyle x(x-1)(x-2)\cdots (x-n+1)}$ .

Then ${\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)}.}$ 

For example,

$${\displaystyle x(x+1)(x+2)={\color {red}6}x+{\color {red}6}x(x-1)+{\color {red}1}x(x-1)(x-2)}$$

 

and

$${\displaystyle x(x-1)(x-2)={\color {red}6}x-{\color {red}6}x(x+1)+{\color {red}1}x(x+1)(x+2).}$$

 

Compare the third row of the table of values.

Identities and relations

${\displaystyle L(n,k)=\sum _{j}\left[{n \atop j}\right]\left\{{j \atop k}\right\},}$  where ${\displaystyle \left[{n \atop j}\right]}$  are the Stirling numbers of the first kind and ${\displaystyle \left\{{j \atop k}\right\}}$  are the Stirling numbers of the second kind, ${\displaystyle L(0,0)=1}$ , and ${\displaystyle L(n,k)=0}$  for all ${\displaystyle k>n}$ .

${\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)}$ , for ${\displaystyle k>0}$ .

So we have

${\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 L(n+1,k)=(n+k)L(n,k)+L(n,k-1)}$  where ${\displaystyle L(n,0)=0}$ , ${\displaystyle L(n,k)=0}$  for all ${\displaystyle k>n}$ 

Exponential generating function

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

Ordinary generating function

${\displaystyle \sum _{n\geq 0}L(n,k)x^{n}=x\prod _{k=1}^{\infty }{\frac {x+k}{1-kx}}}$ 

Practical application

In recent years, Lah numbers have been used in steganography for hiding data in images. Compared to alternatives such as DCT, DFT and DWT, it has lower complexity—${\displaystyle O(n\log n)}$ —of calculation of their integer coefficients.^[6][7] The Lah and Laguerre transforms naturally arise in the perturbative description of the chromatic dispersion^[8][9] . In Lah-Laguerre optics, such an approach tremendously speeds up optimization problems.

See also

• Stirling numbers
• Pascal matrix

References

1. Lah, Ivo (1954). "A new kind of numbers and its application in the actuarial mathematics". Boletim do Instituto dos Actuários Portugueses. 9: 7–15.
2. 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).
3. Daboul, Siad; Mangaldan, Jan; Spivey, Michael Z.; Taylor, Peter J. (2013). "The Lah Numbers and the nth Derivative of ${\displaystyle e^{1 \over x}}$ ". Mathematics Magazine. 86 (1): 39–47. doi:10.4169/math.mag.86.1.039. JSTOR 10.4169/math.mag.86.1.039. S2CID 123113404.
4. Petkovsek, Marko; Pisanski, Tomaz (Fall 2007). "Combinatorial Interpretation of Unsigned Stirling and Lah Numbers". Pi Mu Epsilon Journal. 12 (7): 417–424. JSTOR 24340704.
5. Comtet, Louis (1974). Advanced Combinatorics. Dordrecht, Holland: Reidel. p. 156. ISBN 9789027703804.
6. 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.
7. "Image Steganography-using-Lah-Transform". MathWorks.
8. Popmintchev, Dimitar; Wang, Siyang; Xiaoshi, Zhang; Stoev, Ventzislav; Popmintchev, Tenio (2022-10-24). "Analytical Lah-Laguerre optical formalism for perturbative chromatic dispersion". Optics Express. 30 (22): 40779–40808. Bibcode:2022OExpr..3040779P. doi:10.1364/OE.457139. PMID 36299007.
9. Popmintchev, Dimitar; Wang, Siyang; Xiaoshi, Zhang; Stoev, Ventzislav; Popmintchev, Tenio (2020-08-30). "Theory of the Chromatic Dispersion, Revisited". arXiv:2011.00066 [physics.optics].