Transformación binomial

En combinatoria , la transformada binomial es una transformación de secuencias (es decir, una transformación de una secuencia ) que calcula sus diferencias finitas hacia adelante . Está estrechamente relacionada con la transformada de Euler , que es el resultado de aplicar la transformada binomial a la secuencia asociada con su función generadora ordinaria .

La transformación binomial , T , de una secuencia, { a _n } , es la secuencia { s _n } definida por

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

Formalmente, uno puede escribir

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

para la transformación, donde T es un operador de dimensión infinita con elementos de matriz T _nk . La transformación es una involución , es decir,

$${\displaystyle TT=1}$$

o, utilizando notación de índices ,

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

dónde${\displaystyle \delta _{nm}}$es el delta de Kronecker . La serie original se puede recuperar mediante

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

La transformación binomial de una secuencia es simplemente la n -ésima diferencia hacia adelante de la secuencia, donde las diferencias impares llevan un signo negativo, a saber:

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

donde Δ es el operador de diferencia directa .

Algunos autores definen la transformación binomial con un signo adicional, de modo que no sea autoinversa:

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

cuyo inverso es

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

En este caso, la primera transformación se denomina transformación binomial inversa , y la segunda, simplemente transformación binomial . Este es el uso estándar, por ejemplo, en la Enciclopedia en línea de secuencias de enteros .

Ambas versiones de la transformación binomial aparecen en tablas de diferencias. Considere la siguiente tabla de diferencias:

Cada línea es la diferencia de la línea anterior. (El n -ésimo número en la m -ésima línea es a _{m , n} = 3 ^{n −2} (2 ^{m +1} n ² + 2 ^m (1+6 m ) n + 2 ^{m -1} 9 m ² ), y se cumple la ecuación de diferencias a _{m +1, n} = a _{m , n +1} - a _{m , n} ).

La línea superior leída de izquierda a derecha es { a _n } = 0, 1, 10, 63, 324, 1485, ... La diagonal con el mismo punto de partida 0 es { t _n } = 0, 1, 8, 36, 128, 400, ... { t _n } es la transformación binomial no involutiva de { a _n }.

La línea superior leída de derecha a izquierda es { b _n } = 1485, 324, 63, 10, 1, 0, ... La diagonal cruzada con el mismo punto de partida 1485 es { s _n } = 1485, 1161, 900, 692, 528, 400, ... { s _n } es la transformada binomial involutiva de { b _n }.

La transformación conecta las funciones generadoras asociadas a la serie. Para la función generadora ordinaria , sea

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

y

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

entonces

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

La relación entre las funciones generadoras ordinarias se denomina a veces transformada de Euler . Generalmente aparece de dos maneras diferentes. En una de ellas, se utiliza para acelerar la convergencia de una serie alternada . Es decir, se tiene la identidad

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

que se obtiene sustituyendo x = 1/2 en la última fórmula anterior. Los términos del lado derecho suelen volverse mucho más pequeños y con mayor rapidez, lo que permite una suma numérica rápida.

La transformada de Euler puede generalizarse (Borisov B. y Shkodrov V., 2007):

$${\displaystyle \sum _{n=0}^{\infty }{\left(-1\right)}^{n}{\binom {n+p}{n}}a_{n}=\sum _{n=0}^{\infty }{\left(-1\right)}^{n}{\binom {n+p}{n}}{\frac {(\Delta ^{n}a)_{0}}{2^{n+p+1}}},}$$

donde p = 0, 1, 2,... .

La transformada de Euler también se aplica frecuentemente a la integral hipergeométrica de Euler.${\displaystyle \,_{2}F_{1}}$Aquí, la transformada de Euler toma la forma:

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

[Véase ^{[ 1 ]} para generalizaciones a otras series hipergeométricas.]

La transformada binomial, y su variación como transformada de Euler, es notable por su conexión con la representación de fracciones continuas de un número.${\displaystyle 0<x<1}$tener la representación de fracción continua

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

entonces

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

y

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

Para la función generadora exponencial , sea

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

y

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

entonces

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

La transformada de Borel convertirá la función generatriz ordinaria en la función generatriz exponencial.

Dejar${\displaystyle (a_{n})_{n\in \mathbb {N} }}$y${\displaystyle (b_{n})_{n\in \mathbb {N} }}$sean secuencias de números complejos . Su convolución binomial se define por $${\displaystyle (a\circ b)_{n}=\sum _{k=0}^{n}{\binom {n}{k}}a_{k}b_{n-k},\ \ n=0,1,2,\ldots }$$ Esta convolución se puede encontrar en el libro de RL Graham, DE Knuth y O. Patashnik: Concrete Mathematics : A Foundation for Computer Science, Addison-Wesley (1989). Es fácil ver que la convolución binomial es asociativa y conmutativa, y la secuencia${\displaystyle \{e_{n}\}}$definido por${\displaystyle e_{0}=1}$y${\displaystyle e_{n}=0}$para${\displaystyle n=1,2,\ldots ,}$sirve como identidad bajo la convolución binomial. Además, es fácil ver que las secuencias${\displaystyle \{a_{n}\}}$con${\displaystyle a_{0}\neq 0}$poseen una inversa. Por lo tanto, el conjunto de secuencias${\displaystyle \{a_{n}\}}$con${\displaystyle a_{0}\neq 0}$forma un grupo abeliano bajo la convolución binomial.

La convolución binomial surge naturalmente del producto de las funciones generadoras exponenciales. De hecho, $${\displaystyle \left(\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}\right)\left(\sum _{n=0}^{\infty }b_{n}{\frac {x^{n}}{n!}}\right)=\sum _{n=0}^{\infty }(a\circ b)_{n}{\frac {x^{n}}{n!}}.}$$

La transformada binomial se puede escribir en términos de convolución binomial. Sea${\displaystyle \lambda _{n}=(-1)^{n}}$y${\displaystyle 1_{n}=1}$a pesar de${\displaystyle n}$. Entonces $${\displaystyle (Ta)_{n}=(\lambda a\circ 1)_{n}.}$$ La fórmula $${\displaystyle t_{n}=\sum _{k=0}^{n}{\left(-1\right)}^{n-k}{\binom {n}{k}}a_{k}\iff a_{n}=\sum _{k=0}^{n}{\binom {n}{k}}t_{k}}$$ puede interpretarse como una fórmula de inversión de tipo Möbius $${\displaystyle t_{n}=(a\circ \lambda )_{n}\iff a_{n}=(t\circ 1)_{n}}$$ desde${\displaystyle \lambda _{n}}$es lo inverso de ${\displaystyle 1_{n}}$ bajo la convolución binomial.

También existe otra convolución binomial en la literatura matemática. La convolución binomial de funciones aritméticas${\displaystyle f}$y${\displaystyle g}$se define como $${\displaystyle (f\circ _{B}g)(n)=\sum _{d\mid n}\left(\prod _{p}{\binom {\nu _{p}(n)}{\nu _{p}(d)}}\right)f(d)g(n/d),}$$ dónde${\displaystyle n=\prod _{p}p^{\nu _{p}(n)}}$es la factorización canónica de un entero positivo${\displaystyle n}$y${\displaystyle {\binom {\nu _{p}(n)}{\nu _{p}(d)}}}$es el coeficiente binomial . Esta convolución aparece en el libro de PJ McCarthy (1986) y fue estudiada posteriormente por L. Toth y P. Haukkanen (2009).

Cuando la secuencia puede interpolarse mediante una función analítica compleja , la transformada binomial de la secuencia puede representarse mediante una integral de Nörlund-Rice sobre la función interpoladora.

Prodinger ofrece una transformación relacionada, de tipo modular : dejando

$${\displaystyle u_{n}=\sum _{k=0}^{n}{\binom {n}{k}}a^{k}{\left(-c\right)}^{n-k}b_{k}}$$

da

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

donde U y B son las funciones generadoras ordinarias asociadas con la serie${\displaystyle \{u_{n}\}}$y${\displaystyle \{b_{n}\}}$, respectivamente.

La transformada k -binomial ascendente a veces se define como

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

La transformada k -binomial descendente es

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

Ambos son homomorfismos del núcleo de la transformada de Hankel de una serie .

En el caso en que la transformación binomial se define como

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

Sea esto igual a la función${\displaystyle {\mathfrak {J}}(a)_{n}=b_{n}.}$

Si se crea una nueva tabla de diferencias hacia adelante y se toman los primeros elementos de cada fila de esta tabla para formar una nueva secuencia${\displaystyle \{b_{n}\}}$, entonces la segunda transformación binomial de la secuencia original es,

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

Si el mismo proceso se repite k veces, entonces se deduce que,

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

Su inversa es,

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

Esto se puede generalizar como,

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

dónde${\displaystyle \mathbf {E} }$es el operador de turno .

Su inversa es

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

• Serie Newton
• Matriz de Hankel
• Transformación de Möbius
• Stirling transforma
• sumatoria de Euler
• QMF binomial
• Integral de Riemann-Liouville
• Lista de temas factoriales y binomiales

• John H. Conway y Richard K. Guy, 1996, El libro de los números
• Donald E. Knuth, El arte de la programación informática Vol. 3 , (1973) Addison-Wesley, Reading, MA.
• Helmut Prodinger, Información sobre la transformación binomial , The Fibonacci Quarterly 32 (1994), 412–415.
• Spivey, Michael Z.; Steil, Laura L. (2006). "Las transformadas k-binomiales y la transformada de Hankel" . Journal of Integer Sequences . 9 : 06.1.1. Bibcode : 2006JIntS...9...11S .
• Borisov, B.; Shkodrov, V. (2007). "Series divergentes en la transformada binomial generalizada" . Adv. Stud. Cont. Math . 14 (1): 77– 82.
• Khristo N. Boyadzhiev, Notas sobre la transformada binomial , teoría y tabla, con apéndice sobre la transformada de Stirling (2018), World Scientific.
• RL Graham, DE Knuth y O. Patashnik: Matemáticas concretas: una base para la informática, Addison-Wesley (1989).
• PJ McCarthy, Introducción a las funciones aritméticas, Springer-Verlag, 1986.
• P. Haukkanen, Sobre una convolución binomial de funciones aritméticas, Nieuw Arch. Wisk. (IV) 14 (1996), núm. 2, 209--216.
• L. Toth y P. Haukkanen, Sobre la convolución binomial de funciones aritméticas, J. Combinatorics and Number Theory 1(2009), 31–48.
• P. Haukkanen, Algunas inversiones binomiales en términos de funciones generadoras ordinarias. Publ. Math. Debr. 47, No. 1-2, 181-191 (1995).

• Transformación binomial en Wolfram MathWorld
• Transformación binomial en la wiki de OEIS