Transformada binomial

En combinatòria, la transformació binomial és una transformació de seqüències (és a dir, una transformació d'una seqüència) que calcula les seves diferències directes. Està estretament relacionada amb la transformada d'Euler, que és el resultat d'aplicar la transformada binomial a la seqüència associada a la seva funció generadora ordinària.

Definició

La transformada binomial, T, d'una seqüència, {a_n}, és la seqüència {s_n} definida per

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

Formalment, es pot escriure

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

per a la transformació, on T és un operador de dimensions infinites amb elements matricials T_nk. La transformació és una involució, és a dir,

$TT=1$

o, utilitzant la notació d'índex,

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

on $\delta _{nm}$ és el delta de Kronecker. La sèrie original es pot recuperar per

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

La transformada binomial d'una seqüència és només l'enèsima diferències directes de la seqüència, amb diferències senars que porten un signe negatiu, és a dir:

${\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}}$

on Δ és l'operador de diferència directa.

Alguns autors defineixen la transformada binomial amb un signe extra, de manera que no sigui autoinversa:

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

la inversa de la qual és

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

En aquest cas, la primera transformada s'anomena transformada binomial inversa, i la segona només és transformada binomial. Aquest és un ús estàndard, per exemple, a l'Enciclopèdia en línia de seqüències d'entiers.

Exemple

Les dues versions de la transformada binomial apareixen a les taules de diferències. Considereu la següent taula de diferències:

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

Cada línia és la diferència de la línia anterior. (L' n -è nombre de la m -a línia és a_{m, n} = 3^{n −2} (2^{m +1} n² + 2^m (1+6 m) ) n + 2^{m -1} 9 m²), i es compleix l'equació de diferència a _{m +1, n} = a _{m, n +1} - a _{m, n}.)

La línia superior llegida d'esquerra a dreta és {a_n} = 0, 1, 10, 63, 324, 1485,... La diagonal amb el mateix punt de partida 0 és { t _n } = 0, 1, 8, 36, 128, 400,... { t_n} és la transformada binomial no involutiva de {a_n}.

La línia superior llegida de dreta a esquerra és { b _n } = 1485, 324, 63, 10, 1, 0,... La diagonal creuada amb el mateix punt de partida 1485 és {s_n} = 1485, 1161, 900, 692, 528, 400,... {s_n} és la transformada binomial involutiva de {b_n}.

Funció generadora ordinària

La transformada connecta les funcions generadores associades a la sèrie. Per a la funció de generació ordinària, sigui

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

i

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

aleshores

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