Lah číslo - Lah number

Ilustrace nepodepsaných čísel Lah pro n a k mezi 1 a 4

v matematika, Lah čísla, objeveno uživatelem Ivo Lah v roce 1954,^[1][2] jsou koeficienty vyjadřování rostoucí faktoriály ve smyslu klesající faktoriály. Jsou také koeficienty ${ displaystyle n}$th deriváty ${ displaystyle e ^ {1 nad x}}$.^[3]

Nepodepsaná čísla Lah mít zajímavý význam v kombinatorika: počítají počet způsobů a soubor z n prvky mohou být rozdělené do k neprázdné lineárně seřazené podmnožiny.^[4] Lah čísla souvisí Stirlingova čísla.^[5]

Nepodepsaná čísla Lah (sekvence A105278 v OEIS ):

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

Podepsaná Lah čísla (sekvence A008297 v OEIS ):

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

L(n, 1) je vždy n!; ve výše uvedené interpretaci může mít jediný oddíl {1, 2, 3} do 1 sady svoji sadu uspořádanou 6 způsoby:

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

L(3, 2) odpovídá 6 oddílům se dvěma uspořádanými částmi:

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

L(n, n) je vždy 1, protože například rozdělení {1, 2, 3} na 3 neprázdné podmnožiny má za následek podmnožiny délky 1.

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

Přizpůsobení notace Karamata – Knuth pro Stirlingova čísla, bylo navrženo použít následující alternativní notaci pro Lah čísla:

$${ displaystyle L (n, k) = součet _ {j = 0} ^ {n} left [{ begin {matrix} n j end {matrix}} right] left {{ začátek {matice} j k konec {matice}} doprava } ,}$$

Rostoucí a klesající faktoriály

Nechat ${ displaystyle x ^ {(n)}}$ představují rostoucí faktoriál ${ displaystyle x (x + 1) (x + 2) cdots (x + n-1)}$ a nechte ${ displaystyle (x) _ {n}}$ představují klesající faktoriál ${ displaystyle x (x-1) (x-2) cdots (x-n + 1)}$.

Pak ${ displaystyle x ^ {(n)} = součet _ {k = 1} ^ {n} L (n, k) (x) _ {k}}$ a ${ displaystyle (x) _ {n} = součet _ {k = 1} ^ {n} (- 1) ^ {n-k} L (n, k) x ^ {(k)}.}$

Například,

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

Porovnejte třetí řádek tabulky hodnot.

Totožnosti a vztahy

${ displaystyle L (n, k) = {n-1 zvolit k-1} { frac {n!} {k!}} = {n zvolit k} { frac {(n-1)!} {(k-1)!}} = {n zvolit k} {n-1 vybrat 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 {n-k} {k (k + 1)}} L (n, k).}$

${ Displaystyle L (n + 1, k) = (n + k) L (n, k) + L (n, k-1)}$ kde ${ displaystyle L (n, 0) = 0}$, ${ displaystyle L (n, k) = 0}$ pro všechny ${ displaystyle k> n}$, a ${ displaystyle L (1,1) = 1.}$

${ displaystyle L (n, k) = součet _ {j} doleva [{n nahoře j} doprava] doleva {{j nahoře k} doprava },}$ kde ${ displaystyle left [{n nahoře j} right]}$ jsou Stirlingova čísla prvního druhu a ${ displaystyle left {{j nahoře k} vpravo }}$ jsou Stirlingova čísla druhého druhu, ${ displaystyle L (0,0) = 1}$, a ${ displaystyle L (n, k) = 0}$ pro všechny ${ displaystyle k> n}$.

${ displaystyle L (n, 1) = n!}$

${ displaystyle L (n, 2) = (n-1) n! / 2}$

${ displaystyle L (n, 3) = (n-2) (n-1) n! / 12}$

${ displaystyle L (n, n-1) = n (n-1)}$

${ displaystyle L (n, n) = 1}$

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

Tabulka hodnot

Níže je tabulka hodnot pro čísla Lah:

Viz také

• Stirlingova čísla
• Pascalova matice

Nedávná praktická aplikace

V posledních letech se Lah Number používá v Steganografie, data se skrývají v obraze. Tak málo vědců^{[6] [7]} jako Dr. Sudipta Kumar Ghosal využili v této doméně jako alternativu k DCT, DFT a DWT kvůli nízké složitosti ${ displaystyle O (nlogn)}$ výpočtu celočíselných koeficientů uvedené transformace.

Reference