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 \over 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\}\,}$$

Rising and falling 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).}$$

Compare the third row of the table of values.

Identities and relations

${\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+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}$, and ${\displaystyle L(1,1)=1.}$

${\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,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}}$

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

See also

• Stirling numbers
• Pascal matrix

Recent Practical Application

In most recent years, Lah Number is used in Steganography, data hiding in image. So few researchers[6] [7] like Dr. Sudipta Kumar Ghosal have exploited it in this domain as alternative of DCT, DFT and DWT because of low complexity ${\displaystyle O(nlogn)}$ of calculation of integer coefficients of the said transform.

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.
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. doi:10.1002/ett.3984.
7. "Image Steganography-using-Lah-Transform". MathWorks.