Binomická transformace - Binomial transform - Wikipedia

v kombinatorika, binomická transformace je sekvenční transformace (tj. transformace a sekvence ), který počítá jeho vpřed rozdíly. Úzce souvisí s Eulerova transformace, což je výsledek aplikace binomické transformace na sekvenci spojenou s její obyčejná generující funkce.

Definice

The binomická transformace, Tsekvence, {A_n}, je posloupnost {s_n} definován

${ displaystyle s_ {n} = součet _ {k = 0} ^ {n} (- 1) ^ {k} {n zvolte k} a_ {k}.}$

Formálně lze psát

${ displaystyle s_ {n} = (Ta) _ {n} = součet _ {k = 0} ^ {n} T_ {nk} a_ {k}}$

pro transformaci, kde T je nekonečně dimenzionální operátor s maticovými prvky T_nk. Transformace je involuce, to znamená,

${ displaystyle TT = 1 ,}$

nebo pomocí indexové notace,

${ displaystyle sum _ {k = 0} ^ { infty} T_ {nk} T_ {km} = delta _ {nm}}$

kde ${ displaystyle delta _ {nm}}$ je Kroneckerova delta. Původní série může být znovu získána

${ displaystyle a_ {n} = součet _ {k = 0} ^ {n} (- 1) ^ {k} {n zvolte k} s_ {k}.}$

Binomická transformace sekvence je právě nth vpřed rozdíly sekvence, s lichými rozdíly nesoucími záporné znaménko, jmenovitě:

${ displaystyle s_ {0} = a_ {0}}$

${ displaystyle s_ {1} = - ( Delta a) _ {0} = - a_ {1} + a_ {0}}$

${ displaystyle s_ {2} = ( Delta ^ {2} a) _ {0} = - (- a_ {2} + a_ {1}) + (- a_ {1} + a_ {0}) = a_ {2} -2a_ {1} + a_ {0}}$

${ displaystyle vdots ,}$

${ displaystyle s_ {n} = (- 1) ^ {n} ( Delta ^ {n} a) _ {0}}$

kde Δ je operátor dopředného rozdílu.

Někteří autoři definují binomickou transformaci znakem navíc, aby nebyla inverzní:

${ displaystyle t_ {n} = součet _ {k = 0} ^ {n} (- 1) ^ {n-k} {n zvolit k} a_ {k}}$

jehož inverzní je

${ displaystyle a_ {n} = součet _ {k = 0} ^ {n} {n zvolit k} t_ {k}.}$

V tomto případě se dřívější transformace nazývá inverzní binomická transformacea ten druhý je spravedlivý binomická transformace. Toto je standardní použití například v On-line encyklopedie celočíselných sekvencí.

Příklad

Binomické transformace lze vidět v rozdílových tabulkách. Zvažte následující:

Horní řádek 0, 1, 10, 63, 324, 1485, ... (posloupnost definovaná (2n² + n)3^n − 2) je (neinvolutivní verze) binomické transformace úhlopříčky 0, 1, 8, 36, 128, 400, ... (posloupnost definovaná n²2^n − 1).

Obyčejná generující funkce

Transformace spojuje generující funkce spojené se sérií. Pro obyčejná generující funkce, nechť

${ displaystyle f (x) = součet _ {n = 0} ^ { infty} a_ {n} x ^ {n}}$

a

${ displaystyle g (x) = součet _ {n = 0} ^ { infty} s_ {n} x ^ {n}}$

pak

${ displaystyle g (x) = (Tf) (x) = { frac {1} {1-x}} f vlevo ({ frac {-x} {1-x}} vpravo).}$

Eulerova transformace

Vztah mezi běžnými generujícími funkcemi se někdy nazývá Eulerova transformace. Obvykle se objevuje jedním ze dvou různých způsobů. V jedné formě je zvyklý urychlit konvergenci z střídavé řady. To znamená, že člověk má identitu

${ displaystyle sum _ {n = 0} ^ { infty} (- 1) ^ {n} a_ {n} = sum _ {n = 0} ^ { infty} (- 1) ^ {n} { frac { Delta ^ {n} a_ {0}} {2 ^ {n + 1}}}}$

který se získá dosazením X= 1/2 do posledního vzorce výše. Výrazy na pravé straně se obvykle mnohem zmenšují, mnohem rychleji, což umožňuje rychlé numerické shrnutí.

Eulerovu transformaci lze zobecnit (Borisov B. a Shkodrov V., 2007):

${ displaystyle sum _ {n = 0} ^ { infty} (- 1) ^ {n} {n + p zvolte n} a_ {n} = sum _ {n = 0} ^ { infty} (-1) ^ {n} {n + p vyberte n} { frac { Delta ^ {n} a_ {0}} {2 ^ {n + p + 1}}}}$,

kde str = 0, 1, 2,...

Eulerova transformace je také často aplikována na Eulerův hypergeometrický integrál ${ displaystyle , _ {2} F_ {1}}$. Zde má Eulerova transformace podobu:

${ displaystyle , _ {2} F_ {1} (a, b; c; z) = (1-z) ^ {- b} , _ {2} F_ {1} vlevo (ca, b; c; { frac {z} {z-1}} right).}$

Binomická transformace a její variace jako Eulerova transformace je pozoruhodná jeho spojením s pokračující zlomek reprezentace čísla. Nechat ${ displaystyle 0$ mít pokračující zlomkovou reprezentaci

${ displaystyle x = [0; a_ {1}, a_ {2}, a_ {3}, cdots]}$

pak

${ displaystyle { frac {x} {1-x}} = [0; a_ {1} -1, a_ {2}, a_ {3}, cdots]}$

a

${ displaystyle { frac {x} {1 + x}} = [0; a_ {1} + 1, a_ {2}, a_ {3}, cdots].}$

Funkce exponenciálního generování

Pro exponenciální generující funkce, nechť

${ displaystyle { overline {f}} (x) = součet _ {n = 0} ^ { infty} a_ {n} { frac {x ^ {n}} {n!}}}$

a

${ displaystyle { overline {g}} (x) = součet _ {n = 0} ^ { infty} s_ {n} { frac {x ^ {n}} {n!}}}$

pak

${ displaystyle { overline {g}} (x) = (T { overline {f}}) (x) = e ^ {x} { overline {f}} (- x).}$

The Borelova transformace převede běžnou generující funkci na exponenciální generující funkci.

Integrální zastoupení

Když lze sekvenci interpolovat pomocí a komplexní analytické funkci, pak lze binomickou transformaci posloupnosti reprezentovat pomocí a Nörlund – rýžový integrál na interpolační funkci.

Zobecnění

Prodinger dává související, modulární transformace: pronájem

${ displaystyle u_ {n} = součet _ {k = 0} ^ {n} {n zvolit k} a ^ {k} (- c) ^ {n-k} b_ {k}}$

dává

${ displaystyle U (x) = { frac {1} {cx + 1}} B vlevo ({ frac {ax} {cx + 1}} vpravo)}$

kde U a B jsou běžné generující funkce spojené s řadou ${ displaystyle {u_ {n} }}$ a ${ displaystyle {b_ {n} }}$, resp.

Povstání k-binomiální transformace je někdy definována jako

${ displaystyle sum _ {j = 0} ^ {n} {n vyberte j} j ^ {k} a_ {j}.}$

Padající k-binomiální transformace je

${ displaystyle sum _ {j = 0} ^ {n} {n vyberte j} j ^ {n-k} a_ {j}}$.

Oba jsou homomorfismy jádro z Hankelova transformace řady.

V případě, že je binomická transformace definována jako

${ displaystyle sum _ {i = 0} ^ {n} (- 1) ^ {n-i} { binom {n} {i}} a_ {i} = b_ {n}.}$

Nechť se to rovná funkci ${ displaystyle { mathfrak {J}} (a) _ {n} = b_ {n}.}$

Pokud nový vpřed rozdíl je vytvořena tabulka a první prvky z každého řádku této tabulky jsou vytvořeny pro vytvoření nové sekvence ${ displaystyle {b_ {n} }}$, pak je druhá binomická transformace původní sekvence,

${ displaystyle { mathfrak {J}} ^ {2} (a) _ {n} = součet _ {i = 0} ^ {n} (- 2) ^ {ni} { binom {n} {i }} a_ {i}.}$

Pokud se stejný proces opakuje k z toho vyplývá, že

${ displaystyle { mathfrak {J}} ^ {k} (a) _ {n} = b_ {n} = součet _ {i = 0} ^ {n} (- k) ^ {ni} { binom {n} {i}} a_ {i}.}$

Jeho inverzní je,

${ displaystyle { mathfrak {J}} ^ {- k} (b) _ {n} = a_ {n} = součet _ {i = 0} ^ {n} k ^ {ni} { binom {n } {i}} b_ {i}.}$

To lze zobecnit jako,

${ displaystyle { mathfrak {J}} ^ {k} (a) _ {n} = b_ {n} = ( mathbf {E} -k) ^ {n} a_ {0}}$

kde ${ displaystyle mathbf {E}}$ je operátor směny.

Jeho inverzní je

${ displaystyle { mathfrak {J}} ^ {- k} (b) _ {n} = a_ {n} = ( mathbf {E} + k) ^ {n} b_ {0}.}$

Viz také

• Newtonova řada
• Hankelova matice
• Möbiova transformace
• Stirlingova transformace
• Eulerův součet
• Seznam faktoriálních a binomických témat

Reference

• John H. Conway a Richard K. Guy, 1996, Kniha čísel
• Donald E. Knuth, Umění počítačového programování Sv. 3(1973) Addison-Wesley, Reading, MA.
• Helmut Prodinger, 1992, Některé informace o binomické transformaci
• Michael Z. Spivey a Laura L. Steil, 2006, K-binomické transformace a Hankelova transformace
• Borisov B. a Shkodrov V., 2007, Divergent Series in the Generalized Binomial Transform, Adv. Stud. Pokračování Math., 14 (1): 77-82
• Khristo N. Boyadzhiev, Poznámky k binomické transformaci, Theory and Table, with Annex on the Stirling Transform (2018), World Scientific.

externí odkazy

• Binomická transformace
• Transformace celočíselných sekvencí