Лах саны - Lah number

Үшін қол қойылмаған Лах сандарының суреті n және к 1 мен 4 аралығында

Жылы математика, Лах сандарыарқылы ашылған Иво Лах 1954 жылы,^[1][2] болып табылады коэффициенттер білдіру өсіп келе жатқан факторлар жөнінде құлау факториалдары. Олар сондай-ақ коэффициенттері ${ displaystyle n}$туындылары ${ displaystyle e ^ {1 x}} үстінде$.^[3]

Қол қойылмаған Лах сандары қызықты мағынасы бар комбинаторика: олар жолдардың санын санайды а орнатылды туралы n элементтер болуы мүмкін бөлінді ішіне к бос емес сызықтық тапсырыс ішкі жиындар.^[4] Лах сандары байланысты Стирлинг сандары.^[5]

Қол қойылмаған Лах сандары (реттілігі) A105278 ішінде OEIS ):

${ displaystyle L (n, k) = {n-1 k-1} таңдаңыз { frac {n!} {k!}}.}$

Лах сандары (реттік) A008297 ішінде OEIS ):

${ displaystyle L '(n, k) = (- 1) ^ {n} {n-1 k-1} { frac {n!} {k!}} таңдаңыз.}$

L(n, 1) әрқашан n!; жоғарыдағы интерпретацияда {1, 2, 3} -ді 1 жиынға бөлудің жиынтығы 6 тәсілмен реттелуі мүмкін:

{(1, 2, 3)}, {(1, 3, 2)}, {(2, 1, 3)}, {(2, 3, 1)}, {(3, 1, 2)} немесе {(3, 2, 1)}

L(3, 2) тапсырыс берілген екі бөліктен тұратын 6 бөлімге сәйкес келеді:

{(1), (2, 3)}, {(1), (3, 2)}, {(2), (1, 3)}, {(2), (3, 1)}, {( 3), (1, 2)} немесе {(3), (2, 1)}

L(n, n) әрқашан 1 болады, өйткені, мысалы, {1, 2, 3} -ті бос емес 3 жиынға бөлу 1 ұзындықтағы ішкі жиындарға әкеледі.

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

Карамата-Кнут жазбаларын бейімдеу Стирлинг сандары, Лах сандарына келесі балама белгілерді қолдану ұсынылды:

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

Көтеріліп, құлап бара жатқан факторлар

Келіңіздер ${ displaystyle x ^ {(n)}}$ көтеріліп жатқан факторлықты білдіреді ${ displaystyle x (x + 1) (x + 2) cdots (x + n-1)}$ және рұқсат етіңіз ${ displaystyle (x) _ {n}}$ құлаған факториалды білдіреді ${ displaystyle x (x-1) (x-2) cdots (x-n + 1)}$.

Содан кейін ${ displaystyle x ^ {(n)} = sum _ {k = 1} ^ {n} L (n, k) (x) _ {k}}$ және ${ displaystyle (x) _ {n} = sum _ {k = 1} ^ {n} (- 1) ^ {n-k} L (n, k) x ^ {(k)}.}$

Мысалға,

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

Мәндер кестесінің үшінші жолын салыстырыңыз.

Тұлғалар және қатынастар

${ displaystyle L (n, k) = {n-1 k-1} { frac {n!} {k!}} = {n k} { frac {(n-1) таңдаңыз!} {(k-1)!}} = {n k} {n-1 таңдаңыз k-1} (nk) таңдаңыз!}$

${ displaystyle L (n, k) = { frac {n! (n-1)!} {k! (k-1)!}} cdot { frac {1} {(nk)!}} = солға ({ frac {n!} {k!}} оңға) ^ {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)})$ қайда ${ displaystyle L (n, 0) = 0}$, ${ displaystyle L (n, k) = 0}$ барлығына ${ displaystyle k> n}$, және ${ displaystyle L (1,1) = 1.}$

${ displaystyle L (n, k) = sum _ {j} сол [{n үстіңгі j} оң жақ] сол {{j ең жоғарғы k} оң },}$ қайда ${ displaystyle сол жақта [{n j} оң жақта]]$ болып табылады Стирлинг бірінші түрдегі нөмірлер және ${ displaystyle left {{j atop k} right }}$ болып табылады Стирлинг екінші түрдегі нөмірлер, ${ displaystyle L (0,0) = 1}$, және ${ displaystyle L (n, k) = 0}$ барлығына ${ 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!}} left ({ frac {x} {1-x}} right) ^ {k}}$

Мәндер кестесі

Төменде Лах сандарының мәндер кестесі берілген:

Сондай-ақ қараңыз

• Стирлинг сандары
• Паскаль матрицасы

Соңғы практикалық қолдану

Соңғы жылдары Lah нөмірі қолданылады Стеганография, кескінге жасырылған деректер. Зерттеушілер аз^{[6] [7]} Доктор сияқты Sudipta Kumar Ghosal оны осы доменде балама ретінде пайдаланды DCT, DFT және DWT күрделілігі төмен болғандықтан ${ displaystyle O (nlogn)}$ аталған түрлендірудің бүтін коэффициенттерін есептеу.

Әдебиеттер тізімі