Lah number
Template:Short description Template:Use American English
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.<ref>Template:Cite journal</ref><ref>John Riordan, Introduction to Combinatorial Analysis, Princeton University Press (1958, reissue 1980) Template:Isbn (reprinted again in 2002 by Dover Publications).</ref> Explicitly, the unsigned Lah numbers <math>L(n, k)</math> are given by the formula involving the binomial coefficient
<math display="block"> L(n,k) = {n-1 \choose k-1} \frac{n!}{k!}</math>
for <math>n \geq k \geq 1</math>.
Unsigned Lah numbers have an interesting meaning in combinatorics: they count the number of ways a set of <math display="inline">n</math> elements can be partitioned into <math display="inline">k</math> nonempty linearly ordered subsets.<ref>Template:Cite journal</ref> Lah numbers are related to Stirling numbers.<ref>Template:Cite book</ref>
For <math display="inline">n \geq 1</math>, the Lah number <math display="inline">L(n, 1)</math> is equal to the factorial <math display="inline">n!</math> in the interpretation above, the only partition of <math display="inline">\{1, 2, 3 \}</math> into 1 set can have its set ordered in 6 ways:<math display="block">\{(1, 2, 3)\}, \{(1, 3, 2)\}, \{(2, 1, 3)\}, \{(2, 3, 1)\}, \{(3, 1, 2)\}, \{(3, 2, 1)\}</math><math display="inline">L(3, 2)</math> is equal to 6, because there are six partitions of <math display="inline">\{1, 2, 3 \}</math> into two ordered parts:<math display="block">\{1, (2, 3) \}, \{1, (3, 2) \}, \{2, (1, 3) \}, \{2, (3, 1) \}, \{3, (1, 2) \}, \{3, (2, 1) \}</math><math display="inline">L(n, n)</math> is always 1 because the only way to partition <math display="inline">\{1, 2, \ldots, n\}</math> into <math>n</math> non-empty subsets results in subsets of size 1, that can only be permuted in one way. In the more recent literature,<ref>Template:Cite arXiv</ref><ref>Template:Cite journal</ref> Karamata–Knuth style notation has taken over. Lah numbers are now often written as<math display="block">L(n,k) = \left\lfloor {n \atop k} \right\rfloor</math>
Table of values
[edit]Below is a table of values for the Lah numbers:
| Template:Diagonal split header | 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 <math display="inline">1, 1, 3, 13, 73, 501, 4051, 37633, \dots</math> Template:OEIS.
Rising and falling factorials
[edit]Let <math display="inline">x^{(n)}</math> represent the rising factorial <math display="inline">x(x+1)(x+2) \cdots (x+n-1)</math> and let <math display="inline">(x)_n</math> represent the falling factorial <math display="inline">x(x-1)(x-2) \cdots (x-n+1)</math>. The Lah numbers are the coefficients that express each of these families of polynomials in terms of the other. Explicitly,<math display="block">x^{(n)} = \sum_{k=0}^n L(n,k) (x)_k</math>and<math display="block">(x)_n = \sum_{k=0}^n (-1)^{n-k} L(n,k)x^{(k)}.</math>For example,<math display="block">x(x+1)(x+2) = {\color{red}6}x + {\color{red}6}x(x-1) + {\color{red}1}x(x-1)(x-2)</math>and<math display="block">x(x-1)(x-2) = {\color{red}6}x - {\color{red}6}x(x+1) + {\color{red}1}x(x+1)(x+2),</math>
where the coefficients 6, 6, and 1 are exactly the Lah numbers <math>L(3, 1)</math>, <math>L(3, 2)</math>, and <math>L(3, 3)</math>.
Identities and relations
[edit]The Lah numbers satisfy a variety of identities and relations.
In Karamata–Knuth notation for Stirling numbers<math display="block"> L(n,k) = \sum_{j=k}^n \left[{n\atop j}\right] \left\{{j\atop k}\right\}</math>where <math display="inline">\left[{n\atop j}\right]</math> are the unsigned Stirling numbers of the first kind and <math display="inline">\left\{{j\atop k}\right\}</math> are the Stirling numbers of the second kind.
- <math> 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)!</math>
- <math> 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)!}</math>
- <math> k(k+1) L(n,k+1) = (n-k) L(n,k)</math>, for <math>k>0</math>.
Recurrence relations
The Lah numbers satisfy the recurrence relations<math display="block"> \begin{align} L(n+1,k) &= (n+k) L(n,k) + L(n,k-1) \\ &= k(k+1) L(n, k+1) + 2k L(n, k) + L(n, k-1) \end{align} </math>where <math>L(n,0)=\delta_n</math>, the Kronecker delta, and <math>L(n,k)=0</math> for all <math>k > n</math>.
Exponential generating function
- <math>\sum_{n\geq k} L(n,k)\frac{x^n}{n!} = \frac{1}{k!}\left( \frac{x}{1-x} \right)^k</math>
Derivative of exp(1/x)
The n-th derivative of the function <math>e^\frac1{x}</math> can be expressed with the Lah numbers, as follows<ref>Template:Cite journal</ref><math display="block"> \frac{\textrm d^n}{\textrm dx^n} e^\frac1x = (-1)^n \sum_{k=1}^n \frac{L(n,k)}{x^{n+k}} \cdot e^\frac1x.</math>For example,
<math> \frac{\textrm d}{\textrm dx} e^\frac1x = - \frac{1}{x^2} \cdot e^{\frac1x}</math>
<math> \frac{\textrm d^2}{\textrm dx^2}e^\frac1{x} = \frac{\textrm d}{\textrm dx} \left(-\frac1{x^2} e^{\frac1x} \right)= -\frac{-2}{x^3} \cdot e^{\frac1x} - \frac1{x^2} \cdot \frac{-1}{x^2} \cdot e^{\frac1x}= \left(\frac2{x^3} + \frac1{x^4}\right) \cdot e^{\frac1x}</math>
<math> \frac{\textrm d^3}{\textrm dx^3} e^\frac1{x} = \frac{\textrm d}{\textrm dx} \left( \left(\frac2{x^3} + \frac1{x^4}\right) \cdot e^{\frac1x} \right) = \left(\frac{-6}{x^4} + \frac{-4}{x^5}\right) \cdot e^{\frac1x} + \left(\frac2{x^3} + \frac1{x^4}\right) \cdot \frac{-1}{x^2} \cdot e^{\frac1x} =-\left(\frac6{x^4} + \frac6{x^5} + \frac1{x^6}\right) \cdot e^{\frac{1}{x}}</math>
Link to Laguerre polynomials
[edit]Generalized Laguerre polynomials <math>L^{(\alpha)}_n(x)</math> are linked to Lah numbers upon setting <math>\alpha = -1</math><math display="block"> n! L_n^{(-1)}(x) =\sum_{k=0}^n L(n,k) (-x)^k</math>This formula is the default Laguerre polynomial in Umbral calculus convention.<ref>Template:Cite journal</ref>
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—<math>O(n \log n)</math>—of their integer coefficients.<ref>Template:Cite journal</ref><ref>Template:Cite web</ref> The Lah and Laguerre transforms naturally arise in the perturbative description of the chromatic dispersion.<ref>Template:Cite journal</ref><ref>Template:Cite arXiv</ref> In Lah-Laguerre optics, such an approach tremendously speeds up optimization problems.
See also
[edit]References
[edit]<references />
External links
[edit]- The signed and unsigned Lah numbers are respectively Template:OEIS and Template:OEIS