Nombre de Lah
# Nombre de Lah

En mathématiques, les nombres de Lah, établis par Ivo Lah (en), permettent d’exprimer les factorielles croissantes en fonction des factorielles décroissantes et réciproquement.

## Définitions

Les nombres de Lah (signés) L(n, k) (suite A008297 de l'OEIS) sont $définis^,^,$ par :

    $x^{\overline {n}}=\sum _{k}(-1)^{n}L(n,k)x^{\underline {k}}$

avec $x^{\overline {n}}=x(x+1)\cdots (x+n-1)$ la factorielle croissante et $x^{\underline {n}}=x(x-1)\cdots (x-n+1)$ la factorielle décroissante, d’où :

    $\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.$ De même que pour les 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) :

    $\left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor =|L(n,k)|=(-1)^{n}L(n,k)$,

d’où :

    $x^{\overline {n}}=\sum _{k}\left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor x^{\underline {k}}$.

## Propriétés

### Relation inverse

    $x^{\underline {n}}=\sum _{k}L(n,k)(-x)^{\underline {k}}=\sum _{k}(-1)^{k}L(n,k)x^{\overline {k}}$.
    $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}}$.

### Formule de récurrence

    $L(n+1,k)=-(n+k)L(n,k)-L(n,k-1)$ avec $L(0,k)=\delta _{k}$ (symbole de Kronecker).

**Initialisation**

Le produit vide $x^0$ valant 1 pour tout x, on a :

    $\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 $\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}}$, d’où :

    $\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 n>0, $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)!}}$.

Le coefficient binomial ${\tbinom {-1}{-1}}$ (lorsque 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)=-kL(0,k)-L(0,k-1)=-k\delta _{k}-\delta _{k-1}=-\delta _{k-1}$.

On pose ensuite $f(n,k)=(-1)^{n}{\binom {n-1}{k-1}}{\frac {n!}{k!}}=(-1)^{n}{\binom {n}{k}}{\frac {(n-1)!}{(k-1)!}}$, d’où :

* sachant que ${\tbinom {0}{k}}=\delta _{k}$, on a :

       $f(1,k)=(-1)^{1}{\binom {0}{k-1}}{\frac {1!}{k!}}=-\delta _{k-1}{\frac {1}{k!}}=-\delta _{k-1}$ ;
* sachant que ${\tbinom {n}{k}}={\tbinom {n-1}{k}}+{\tbinom {n-1}{k-1}}$, on a :

       ${\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,$ d’où l’expression de $\left\lfloor {\begin{smallmatrix}n\\k\end{smallmatrix}}\right\rfloor$.

### Involution

    $\sum _{i}L(n,i)L(i,k)=\delta _{n,k}$

avec $δ_{n,k}$ le symbole de Kronecker. La matrice des L(n, k) est donc involutive.

    $\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.

### Autres propriétés

Les nombres de Lah non signés peuvent s’exprimer en fonction des nombres de Stirling $\left[{\begin{smallmatrix}n\\k\end{smallmatrix}}\right]$ (de première espèce non signés) et $\left\{{\begin{smallmatrix}n\\k\end{smallmatrix}}\right\}$ (de seconde espèce) :

    $\left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor =\sum _{i}{\begin{bmatrix}n\\i\end{bmatrix}}{\begin{Bmatrix}i\\k\end{Bmatrix}}$.

On a $x^{\overline {n}}=\sum _{k}{\begin{bmatrix}n\\k\end{bmatrix}}x^{k}$ et $x^{n}=\sum _{k}{\begin{Bmatrix}n\\k\end{Bmatrix}}x^{\underline {k}}$, d’où :

    $\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 :

    $\left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor =B_{n,k}\left(1!,2!,\dots ,(n-k+1)!\right)$.

### Dérivée de exp(1/x)

Les nombres de Lah permettent d'exprimer la dérivée n-ème de $e^{\frac {1}{x}}$ :

    ${\frac {d^{n}}{dx^{n}}}e^{\frac {1}{x}}=e^{\frac {1}{x}}\sum _{k=1}^{n}{\frac {L(n,k)}{x^{n+k}}}$

## Application pratique récente

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)$—de calcul de leurs coefficients $entiers^,.$ Les transformées de Lah et de Laguerre apparaissent naturellement dans la description perturbative de la dispersion $chromatique^,.$ En optique de Lah-Laguerre, une telle approche accélère considérablement les problèmes d'optimisation.

