Lah number

Summary

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 are given by the formula involving the binomial coefficient

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

for .

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

For , the Lah number is equal to the factorial in the interpretation above, the only partition of into 1 set can have its set ordered in 6 ways:

is equal to 6, because there are six partitions of into two ordered parts:
is always 1 because the only way to partition into non-empty subsets results in subsets of size 1, that can only be permuted in one way. In the more recent literature,[5][6] KaramataKnuth style notation has taken over. Lah numbers are now often written as

Table of values edit

Below is a table of values for the Lah numbers:

 k
n 
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   (sequence A000262 in the OEIS).

Rising and falling factorials edit

Let   represent the rising factorial   and let   represent the falling factorial  . The Lah numbers are the coefficients that express each of these families of polynomials in terms of the other. Explicitly,

 
and
 
For example,
 
and
 

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

Identities and relations edit

The Lah numbers satisfy a variety of identities and relations.

In KaramataKnuth notation for Stirling numbers

 
where   are the Stirling numbers of the first kind and   are the Stirling numbers of the second kind.
 
 
 , for  .

Recurrence relations edit

The Lah numbers satisfy the recurrence relations

 
where  , the Kronecker delta, and   for all  .

Exponential generating function edit

 

Derivative of exp(1/x) edit

The n-th derivative of the function   can be expressed with the Lah numbers, as follows[7]

 
For example,

 

 

 

Link to Laguerre polynomials edit

Generalized Laguerre polynomials   are linked to Lah numbers upon setting  

 
This formula is the default Laguerre polynomial in Umbral calculus convention.[8]

Practical application edit

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— —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 edit

References edit

  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. ^ Petkovsek, Marko; Pisanski, Tomaz (Fall 2007). "Combinatorial Interpretation of Unsigned Stirling and Lah Numbers". Pi Mu Epsilon Journal. 12 (7): 417–424. JSTOR 24340704.
  4. ^ Comtet, Louis (1974). Advanced Combinatorics. Dordrecht, Holland: Reidel. p. 156. ISBN 9789027703804.
  5. ^ Shattuck, Mark (2014). "Generalized r-Lah numbers". arXiv:1412.8721 [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. 338 (10): 1660–1666. doi:10.1016/j.disc.2014.03.029. ISSN 0012-365X.
  7. ^ Daboul, Siad; Mangaldan, Jan; Spivey, Michael Z.; Taylor, Peter J. (2013). "The Lah Numbers and the nth Derivative of  ". Mathematics Magazine. 86 (1): 39–47. doi:10.4169/math.mag.86.1.039. JSTOR 10.4169/math.mag.86.1.039. S2CID 123113404.
  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. 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). "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.
  10. ^ "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. Bibcode:2022OExpr..3040779P. doi:10.1364/OE.457139. PMID 36299007.
  12. ^ Popmintchev, Dimitar; Wang, Siyang; Xiaoshi, Zhang; Stoev, Ventzislav; Popmintchev, Tenio (2020-08-30). "Theory of the Chromatic Dispersion, Revisited". arXiv:2011.00066 [physics.optics].

External links edit

  • The signed and unsigned Lah numbers are respectively (sequence A008297 in the OEIS) and (sequence A105278 in the OEIS)