Numéro de Lah - Lah number

Illustration des nombres de Lah non signés pour n et k compris entre 1 et 4

En mathématiques , les nombres de Lah , découverts par Ivo Lah en 1954, sont des coefficients exprimant des factorielles croissantes en termes de factorielles décroissantes . Ce sont aussi les coefficients des dérivées e de . ${\style d'affichage n}$${\displaystyle e^{1/x}}$

Les nombres de Lah non signés ont une signification intéressante en combinatoire : ils comptent le nombre de façons dont un ensemble de n éléments peut être partitionné en k sous- ensembles linéairement ordonnés non vides . Les nombres de Lah sont liés aux nombres de Stirling .

Numéros de Lah non signés (séquence A105278 dans l' OEIS ):

${\displaystyle L(n,k)={n-1 \choisissez k-1}{\frac {n!}{k!}}.}$

Numéros de Lah signés (séquence A008297 dans l' OEIS ) :

${\displaystyle L'(n,k)=(-1)^{n}{n-1 \choisissez k-1}{\frac {n!}{k!}}.}$

L ( n , 1) est toujours n !; dans l'interprétation ci-dessus, la seule partition de {1, 2, 3} en 1 ensemble peut avoir son ensemble ordonné de 6 manières :

{(1, 2, 3)}, {(1, 3, 2)}, {(2, 1, 3)}, {(2, 3, 1)}, {(3, 1, 2)} ou {(3, 2, 1)}

L (3, 2) correspond aux 6 cloisons avec deux parties ordonnées :

{(1), (2, 3)}, {(1), (3, 2)}, {(2), (1, 3)}, {(2), (3, 1)}, {( 3), (1, 2)} ou {(3), (2, 1)}

L ( n , n ) est toujours égal à 1 puisque, par exemple, le partitionnement de {1, 2, 3} en 3 sous-ensembles non vides donne des sous-ensembles de longueur 1.

{(1), (2), (3)}

En adaptant la notation Karamata – Knuth pour les nombres de Stirling , il a été proposé d'utiliser la notation alternative suivante pour les nombres de Lah :

$${\displaystyle L(n,k)=\sum _{j=0}^{n}\left[{\begin{matrix}n\\j\end{matrix}}\right]\left\{{\ commencer{matrice}j\\k\end{matrice}}\right\}}$$

Factorielles montantes et descendantes

Soit la factorielle montante et la factorielle descendante . ${\style d'affichage x^{(n)}}$${\style d'affichage x(x+1)(x+2)\cdots (x+n-1)}$${\style d'affichage (x)_{n}}$${\style d'affichage x(x-1)(x-2)\cdots (x-n+1)}$

Puis et${\displaystyle x^{(n)}=\sum _{k=1}^{n}L(n,k)(x)_{k}}$${\displaystyle (x)_{n}=\sum _{k=1}^{n}(-1)^{nk}L(n,k)x^{(k)}.}$

Par example,

$${\displaystyle x(x+1)(x+2)={\color {red}6}x+{\color {red}6}x(x-1)+{\color {red}1}x(x -1)(x-2).}$$

Comparez la troisième ligne du tableau des valeurs.

Identités et relations

${\displaystyle L(n,k)={n-1 \choisissez k-1}{\frac {n!}{k!}}={n \choisissez k}{\frac {(n-1)!} {(k-1)!}}={n \choisissez k}{n-1 \choisissez k-1}(nk)!}$

${\displaystyle L(n,k)={\frac {n!(n-1)!}{k!(k-1)!}}\cdot {\frac {1}{(nk)!}}= \left({\frac {n!}{k!}}\right)^{2}{\frac {k}{n(nk)!}}}$

${\displaystyle L(n,k+1)={\frac {nk}{k(k+1)}}L(n,k).}$

${\style d'affichage L(n+1,k)=(n+k)L(n,k)+L(n,k-1)}$où , pour tout , et${\style d'affichage L(n,0)=0}$${\style d'affichage L(n,k)=0}$${\style d'affichage k>n}$${\style d'affichage L(1,1)=1.}$

${\displaystyle L(n,k)=\sum _{j}\left[{n \atop j}\right]\left\{{j \atop k}\right\},}$où sont les nombres de Stirling du premier genre et sont les nombres de Stirling du deuxième genre , , et pour tous .${\displaystyle \left[{n \atop j}\right]}$${\displaystyle \left\{{j \atop k}\right\}}$${\style d'affichage L(0,0)=1}$${\style d'affichage L(n,k)=0}$${\style d'affichage k>n}$

${\style d'affichage L(n,1)=n!}$

${\style d'affichage L(n,2)=(n-1)n!/2}$

${\style d'affichage L(n,3)=(n-2)(n-1)n!/12}$

${\style d'affichage L(n,n-1)=n(n-1)}$

${\style d'affichage L(n,n)=1}$

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

Tableau des valeurs

Vous trouverez ci-dessous un tableau de valeurs pour les nombres de Lah :

Application pratique récente

Ces dernières années, les nombres de Lah ont été utilisés en stéganographie pour masquer des données dans des images. Quelques chercheurs, comme le Dr Sudipta Kumar Ghosal, les ont exploitées dans ce domaine comme alternative aux DCT , DFT et DWT en raison de la faible complexité — — du calcul de leurs coefficients entiers. ${\displaystyle O(n\log n)}$

Voir également

• Chiffres de Stirling
• Matrice pascale

Les références