Lah number

Last updated October 31, 2024

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

For ${\textstyle n\geq 1}$ , the Lah number ${\textstyle L(n,1)}$ is equal to the factorial ${\textstyle n!}$ in the interpretation above, the only partition of ${\textstyle \{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)\},\{(3,2,1)\}$ ${\textstyle L(3,2)}$ is equal to 6, because there are six partitions of ${\textstyle \{1,2,3\}}$ into two ordered parts: $\{1,(2,3)\},\{1,(3,2)\},\{2,(1,3)\},\{2,(3,1)\},\{3,(1,2)\},\{3,(2,1)\}$ ${\textstyle L(n,n)}$ is always 1 because the only way to partition ${\textstyle \{1,2,\ldots ,n\}}$ 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)=\left\lfloor {n \atop k}\right\rfloor$

Table of values

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 ${\textstyle 1,1,3,13,73,501,4051,37633,\dots }$ (sequence A000262 in the OEIS ).

Rising and falling factorials

Let ${\textstyle x^{(n)}}$ represent the rising factorial ${\textstyle x(x+1)(x+2)\cdots (x+n-1)}$ and let ${\textstyle (x)_{n}}$ represent the falling factorial ${\textstyle x(x-1)(x-2)\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^{(n)}=\sum _{k=0}^{n}L(n,k)(x)_{k}$ and $(x)_{n}=\sum _{k=0}^{n}(-1)^{n-k}L(n,k)x^{(k)}.$ For example, $x(x+1)(x+2)={\color {red}6}x+{\color {red}6}x(x-1)+{\color {red}1}x(x-1)(x-2)$ and $x(x-1)(x-2)={\color {red}6}x-{\color {red}6}x(x+1)+{\color {red}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)=\sum _{j=k}^{n}\left[{n \atop j}\right]\left\{{j \atop k}\right\}$ where ${\textstyle \left[{n \atop j}\right]}$ are the unsigned Stirling numbers of the first kind and ${\textstyle \left\{{j \atop k}\right\}}$ are the Stirling numbers of the second kind.

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

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)!}}

k(k+1)L(n,k+1)=(n-k)L(n,k)

, for

k>0

.

Recurrence relations

The Lah numbers satisfy the recurrence relations ${\begin{aligned}L(n+1,k)&=(n+k)L(n,k)+L(n,k-1)\\&=k(k+1)L(n,k+1)+2kL(n,k)+L(n,k-1)\end{aligned}}$ where $L(n,0)=\delta _{n}$ , the Kronecker delta, and $L(n,k)=0$ for all $k>n$ .

Exponential generating function

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

Derivative of exp(1/x)

The n-th derivative of the function $e^{\frac {1}{x}}$ can be expressed with the Lah numbers, as follows^[7] ${\frac {{\textrm {d}}^{n}}{{\textrm {d}}x^{n}}}e^{\frac {1}{x}}=(-1)^{n}\sum _{k=1}^{n}{\frac {L(n,k)}{x^{n+k}}}\cdot e^{\frac {1}{x}}.$ For example,

${\frac {\textrm {d}}{{\textrm {d}}x}}e^{\frac {1}{x}}=-{\frac {1}{x^{2}}}\cdot e^{\frac {1}{x}}$

${\frac {{\textrm {d}}^{2}}{{\textrm {d}}x^{2}}}e^{\frac {1}{x}}={\frac {\textrm {d}}{{\textrm {d}}x}}\left(-{\frac {1}{x^{2}}}e^{\frac {1}{x}}\right)=-{\frac {-2}{x^{3}}}\cdot e^{\frac {1}{x}}-{\frac {1}{x^{2}}}\cdot {\frac {-1}{x^{2}}}\cdot e^{\frac {1}{x}}=\left({\frac {2}{x^{3}}}+{\frac {1}{x^{4}}}\right)\cdot e^{\frac {1}{x}}$

${\frac {{\textrm {d}}^{3}}{{\textrm {d}}x^{3}}}e^{\frac {1}{x}}={\frac {\textrm {d}}{{\textrm {d}}x}}\left(\left({\frac {2}{x^{3}}}+{\frac {1}{x^{4}}}\right)\cdot e^{\frac {1}{x}}\right)=\left({\frac {-6}{x^{4}}}+{\frac {-4}{x^{5}}}\right)\cdot e^{\frac {1}{x}}+\left({\frac {2}{x^{3}}}+{\frac {1}{x^{4}}}\right)\cdot {\frac {-1}{x^{2}}}\cdot e^{\frac {1}{x}}=-\left({\frac {6}{x^{4}}}+{\frac {6}{x^{5}}}+{\frac {1}{x^{6}}}\right)\cdot e^{\frac {1}{x}}$

Link to Laguerre polynomials

Generalized Laguerre polynomials $L_{n}^{(\alpha )}(x)$ are linked to Lah numbers upon setting $\alpha =-1$ $n!L_{n}^{(-1)}(x)=\sum _{k=0}^{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.

Related Research Articles

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

In mathematics, the Bernoulli numbers $B n$ are a sequence of rational numbers which occur frequently in analysis. The Bernoulli numbers appear in the Taylor series expansions of the tangent and hyperbolic tangent functions, in Faulhaber's formula for the sum of m-th powers of the first n positive integers, in the Euler–Maclaurin formula, and in expressions for certain values of the Riemann zeta function.

In mathematics, the gamma function is the most common extension of the factorial function to complex numbers. Derived by Daniel Bernoulli, the gamma function $is defined for all complex numbers except non-positive integers, and for every positive integer, The gamma function can be defined via a convergent improper integral for complex numbers with positive real part:$

In mathematics, the Euler numbers are a sequence E_n of integers defined by the Taylor series expansion

In mathematics, a power series is an infinite series of the form $where a n represents the coefficient of the n th term and c is a constant called the center of the series. Power series are useful in mathematical analysis, where they arise as Taylor series of infinitely differentiable functions. In fact, Borel's theorem implies that every power series is the Taylor series of some smooth function.$

In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book Methodus differentialis (1730). They were rediscovered and given a combinatorial meaning by Masanobu Saka in 1782.

In mathematics, Stirling's approximation is an asymptotic approximation for factorials. It is a good approximation, leading to accurate results even for small values of $. It is named after James Stirling, though a related but less precise result was first stated by Abraham de Moivre.$

In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form, by some expression involving operations on the formal series.

<span class="mw-page-title-main">Harmonic number</span> Sum of the first n whole number reciprocals; 1/1 + 1/2 + 1/3 + ... + 1/n

In mathematics, the $n$ -th harmonic number is the sum of the reciprocals of the first $n$ natural numbers:

In mathematics, the falling factorial is defined as the polynomial

In mathematics, the double factorial of a number $n$ , denoted by $n ‼$ , is the product of all the positive integers up to $n$ that have the same parity as $n$ . That is,

In mathematics, the Laguerre polynomials, named after Edmond Laguerre (1834–1886), are nontrivial solutions of Laguerre's differential equation: $which is a second-order linear differential equation. This equation has nonsingular solutions only if n is a non-negative integer.$

In mathematics, a series is the sum of the terms of an infinite sequence of numbers. More precisely, an infinite sequence $defines a series S that is denoted$

In mathematics, particularly in combinatorics, a Stirling number of the second kind is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by $or . Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions. They are named after James Stirling.$

In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the unsigned Stirling numbers of the first kind count permutations according to their number of cycles.

In mathematics, the Stirling polynomials are a family of polynomials that generalize important sequences of numbers appearing in combinatorics and analysis, which are closely related to the Stirling numbers, the Bernoulli numbers, and the generalized Bernoulli polynomials. There are multiple variants of the Stirling polynomial sequence considered below most notably including the Sheffer sequence form of the sequence, $, defined characteristically through the special form of its exponential generating function, and the Stirling (convolution) polynomials,, which also satisfy a characteristic ordinary generating function and that are of use in generalizing the Stirling numbers to arbitrary complex-valued inputs. We consider the " convolution polynomial " variant of this sequence and its properties second in the last subsection of the article. Still other variants of the Stirling polynomials are studied in the supplementary links to the articles given in the references.$

<span class="mw-page-title-main">Eulerian number</span> Polynomial sequence

In combinatorics, the Eulerian number $is the number of permutations of the numbers 1 to in which exactly elements are greater than the previous element.$

In the mathematical theory of special functions, the Pochhammer k-symbol and the k-gamma function, introduced by Rafael Díaz and Eddy Pariguan are generalizations of the Pochhammer symbol and gamma function. They differ from the Pochhammer symbol and gamma function in that they can be related to a general arithmetic progression in the same manner as those are related to the sequence of consecutive integers.

In mathematics, a Carleman matrix is a matrix used to convert function composition into matrix multiplication. It is often used in iteration theory to find the continuous iteration of functions which cannot be iterated by pattern recognition alone. Other uses of Carleman matrices occur in the theory of probability generating functions, and Markov chains.

In mathematics, a transformation of a sequence's generating function provides a method of converting the generating function for one sequence into a generating function enumerating another. These transformations typically involve integral formulas applied to a sequence generating function or weighted sums over the higher-order derivatives of these functions.

References

↑ 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.
↑ 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).
↑ Petkovsek, Marko; Pisanski, Tomaz (Fall 2007). "Combinatorial Interpretation of Unsigned Stirling and Lah Numbers". Pi Mu Epsilon Journal. 12 (7): 417–424. JSTOR 24340704.
↑ Comtet, Louis (1974). Advanced Combinatorics. Dordrecht, Holland: Reidel. p. 156. ISBN 9789027703804.
↑ Shattuck, Mark (2014). "Generalized r-Lah numbers". arXiv: 1412.8721 [math.CO].
↑ 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. hdl: 2437/213886 . ISSN 0012-365X.
↑ Daboul, Siad; Mangaldan, Jan; Spivey, Michael Z.; Taylor, Peter J. (2013). "The Lah Numbers and the nth Derivative of $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.
↑ 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.
↑ 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.
↑ "Image Steganography-using-Lah-Transform". MathWorks. 5 June 2020.
↑ 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.
↑ 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

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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. hdl: 2437/213886 . ISSN 0012-365X.

[7] Daboul, Siad; Mangaldan, Jan; Spivey, Michael Z.; Taylor, Peter J. (2013). "The Lah Numbers and the nth Derivative of $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.

[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].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]