Binomial transformation

I kombinatorik är den binomala transformationen en sekvenstransformation (dvs. en transformation av en sekvens ) som beräknar dess framåtskridande skillnader . Den är nära besläktad med Euler-transformen , som är resultatet av att applicera binomialtransformen på sekvensen som är associerad med dess vanliga genererande funktion .

Definition

Den binomala transformen , T , för en sekvens, { a _n }, är sekvensen { s _n } definierad av

$s_{n}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}a_{k}.$

Formellt kan man skriva

$s_{n}=(Ta)_{n}=\summa _{k=0}^{n}T_{nk} a_{k}$

för transformationen, där T är en oändlig dimensionell operator med matriselement T _nk . Förvandlingen är en involution , det vill säga

$TT=1$

eller, med hjälp av indexnotation,

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

där $\delta _{nm}$ är Kroneckerdeltat . Originalserien kan återvinnas av

$a_{n}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}s_{k}.$

Den binomala transformationen av en sekvens är bara de n: te framåtriktade skillnaderna i sekvensen, med udda skillnader som bär ett negativt tecken, nämligen:

${\begin{aligned}s_{0}&=a_{0}\\s_{1}&=-(\Delta a)_ {0}=-a_{1}+a_{0}\\s_{2}&=(\Delta ^{2}a)_{0}=-(-a_{2}+a_{1})+ (-a_{1}+a_{0})=a_{2}-2a_{1}+a_{0}\\&\;\;\vdots \\s_{n}&=(-1)^{ n}(\Delta ^{n}a)_{0}\end{aligned}}$

där Δ är differensoperatorn framåt .

Vissa författare definierar den binomala transformationen med ett extra tecken, så att den inte är självinvers:

$t_{n}=\summa _{k=0}^{n}(-1)^{nk}{n \choose k}a_{k}$

vars invers är

$a_{n}=\sum _{k=0}^{n}{n \choose k}t_{k}.$

I det här fallet kallas den förra transformationen invers binomialtransform , och den senare är bara binomialtransform . Detta är standardanvändning till exempel i On-Line Encyclopedia of Integer Sequences .

Exempel

Båda versionerna av binomialtransformen visas i skillnadstabeller. Tänk på följande skillnadstabell:

0		1		10		63		324		1485
	1		9		53		261		1161
		8		44		208		900
			36		164		692
				128		528
					400

Varje rad är skillnaden från föregående rad. (Det n -:te talet på den m -:te raden är a _{m , n} = 3 ^{n −2} (2 ^{m +1} n ² + 2 ^m (1+6 m ) n + 2 ^{m -1} 9 m ² ), och differensekvationen a _{m +1, n} = a _{m , n +1} - a _{m , n} gäller.)

Den översta raden som läses från vänster till höger är { a _n } = 0, 1, 10, 63, 324, 1485, ... Diagonalen med samma startpunkt 0 är { t _n } = 0, 1, 8, 36 , 128, 400, ... { t _n } är den icke-involutiva binomialtransformen av { a _n }.

Den översta raden som läses från höger till vänster är { b _n } = 1485, 324, 63, 10, 1, 0, ... Tvärdiagonalen med samma startpunkt 1485 är { s _n } = 1485, 1161, 900 , 692, 528, 400, ... { s _n } är den involutiva binomialtransformen av { b _n }.

Vanlig genererande funktion

Transformen kopplar samman de genererande funktionerna som är associerade med serien. För den vanliga genereringsfunktionen låt

$f(x)=\summa _{n=0}^{\infty }a_{n}x^{n}$

och

$g(x)=\summa _{n=0}^{\infty }s_{n}x^{n}$

sedan

$g(x)=(Tf)(x)={\frac {1}{1-x}}f\left({\frac {-x}{1-x}}\right).$

Euler transformation

Relationen mellan de vanliga genererande funktionerna kallas ibland Eulertransformen . Det gör vanligtvis sitt utseende på ett av två olika sätt. I en form används den för att påskynda konvergensen av en alternerande serie . Det vill säga att man har identiteten

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

som erhålls genom att ersätta x = 1/2 i den sista formeln ovan. Termerna på höger sida blir vanligtvis mycket mindre, mycket snabbare, vilket möjliggör snabb numerisk summering.

Euler-transformen kan generaliseras (Borisov B. och Shkodrov V., 2007):

$\summa _{n=0}^{\infty }(-1)^{n}{n+p \choose n}a_{n}=\summa _{n=0}^{\infty }(-1)^ {n}{n+p \choose n}{\frac {(\Delta ^{n}a)_{0}}{2^{n+p+1}}},$

där p = 0, 1, 2,...

Euler-transformen tillämpas också ofta på Eulers hypergeometriska integral $\,_{2}F_{1}$ . Här tar Euler-transformen formen:

$\,_{2}F_{1}(a,b;c;z)=(1-z)^{-b}\,_{2}F_{1}\left(ca,b; c;{\frac {z}{z-1}}\höger).$

Den binomala transformationen, och dess variation som Euler-transformen, är anmärkningsvärd för sin koppling till den fortsatta bråkrepresentationen av ett tal. Låt $0<x<1$ ha den fortsatta bråkrepresentationen

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

sedan

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

och

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

Exponentiell genererande funktion

För den exponentiella genererande funktionen låt

${\overline {f}}(x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}$

och

${\overline {g}}(x)=\sum _{n=0}^{\infty }s_{n}{\frac {x^{n}}{n!}}$

sedan

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

Borel -transformen kommer att omvandla den vanliga genererande funktionen till den exponentiella genererande funktionen.

Integral representation

När sekvensen kan interpoleras med en komplex analytisk funktion, kan sekvensens binomiska transformation representeras med hjälp av en Nörlund–Rice-integral på den interpolerande funktionen.

Generaliseringar

Prodinger ger en relaterad, modulliknande transformation: uthyrning

$u_{n}=\summa _{k=0}^{n}{n \choose k}a^ {k}(-c)^{nk}b_{k}$

ger

$U(x)={\frac {1}{cx+1}}B\left({\frac {ax}{ cx+1}}\right)$

där U och B är de vanliga genererande funktionerna som är associerade med serierna $\{u_{n}\}$ respektive $\{b_{n}\}$ .

Den stigande k- binomialtransformen definieras ibland som

$\sum _{j=0}^{n}{n \choose j}j^{k}a_{j}.$

Den fallande k- binomialtransformen är

$\sum _{j=0}^{n}{n \choose j}j^{nk}a_{j}$ .

Båda är homomorfismer av kärnan i Hankeltransformeringen av en serie .

I det fall där binomialtransformen definieras som

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

Låt detta vara lika med funktionen ${\mathfrak {J}}(a)_{n}=b_{n}.$

Om en ny framåtriktad differenstabell görs och de första elementen från varje rad i denna tabell tas för att bilda en ny sekvens { $\displaystyle \{b_{n}\}},$ då den andra binomialtransformen av originalet sekvensen är,

${\mathfrak {J}}^{2}(a)_{n}=\sum _{i=0}^{n}(-2)^{ni}{\binom {n}{i }}a_{i}.$

Om samma process upprepas k gånger, följer det att,

${\mathfrak {J}}^{k}(a)_{n}=b_{n}=\sum _{i=0}^{n}(-k)^{ni}{\binom {n}{i}}a_{i}.$

Dess invers är,

${\mathfrak {J}}^{-k}(b)_{n}=a_{n}=\summa _{i=0}^{n}k^{ni}{\binom {n }{i}}b_{i}.$

Detta kan generaliseras som

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

där $\mathbf {E}$ är skiftoperatorn .

Dess omvända är

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

Se även

• Newton-serien
• Hankel matris
• Möbius transformation
• Stirlingförvandling
• Euler summering
• Binomial QMF
• Riemann–Liouville integral
• Lista över faktoriella och binomiska ämnen

• John H. Conway och Richard K. Guy, 1996, The Book of Numbers
• Donald E. Knuth, The Art of Computer Programming Vol. 3 , (1973) Addison-Wesley, Reading, MA.
• Helmut Prodinger, 1992, Lite information om den binomala transformationen
• Michael Z. Spivey och Laura L. Steil, 2006, The k-Binomial Transforms and the Hankel Transform
• Borisov B. och Shkodrov V., 2007, Divergent Series in the Generalized Binomial Transform, Adv. Hingst. forts. Math., 14 (1): 77-82
• Khristo N. Boyadzhiev, Notes on the Binomial Transform , Theory and Table, with Appendix on the Stirling Transform (2018), World Scientific.

externa länkar

• Binomial transformation
• Transformationer av heltalssekvenser