Lah number explained

In mathematics, the (signed and unsigned) Lah numbers are coefficients expressing rising factorials in terms of falling factorials and vice versa. They were discovered by Ivo Lah in 1954.^{[1] [2]} Explicitly, the unsigned Lah numbers

$$L(n,k)\; =\; \backslash frac$$

for

n \geq k \geq 1 .

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.^[3] Lah numbers are related to Stirling numbers.^[4]

For $n\; \backslash geq\; 1$, the Lah number $L(n,\; 1)$ is equal to the factorial $n!$ in the interpretation above, the only partition of $\backslash$ into 1 set can have its set ordered in 6 ways:$$\backslash ,\; \backslash ,\; \backslash ,\; \backslash ,\; \backslash ,\; \backslash$$$L(3,\; 2)$ is equal to 6, because there are six partitions of $\backslash$ into two ordered parts:$$\backslash ,\; \backslash ,\; \backslash ,\; \backslash ,\; \backslash ,\; \backslash$$$L(n,\; n)$ is always 1 because the only way to partition $\backslash$ into

n non-empty subsets results in subsets of size 1, that can only be permuted in one way.In the more recent literature,^{[5] [6]} Karamata–Knuth style notation has taken over. Lah numbers are now often written as$$L(n,k)\; =\; \backslash left\backslash lfloor\; \backslash right\backslash rfloor$$

Table of values

Below is a table of values for the Lah numbers:

	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 $1,\; 1,\; 3,\; 13,\; 73,\; 501,\; 4051,\; 37633,\; \backslash dots$ .

Rising and falling factorials

Let $x^$ represent the rising factorial $x(x+1)(x+2)\; \backslash cdots\; (x+n-1)$ and let $(x)\_n$ represent the falling factorial $x(x-1)(x-2)\; \backslash cdots\; (x-n+1)$. The Lah numbers are the coefficients that express each of these families of polynomials in terms of the other. Explicitly,$$x^\; =\; \backslash sum\_^n\; L(n,k)\; (x)\_k$$and$$(x)\_n\; =\; \backslash sum\_^n\; (-1)^\; L(n,k)x^.$$For example,$$x(x+1)(x+2)\; =\; x\; +\; x(x-1)\; +\; x(x-1)(x-2)$$and$$x(x-1)(x-2)\; =\; x\; -\; x(x+1)\; +\; x(x+1)(x+2),$$

where the coefficients 6, 6, and 1 are exactly the Lah numbers

L( 3 , 1 ) , L( 3 , 2 ) , and L( 3 , 3 ) .

Identities and relations

The Lah numbers satisfy a variety of identities and relations.

In Karamata–Knuth notation for Stirling numbers$$L(n,k)\; =\; \backslash sum\_^n\; \backslash left[\{n\backslash atop\; j\}\backslash right]\; \backslash left\backslash$$where $\backslash left[\{n\backslash atop\; j\}\backslash right]$ are the Stirling numbers of the first kind and $\backslash left\backslash$ are the Stirling numbers of the second kind.

L(n,k) = {n -1 \choose k -1 } (n!)/(k!) = {n \choose k} ((n -1 )!)/((k -1 )!) = {n \choose k} {n -1 \choose k -1 } (n - k)! L(n,k) = (n!(n -1 )!)/(⋅ k!(k -1 )!) (1)/((n - k)!) = \left ( (n!)/(k!) \right ) ^{2 (k)/(n(n - k)!)} k(k +1 ) L(n,k +1 ) = (n - k) L(n,k) , for k> 0 .

Recurrence relations

The Lah numbers satisfy the recurrence relationswhere

L(n, 0 ) = \delta _{n} , the Kronecker delta, and L(n,k) =0 for all k > n .

Exponential generating function

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

Derivative of exp(1/x)

The n-th derivative of the function

e ^{(1 {x})/()} can be expressed with the Lah numbers, as follows^[7] $$\backslash frac\; e^\backslash frac1x\; =\; (-1)^n\; \backslash sum\_^n\; \backslash frac\; \backslash cdot\; e^\backslash frac1x.$$For example,(rm d)/(rm dx) e ^{(1 x)/(=)} - (1)/(x ^{2}) ⋅ e ^{(1 x)/()} (rm d ^{2})/(rm dx ^{2}) e ^{(1 {x})/(=)} (rm d)/(\left( - rm dx) (1 {x)/(^{2}}) e ^{(1 x)/()} \right) =- (-2)/(x ^{3}) ⋅ e ^{(1 x)/()} - (1 {x)/(^{2}}) ⋅ (-1)/(x ^{2}) ⋅ e ^{(1 x)/()} = \left( (2 {x)/(^{3}}) + (1 {x)/(^{4}\right)}) ⋅ e ^{(1 x)/()} (rm d ^{3})/(rm dx ^{3}) e ^{(1 {x})/(=)} (rm d)/(rm dx) \left( \left( (2 {x)/(^{3}}) + (1 {x)/(^{4}\right)}) ⋅ e ^{(1 x)/()} \right) = \left( (-6)/(x ^{4}) + (-4)/(x ^{5}) \right) ⋅ e ^{(1 x)/()} + \left( (2 {x)/(^{3}}) + (1 {x)/(^{4}\right)}) ⋅ (-1)/(x ^{2}) ⋅ e ^{(1 x)/()} =- \left( (6 {x)/(^{4}}) + (6 {x)/(^{5}}) + (1 {x)/(^{6}\right)}) ⋅ e ^{(1)/(x)}

Link to Laguerre polynomials

L ^{(\alpha)} _{n(x)} are linked to Lah numbers upon setting \alpha = -1 $$n!\; L\_n^(x)\; =\backslash sum\_^n\; L(n,k)\; (-x)^k$$This formula is the default Laguerre polynomial in Umbral calculus convention.^[8]

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 of calculation -

O(n log n) - of their integer coefficients.^{[9] [10]} The Lah and Laguerre transforms naturally arise in the perturbative description of the chromatic dispersion.^{[11] [12]} In Lah-Laguerre optics, such an approach tremendously speeds up optimization problems.

See also

• Stirling numbers
• Pascal matrix

References

1. Ivo . Lah . A new kind of numbers and its application in the actuarial mathematics . Boletim do Instituto dos Actuários Portugueses . 9 . 1954 . 7–15.
2. https://books.google.com/books?id=zWgIPlds29UC John Riordan, Introduction to Combinatorial Analysis
3. Combinatorial Interpretation of Unsigned Stirling and Lah Numbers . Marko . Petkovsek . Tomaz . Pisanski . Pi Mu Epsilon Journal . 12 . 7 . Fall 2007 . 417–424 . 24340704.
4. Book: Comtet, Louis . Advanced Combinatorics . Reidel . Dordrecht, Holland . 1974 . 156. 9789027703804 .
5. 1412.8721 . Mark . Shattuck . Generalized r-Lah numbers . 2014. math.CO .
6. Nyul . Gábor . Rácz . Gabriella . 2015-10-06 . The r-Lah numbers . Discrete Mathematics . Seventh Czech-Slovak International Symposium on Graph Theory, Combinatorics, Algorithms and Applications, Košice 2013 . en . 338 . 10 . 1660–1666 . 10.1016/j.disc.2014.03.029 . 0012-365X. 2437/213886 . free .
7. Daboul . Siad . Mangaldan . Jan . Spivey . Michael Z. . Taylor . Peter J. . 2013 . The Lah Numbers and the nth Derivative of e ^{1\over} . Mathematics Magazine . 86 . 39–47 . 10.4169/math.mag.86.1.039 . 10.4169/math.mag.86.1.039 . 123113404 . 1.
8. Rota . Gian-Carlo . Kahaner . D . Odlyzko . A . 1973-06-01 . On the foundations of combinatorial theory. VIII. Finite operator calculus . Journal of Mathematical Analysis and Applications . en . 42 . 3 . 684–760 . 10.1016/0022-247X(73)90172-8 . 0022-247X. free .
9. 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 . 10.1002/ett.3984. 225866797 .
10. Web site: Image Steganography-using-Lah-Transform . MathWorks. 5 June 2020 .
11. 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. 10.1364/OE.457139. free. 36299007 . 2022OExpr..3040779P.
12. Popmintchev. Dimitar. Wang. Siyang. Xiaoshi. Zhang . Stoev. Ventzislav. Popmintchev. Tenio. 2020-08-30. Theory of the Chromatic Dispersion, Revisited . physics.optics . 2011.00066.

External links

• The signed and unsigned Lah numbers are respectively and