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(\genfrac{}{}{0ex}{}{n}{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}^{\mathrm{\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(\genfrac{}{}{0ex}{}{n}{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{array}{cc}{s}_0& =a_0\\ s_1& =-(\mathrm{\Delta }a{)}_0=-a_1+a_0\\ s_2& =({\mathrm{\Delta }}^{2}a{)}_0=-(-a_2+a_1)+(-a_1+a_0)=a_2-2a_1+a_0\\ & ⋮\\ s_n& =(-1{)}^n({\mathrm{\Delta }}^{n}a{)}_0\end{array}$

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}(\genfrac{}{}{0ex}{}{n}{k})a_k$

la inversa de la qual és

$a_n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{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}^{\mathrm{\infty }}{a}_n{x}^n$

i

$g(x)=\sum _{n=0}^{\mathrm{\infty }}{s}_n{x}^n$

aleshores

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