Mathematical sequence
Illustration of the unsigned Lah numbers for n and k between 1 and 4 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
)
{\displaystyle L(n,k)}
are given by the formula involving the binomial coefficient
L
(
n
,
k
)
=
(
n
−
1
k
−
1
)
n
!
k
!
{\displaystyle L(n,k)={n-1 \choose k-1}{\frac {n!}{k!))}
for
n
≥
k
≥
1
{\displaystyle n\geq k\geq 1}
.
Unsigned Lah numbers have an interesting meaning in combinatorics : they count the number of ways a set of
n
{\textstyle n}
elements can be partitioned into
k
{\textstyle k}
nonempty linearly ordered subsets .[3] Lah numbers are related to Stirling numbers .[4]
For
n
≥
1
{\textstyle n\geq 1}
, the Lah number
L
(
n
,
1
)
{\textstyle L(n,1)}
is equal to the factorial
n
!
{\textstyle n!}
in the interpretation above, the only partition of
{
1
,
2
,
3
}
{\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
)
}
{\displaystyle \{(1,2,3)\},\{(1,3,2)\},\{(2,1,3)\},\{(2,3,1)\},\{(3,1,2)\},\{(3,2,1)\))
L
(
3
,
2
)
{\textstyle L(3,2)}
is equal to 6, because there are six partitions of
{
1
,
2
,
3
}
{\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
)
}
{\displaystyle \{1,(2,3)\},\{1,(3,2)\},\{2,(1,3)\},\{2,(3,1)\},\{3,(1,2)\},\{3,(2,1)\))
L
(
n
,
n
)
{\textstyle L(n,n)}
is always 1 because the only way to partition
{
1
,
2
,
…
,
n
}
{\textstyle \{1,2,\ldots ,n\))
into
n
{\displaystyle n}
non-empty subsets results in subsets of size 1, that can only be permuted in one way.
In the more recent litterature,[5] [6] Karamata –Knuth style notation has taken over. Lah numbers are now often written as
L
(
n
,
k
)
=
⌊
n
k
⌋
{\displaystyle 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
1
,
1
,
3
,
13
,
73
,
501
,
4051
,
37633
,
…
{\textstyle 1,1,3,13,73,501,4051,37633,\dots }
(sequence A000262 in the OEIS ).
Rising and falling factorials
Let
x
(
n
)
{\textstyle x^{(n)))
represent the rising factorial
x
(
x
+
1
)
(
x
+
2
)
⋯
(
x
+
n
−
1
)
{\textstyle x(x+1)(x+2)\cdots (x+n-1)}
and let
(
x
)
n
{\textstyle (x)_{n))
represent the falling factorial
x
(
x
−
1
)
(
x
−
2
)
⋯
(
x
−
n
+
1
)
{\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
)
=
∑
k
=
0
n
L
(
n
,
k
)
(
x
)
k
{\displaystyle x^{(n)}=\sum _{k=0}^{n}L(n,k)(x)_{k))
and
(
x
)
n
=
∑
k
=
0
n
(
−
1
)
n
−
k
L
(
n
,
k
)
x
(
k
)
.
{\displaystyle (x)_{n}=\sum _{k=0}^{n}(-1)^{n-k}L(n,k)x^{(k)}.}
For example,
x
(
x
+
1
)
(
x
+
2
)
=
6
x
+
6
x
(
x
−
1
)
+
1
x
(
x
−
1
)
(
x
−
2
)
{\displaystyle 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
)
=
6
x
−
6
x
(
x
+
1
)
+
1
x
(
x
+
1
)
(
x
+
2
)
,
{\displaystyle 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
)
{\displaystyle L(3,1)}
,
L
(
3
,
2
)
{\displaystyle L(3,2)}
, and
L
(
3
,
3
)
{\displaystyle 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
)
=
∑
j
=
k
n
[
n
j
]
{
j
k
}
{\displaystyle L(n,k)=\sum _{j=k}^{n}\left[{n \atop j}\right]\left\((j \atop k}\right\))
where
[
n
j
]
{\textstyle \left[{n \atop j}\right]}
are the Stirling numbers of the first kind and
{
j
k
}
{\textstyle \left\((j \atop k}\right\))
are the Stirling numbers of the second kind .
L
(
n
,
k
)
=
(
n
−
1
k
−
1
)
n
!
k
!
=
(
n
k
)
(
n
−
1
)
!
(
k
−
1
)
!
=
(
n
k
)
(
n
−
1
k
−
1
)
(
n
−
k
)
!
{\displaystyle 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
)
=
n
!
(
n
−
1
)
!
k
!
(
k
−
1
)
!
⋅
1
(
n
−
k
)
!
=
(
n
!
k
!
)
2
k
n
(
n
−
k
)
!
{\displaystyle 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
)
{\displaystyle k(k+1)L(n,k+1)=(n-k)L(n,k)}
, for
k
>
0
{\displaystyle k>0}
.
Recurrence relations
The Lah numbers satisfy the recurrence relations
L
(
n
+
1
,
k
)
=
(
n
+
k
)
L
(
n
,
k
)
+
L
(
n
,
k
−
1
)
=
k
(
k
+
1
)
L
(
n
,
k
+
1
)
+
2
k
L
(
n
,
k
)
+
L
(
n
,
k
−
1
)
{\displaystyle {\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
)
=
δ
n
{\displaystyle L(n,0)=\delta _{n))
, the Kronecker delta , and
L
(
n
,
k
)
=
0
{\displaystyle L(n,k)=0}
for all
k
>
n
{\displaystyle k>n}
.
Exponential generating function
∑
n
≥
k
L
(
n
,
k
)
x
n
n
!
=
1
k
!
(
x
1
−
x
)
k
{\displaystyle \sum _{n\geq k}L(n,k){\frac {x^{n)){n!))={\frac {1}{k!))\left({\frac {x}{1-x))\right)^{k))
Ordinary generating function
∑
n
≥
0
L
(
n
,
k
)
x
n
=
x
∏
k
=
1
∞
x
+
k
1
−
k
x
{\displaystyle \sum _{n\geq 0}L(n,k)x^{n}=x\prod _{k=1}^{\infty }{\frac {x+k}{1-kx))}
Derivative of exp(1/x )
The n -th derivative of the function
e
1
x
{\displaystyle e^{\frac {1}{x))}
can be expressed with the Lah numbers, as follows[7]
d
n
d
x
n
e
1
x
=
(
−
1
)
n
∑
k
=
1
n
L
(
n
,
k
)
x
n
+
k
⋅
e
1
x
.
{\displaystyle {\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,
d
d
x
e
1
x
=
−
1
x
2
⋅
e
1
x
{\displaystyle {\frac {\textrm {d))((\textrm {d))x))e^{\frac {1}{x))=-{\frac {1}{x^{2))}\cdot e^{\frac {1}{x))}
d
2
d
x
2
e
1
x
=
d
d
x
(
−
1
x
2
e
1
x
)
=
−
−
2
x
3
⋅
e
1
x
−
1
x
2
⋅
−
1
x
2
⋅
e
1
x
=
(
2
x
3
+
1
x
4
)
⋅
e
1
x
{\displaystyle {\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))}
d
3
d
x
3
e
1
x
=
d
d
x
(
(
2
x
3
+
1
x
4
)
⋅
e
1
x
)
=
(
−
6
x
4
+
−
4
x
5
)
⋅
e
1
x
+
(
2
x
3
+
1
x
4
)
⋅
−
1
x
2
⋅
e
1
x
=
−
(
6
x
4
+
6
x
5
+
1
x
6
)
⋅
e
1
x
{\displaystyle {\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))}
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
)
{\displaystyle 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.