En mathématiques , les nombres de Lah , établis par Ivo Lah , permettent d’exprimer les factorielles croissantes en fonction des factorielles décroissantes et réciproquement.
Les nombres de Lah (signés) L (n , k ) (suite A008297 de l'OEIS ) sont définis[ 1] , [ 2] , [ 3] par :
x
n
¯
=
∑
k
(
−
1
)
n
L
(
n
,
k
)
x
k
_
{\displaystyle x^{\overline {n}}=\sum _{k}(-1)^{n}L(n,k)x^{\underline {k}}}
avec
x
n
¯
=
x
(
x
+
1
)
⋯
(
x
+
n
−
1
)
{\displaystyle x^{\overline {n}}=x(x+1)\cdots (x+n-1)}
factorielle croissante et
x
n
_
=
x
(
x
−
1
)
⋯
(
x
−
n
+
1
)
{\displaystyle x^{\underline {n}}=x(x-1)\cdots (x-n+1)}
factorielle décroissante , d’où :
∑
k
L
(
n
,
k
)
x
k
_
=
(
−
1
)
n
x
n
¯
=
(
−
x
)
n
_
{\displaystyle \sum _{k}L(n,k)x^{\underline {k}}=(-1)^{n}x^{\overline {n}}=(-x)^{\underline {n}}}
On montre (voir section #Expression directe ci-dessous) que L (n , k ) a pour signe (-1)n nombres de Stirling de première espèce , la notation de Karamata–Knuth désigne la version non signée des nombres de Lah (suite A105278 de l'OEIS ) :
⌊
n
k
⌋
=
|
L
(
n
,
k
)
|
=
(
−
1
)
n
L
(
n
,
k
)
{\displaystyle \left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor =|L(n,k)|=(-1)^{n}L(n,k)}
d’où :
x
n
¯
=
∑
k
⌊
n
k
⌋
x
k
_
{\displaystyle x^{\overline {n}}=\sum _{k}\left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor x^{\underline {k}}}
Relation inverse
x
n
_
=
∑
k
L
(
n
,
k
)
(
−
x
)
k
_
=
∑
k
(
−
1
)
k
L
(
n
,
k
)
x
k
¯
{\displaystyle x^{\underline {n}}=\sum _{k}L(n,k)(-x)^{\underline {k}}=\sum _{k}(-1)^{k}L(n,k)x^{\overline {k}}}
Démonstration
x
n
_
=
(
−
1
)
n
(
−
x
)
n
¯
=
(
−
1
)
n
∑
k
(
−
1
)
n
L
(
n
,
k
)
(
−
x
)
k
_
=
∑
k
L
(
n
,
k
)
(
−
x
)
k
_
{\displaystyle x^{\underline {n}}=(-1)^{n}(-x)^{\overline {n}}=(-1)^{n}\sum _{k}(-1)^{n}L(n,k)(-x)^{\underline {k}}=\sum _{k}L(n,k)(-x)^{\underline {k}}}
L
(
n
+
1
,
k
)
=
−
(
n
+
k
)
L
(
n
,
k
)
−
L
(
n
,
k
−
1
)
{\displaystyle L(n+1,k)=-(n+k)L(n,k)-L(n,k-1)}
L
(
0
,
k
)
=
δ
k
{\displaystyle L(0,k)=\delta _{k}}
symbole de Kronecker ).
Démonstration
Initialisation Le produit vide x 0 x , on a :
∑
k
L
(
0
,
k
)
x
k
_
=
(
−
x
)
0
_
=
1
=
x
0
_
=
∑
k
δ
k
x
k
_
{\displaystyle \sum _{k}L(0,k)x^{\underline {k}}=(-x)^{\underline {0}}=1=x^{\underline {0}}=\sum _{k}\delta _{k}x^{\underline {k}}}
Or les factorielles décroissantes constituent une base des polynômes, ce qui permet d’identifier les composantes à gauche et à droite.
Hérédité Par changement de variable k →k +1, on a
∑
k
L
(
n
,
k
−
1
)
x
k
_
=
∑
k
L
(
n
,
k
)
x
k
+
1
_
=
∑
k
(
x
−
k
)
L
(
n
,
k
)
x
k
_
{\displaystyle \sum _{k}L(n,k-1)x^{\underline {k}}=\sum _{k}L(n,k)x^{\underline {k+1}}=\sum _{k}(x-k)L(n,k)x^{\underline {k}}}
∑
k
[
(
n
+
k
)
L
(
n
,
k
)
+
L
(
n
,
k
−
1
)
]
x
k
_
=
∑
k
[
(
n
+
k
)
L
(
n
,
k
)
+
(
x
−
k
)
L
(
n
,
k
)
]
x
k
_
=
∑
k
(
x
+
n
)
L
(
n
,
k
)
x
k
_
=
(
x
+
n
)
(
−
x
)
n
_
=
−
(
−
x
)
n
+
1
_
=
−
∑
k
L
(
n
+
1
,
k
)
x
k
_
{\displaystyle \sum _{k}\left[(n+k)L(n,k)+L(n,k-1)\right]x^{\underline {k}}=\sum _{k}\left[(n+k)L(n,k)+(x-k)L(n,k)\right]x^{\underline {k}}=\sum _{k}(x+n)L(n,k)x^{\underline {k}}=(x+n)(-x)^{\underline {n}}=-(-x)^{\underline {n+1}}=-\sum _{k}L(n+1,k)x^{\underline {k}}}
Or les factorielles décroissantes constituent une base des polynômes, ce qui permet d’identifier les composantes à gauche et à droite.
Expression directe
Pour ,
L
(
n
,
k
)
=
(
−
1
)
n
(
n
−
1
k
−
1
)
n
!
k
!
=
(
−
1
)
n
(
n
k
)
(
n
−
1
)
!
(
k
−
1
)
!
=
(
−
1
)
n
(
n
k
)
(
n
−
1
k
−
1
)
(
n
−
k
)
!
=
(
−
1
)
n
n
!
(
n
−
1
)
!
k
!
(
k
−
1
)
!
(
n
−
k
)
!
{\displaystyle L(n,k)=(-1)^{n}{\binom {n-1}{k-1}}{\frac {n!}{k!}}=(-1)^{n}{\binom {n}{k}}{\frac {(n-1)!}{(k-1)!}}=(-1)^{n}{\binom {n}{k}}{\binom {n-1}{k-1}}(n-k)!=(-1)^{n}{\frac {n!(n-1)!}{k!(k-1)!(n-k)!}}}
Démonstration
Le coefficient binomial
(
−
1
−
1
)
{\displaystyle {\tbinom {-1}{-1}}}
n =k =0) n’étant pas défini, on commence par décaler à n =1 l’initialisation de la formule de récurrence de L :
L
(
1
,
k
)
=
−
k
L
(
0
,
k
)
−
L
(
0
,
k
−
1
)
=
−
k
δ
k
−
δ
k
−
1
=
−
δ
k
−
1
{\displaystyle L(1,k)=-kL(0,k)-L(0,k-1)=-k\delta _{k}-\delta _{k-1}=-\delta _{k-1}}
On pose ensuite
f
(
n
,
k
)
=
(
−
1
)
n
(
n
−
1
k
−
1
)
n
!
k
!
=
(
−
1
)
n
(
n
k
)
(
n
−
1
)
!
(
k
−
1
)
!
{\displaystyle f(n,k)=(-1)^{n}{\binom {n-1}{k-1}}{\frac {n!}{k!}}=(-1)^{n}{\binom {n}{k}}{\frac {(n-1)!}{(k-1)!}}}
sachant que
(
0
k
)
=
δ
k
{\displaystyle {\tbinom {0}{k}}=\delta _{k}}
f
(
1
,
k
)
=
(
−
1
)
1
(
0
k
−
1
)
1
!
k
!
=
−
δ
k
−
1
1
k
!
=
−
δ
k
−
1
{\displaystyle f(1,k)=(-1)^{1}{\binom {0}{k-1}}{\frac {1!}{k!}}=-\delta _{k-1}{\frac {1}{k!}}=-\delta _{k-1}}
sachant que
(
n
k
)
=
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
{\displaystyle {\tbinom {n}{k}}={\tbinom {n-1}{k}}+{\tbinom {n-1}{k-1}}}
f
(
n
+
1
,
k
)
=
(
−
1
)
n
+
1
(
n
+
1
k
)
n
!
(
k
−
1
)
!
=
−
(
−
1
)
n
[
(
n
k
)
+
(
n
k
−
1
)
]
n
!
(
k
−
1
)
!
=
−
(
−
1
)
n
[
(
n
k
)
+
(
n
−
1
k
−
1
)
+
(
n
−
1
k
−
2
)
]
n
!
(
k
−
1
)
!
=
−
[
(
−
1
)
n
(
n
k
)
n
(
n
−
1
)
!
(
k
−
1
)
!
+
(
−
1
)
n
(
n
−
1
k
−
1
)
k
n
!
k
!
+
(
−
1
)
n
(
n
−
1
k
−
2
)
n
!
(
k
−
1
)
!
]
=
−
[
n
f
(
n
,
k
)
+
k
f
(
n
,
k
)
+
f
(
n
,
k
−
1
)
]
=
−
(
n
+
k
)
f
(
n
,
k
)
−
f
(
n
,
k
−
1
)
{\displaystyle {\begin{aligned}f(n+1,k)&=(-1)^{n+1}{\binom {n+1}{k}}{\frac {n!}{(k-1)!}}\\&=-(-1)^{n}\left[{\binom {n}{k}}+{\binom {n}{k-1}}\right]{\frac {n!}{(k-1)!}}\\&=-(-1)^{n}\left[{\binom {n}{k}}+{\binom {n-1}{k-1}}+{\binom {n-1}{k-2}}\right]{\frac {n!}{(k-1)!}}\\&=-\left[(-1)^{n}{\binom {n}{k}}{\frac {n\,(n-1)!}{(k-1)!}}+(-1)^{n}{\binom {n-1}{k-1}}{\frac {k\,n!}{k!}}+(-1)^{n}{\binom {n-1}{k-2}}{\frac {n!}{(k-1)!}}\right]\\&=-\left[nf(n,k)+kf(n,k)+f(n,k-1)\right]\\&=-(n+k)f(n,k)-f(n,k-1)\end{aligned}}}
f et L ont donc même initialisation et même hérédité, d’où L =f .
Donc L (n , k ) a pour signe (-1)n
⌊
n
k
⌋
{\displaystyle \left\lfloor {\begin{smallmatrix}n\\k\end{smallmatrix}}\right\rfloor }
A105278 de l'OEIS ) :
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
Involution
∑
i
L
(
n
,
i
)
L
(
i
,
k
)
=
δ
n
,
k
{\displaystyle \sum _{i}L(n,i)L(i,k)=\delta _{n,k}}
avec δ n ,k symbole de Kronecker .
La matrice des L (n , k ) est donc involutive .
Démonstration
∑
k
[
∑
i
L
(
n
,
i
)
L
(
i
,
k
)
]
x
k
_
=
∑
i
L
(
n
,
i
)
[
∑
k
L
(
i
,
k
)
x
k
_
]
=
∑
i
L
(
n
,
i
)
(
−
x
)
i
_
=
x
n
_
=
∑
k
δ
n
,
k
x
k
_
{\displaystyle \sum _{k}\left[\sum _{i}L(n,i)L(i,k)\right]x^{\underline {k}}=\sum _{i}L(n,i)\left[\sum _{k}L(i,k)x^{\underline {k}}\right]=\sum _{i}L(n,i)(-x)^{\underline {i}}=x^{\underline {n}}=\sum _{k}\delta _{n,k}x^{\underline {k}}}
Or les factorielles décroissantes constituent une base des polynômes, ce qui permet d’identifier les composantes à gauche et à droite.
Les nombres de Lah non signés peuvent s’exprimer en fonction des nombres de Stirling
[
n
k
]
{\displaystyle \left[{\begin{smallmatrix}n\\k\end{smallmatrix}}\right]}
{
n
k
}
{\displaystyle \left\{{\begin{smallmatrix}n\\k\end{smallmatrix}}\right\}}
(de seconde espèce) :
⌊
n
k
⌋
=
∑
i
[
n
i
]
{
i
k
}
{\displaystyle \left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor =\sum _{i}{\begin{bmatrix}n\\i\end{bmatrix}}{\begin{Bmatrix}i\\k\end{Bmatrix}}}
Démonstration
On a
x
n
¯
=
∑
k
[
n
k
]
x
k
{\displaystyle x^{\overline {n}}=\sum _{k}{\begin{bmatrix}n\\k\end{bmatrix}}x^{k}}
x
n
=
∑
k
{
n
k
}
x
k
_
{\displaystyle x^{n}=\sum _{k}{\begin{Bmatrix}n\\k\end{Bmatrix}}x^{\underline {k}}}
∑
k
⌊
n
k
⌋
x
k
_
=
x
n
¯
=
∑
i
[
n
i
]
x
i
=
∑
i
[
n
i
]
(
∑
k
{
i
k
}
x
k
_
)
=
∑
k
(
∑
i
[
n
i
]
{
i
k
}
)
x
k
_
{\displaystyle \sum _{k}\left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor x^{\underline {k}}=x^{\overline {n}}=\sum _{i}{\begin{bmatrix}n\\i\end{bmatrix}}x^{i}=\sum _{i}{\begin{bmatrix}n\\i\end{bmatrix}}\left(\sum _{k}{\begin{Bmatrix}i\\k\end{Bmatrix}}x^{\underline {k}}\right)=\sum _{k}\left(\sum _{i}{\begin{bmatrix}n\\i\end{bmatrix}}{\begin{Bmatrix}i\\k\end{Bmatrix}}\right)x^{\underline {k}}}
Or les factorielles décroissantes constituent une base des polynômes, ce qui permet d’identifier les composantes à gauche et à droite.
Ils peuvent également s’exprimer en fonction des polynômes de Bell :
⌊
n
k
⌋
=
B
n
,
k
(
1
!
,
2
!
,
…
,
(
n
−
k
+
1
)
!
)
{\displaystyle \left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor =B_{n,k}\left(1!,2!,\dots ,(n-k+1)!\right)}
x )Les nombres de Lah permettent d'exprimer[ 4] n -ème de
e
1
x
{\displaystyle e^{\frac {1}{x}}}
:
d
n
d
x
n
e
1
x
=
e
1
x
∑
k
=
1
n
L
(
n
,
k
)
x
n
+
k
{\displaystyle {\frac {d^{n}}{dx^{n}}}e^{\frac {1}{x}}=e^{\frac {1}{x}}\sum _{k=1}^{n}{\frac {L(n,k)}{x^{n+k}}}}
Ces dernières années, les nombres de Lah ont été utilisés en stéganographie pour cacher des données dans des images. Par rapport aux alternatives telles que la DCT , la DFT et la DWT , elle présente une complexité moindre —
O
(
n
log
n
)
{\displaystyle O(n\log n)}
[ 5] , [ 6] dispersion chromatique [ 7] , [ 8]
↑ Lah 1954 . ↑ Lah 1955 . ↑ Riordan 2002 , p. 43–44. ↑ (en) S. Daboul, J. Mandalgan, M. Z. Spivey, P. J. Taylor, « The Lah Numbers and the n th Derivative of e1/x », Math. Mag vol. 86, no 1, 2013 , p. 39-47 (DOI 10.4169/math.mag.86.1.039 ↑ Sudipta Kr Ghosal , Souradeep Mukhopadhyay , Sabbir Hossain et Ram Sarkar , « Application of Lah Transform for Security and Privacy of Data through Information Hiding in Telecommunication », Transactions on Emerging Telecommunications Technologies , vol. 32, no 2, 2020 (DOI 10.1002/ett.3984 S2CID 225866797 ↑ « Image Steganography-using-Lah-Transform MathWorks ↑ Dimitar Popmintchev , Siyang Wang , Zhang Xiaoshi , Ventzislav Stoev et Tenio Popmintchev , « Analytical Lah-Laguerre optical formalism for perturbative chromatic dispersion », Optics Express vol. 30, no 22, 24 octobre 2022 , p. 40779–40808 (PMID 36299007 DOI 10.1364/OE.457139 Bibcode 2022OExpr..3040779P ↑ (en) Dimitar Popmintchev, Siyang Wang, Zhang Xiaoshi, Ventzislav Stoev et Tenio Popmintchev, « Theory of the Chromatic Dispersion, Revisited », 30 août 2020 .
Voir aussi
Bibliographie
(en) Ivo Lah, « A new kind of numbers and its application in the actuarial mathematics », Boletim do Instituto dos Actuários Portugueses Lisbonne , Instituto dos Actuários Portugueses, vol. 9, 1954 , p. 7–15 (ISSN 0443-4986, résumé ) (de) Ivo Lah, « Eine neue Art von Zahlen, ihre Eigenschaften und Anwendung in der mathematischen Statistik », Mitteilungsblatt für Mathematische Statistik Wurtzbourg , Physica-Verlag, vol. 7, 1955 , p. 203–212 (ISSN 0176-5531) (en) John Riordan, Introduction to Combinatorial Analysis , Dover Publications , 2002 (1re éd. 1958), 256 p. (ISBN 978-0-486-42536-8, lire en ligne )
Articles connexes
![{\displaystyle \sum _{k}\left[(n+k)L(n,k)+L(n,k-1)\right]x^{\underline {k}}=\sum _{k}\left[(n+k)L(n,k)+(x-k)L(n,k)\right]x^{\underline {k}}=\sum _{k}(x+n)L(n,k)x^{\underline {k}}=(x+n)(-x)^{\underline {n}}=-(-x)^{\underline {n+1}}=-\sum _{k}L(n+1,k)x^{\underline {k}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68f213483bb40c4bd44a2907024ede4a28c48842)
![{\displaystyle {\begin{aligned}f(n+1,k)&=(-1)^{n+1}{\binom {n+1}{k}}{\frac {n!}{(k-1)!}}\\&=-(-1)^{n}\left[{\binom {n}{k}}+{\binom {n}{k-1}}\right]{\frac {n!}{(k-1)!}}\\&=-(-1)^{n}\left[{\binom {n}{k}}+{\binom {n-1}{k-1}}+{\binom {n-1}{k-2}}\right]{\frac {n!}{(k-1)!}}\\&=-\left[(-1)^{n}{\binom {n}{k}}{\frac {n\,(n-1)!}{(k-1)!}}+(-1)^{n}{\binom {n-1}{k-1}}{\frac {k\,n!}{k!}}+(-1)^{n}{\binom {n-1}{k-2}}{\frac {n!}{(k-1)!}}\right]\\&=-\left[nf(n,k)+kf(n,k)+f(n,k-1)\right]\\&=-(n+k)f(n,k)-f(n,k-1)\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3ffeb99c360cd388504b700cbf440fa18a71fd98)
![{\displaystyle \sum _{k}\left[\sum _{i}L(n,i)L(i,k)\right]x^{\underline {k}}=\sum _{i}L(n,i)\left[\sum _{k}L(i,k)x^{\underline {k}}\right]=\sum _{i}L(n,i)(-x)^{\underline {i}}=x^{\underline {n}}=\sum _{k}\delta _{n,k}x^{\underline {k}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c241cf4d2e44bd8538ae22b02e301bdb6fff20c7)
![{\displaystyle \left[{\begin{smallmatrix}n\\k\end{smallmatrix}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d1f36fa7ed3809cd8d1deabf35a4e289e147470)
, Bibcode 2022OExpr..3040779P)
