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

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 th derivatives of .[3]

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):

Signed Lah numbers (sequence A008297 in the OEIS):

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 KaramataKnuth notation for Stirling numbers, it has been proposed to use the following alternative notation for Lah numbers:

Rising and falling factorials

Let represent the rising factorial and let represent the falling factorial .

Then and

For example,

Compare the third row of the table of values.

Identities and relations

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

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

Recent practical application

In recent years, Lah numbers have been used in steganography for hiding data in images. A few researchers,[6] [7] such as Dr Sudipta Kumar Ghosal, have exploited them in this domain as an alternative to DCT, DFT and DWT because of the low complexity——of calculation of their integer coefficients.

See also

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 ". 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.