Transformación de una secuencia matemática.
En combinatoria , la transformada binomial es una transformación de secuencia (es decir, una transformación de una secuencia ) que calcula sus diferencias directas . Está estrechamente relacionada con la transformada de Euler , que es el resultado de aplicar la transformada binomial a la secuencia asociada a su función generadora ordinaria .
Definición
La transformada binomial , T , de una secuencia, { a n }, es la secuencia { s n } definida por
![{\displaystyle s_{n}=\sum _ {k=0}^{n}(-1)^{k}{n \choose k}a_{k}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Formalmente, se puede escribir
![{\displaystyle s_{n}=(Ta)_{n}=\sum _{k=0}^{n}T_{nk}a_{k}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
para la transformación, donde T es un operador de dimensión infinita con elementos matriciales T nk . La transformada es una involución , es decir,
![{\displaystyleTT=1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
o, usando notación de índice,
![{\displaystyle \sum _{k=0}^{\infty }T_{nk}T_{km}=\delta _{nm}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
¿Dónde está el delta del Kronecker ? La serie original se puede recuperar mediante![{\displaystyle \delta _{nm}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle a_{n}=\sum _ {k=0}^{n}(-1)^{k}{n \choose k}s_{k}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La transformada binomial de una secuencia es solo la enésima diferencia directa de la secuencia, y 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}\ fin {alineado}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
donde Δ es el operador de diferencia directa .
Algunos autores definen la transformada binomial con un signo extra, para que no sea autoinversa:
![{\displaystyle t_{n}=\sum _ {k=0}^{n}(-1)^{nk}{n \choose k}a_{k}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
cuyo inverso es
![{\displaystyle a_{n}=\sum _ {k=0}^{n}{n \choose k}t_{k}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
En este caso, la primera transformación se llama transformación binomial inversa y la última es simplemente transformación binomial . Este es un uso estándar, por ejemplo, en la Enciclopedia en línea de secuencias enteras .
Ejemplo
Ambas versiones de la transformada 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 + 2 m (1+6 m ) n + 2 m -1 9 m 2 ), y la ecuación en diferencias a m +1, n = a m , n +1 - a m , n se cumple.)
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 inicial 0 es { t n } = 0, 1, 8, 36 , 128, 400, ... { t n } es la transformada 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 inicial 1485 es { s n } = 1485, 1161, 900 , 692, 528, 400, ... { s n } es la transformada binomial involutiva de { b n }.
Función generadora ordinaria
La transformada conecta las funciones generadoras asociadas con la serie. Para la función generadora ordinaria , sea
![{\displaystyle f(x)=\sum _{n=0}^{\infty }a_{n}x^{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
y
![{\displaystyle g(x)=\sum _{n=0}^{\infty }s_{n}x^{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
entonces
![{\displaystyle g(x)=(Tf)(x)={\frac {1}{1-x}}f\left({\frac {-x}{1-x}}\right).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
transformada de Euler
La relación entre las funciones generadoras ordinarias a veces se denomina transformada de Euler . Por lo general, aparece de dos maneras diferentes. En una forma, se utiliza para acelerar la convergencia de una serie alterna . Es decir, uno tiene la identidad
![{\displaystyle \sum _{n=0}^{\infty }(-1)^{n}a_{n}=\sum _{n=0}^{\infty }(-1)^{n} {\frac {(\Delta ^{n}a)_{0}}{2^{n+1}}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
que se obtiene sustituyendo x = 1/2 en la última fórmula anterior. Los términos del lado derecho normalmente se vuelven mucho más pequeños y mucho más rápidamente, lo que permite una rápida suma numérica.
La transformada de Euler se puede generalizar (Borisov B. y Shkodrov V., 2007):
![{\displaystyle \sum _{n=0}^{\infty }(-1)^{n}{n+p \choose n}a_{n}=\sum _{n=0}^{\infty } (-1)^{n}{n+p \elegir n}{\frac {(\Delta ^{n}a)_{0}}{2^{n+p+1}}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
donde p = 0, 1, 2,…
La transformada de Euler también se aplica frecuentemente a la integral hipergeométrica de Euler . Aquí la transformada de Euler toma la forma:![{\displaystyle \,_{2}F_{1}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \,_{2}F_{1}(a,b;c;z)=(1-z)^{-b}\,_{2}F_{1}\left(ca,b; c;{\frac {z}{z-1}}\right).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
[Ver [1] para generalizaciones a otras series hipergeométricas.]
La transformada binomial, y su variación como transformada de Euler, se destaca por su conexión con la representación de fracción continua de un número. Tengamos la representación de fracción continua.![{\displaystyle 0<x<1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x=[0;a_{1},a_{2},a_{3},\cdots ]}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
entonces
![{\displaystyle {\frac {x}{1-x}}=[0;a_{1}-1,a_{2},a_{3},\cdots ]}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
y
![{\displaystyle {\frac {x}{1+x}}=[0;a_{1}+1,a_{2},a_{3},\cdots ].}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Función generadora exponencial
Para la función generadora exponencial , sea
![{\displaystyle {\overline {f}}(x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
y
![{\displaystyle {\overline {g}}(x)=\sum _{n=0}^{\infty }s_{n}{\frac {x^{n}}{n!}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
entonces
![{\displaystyle {\overline {g}}(x)=(T{\overline {f}})(x)=e^{x}{\overline {f}}(-x).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La transformada de Borel convertirá la función generadora ordinaria en la función generadora exponencial.
convolución binomial
Sean y , sucesiones de números complejos. Su convolución binomial está definida por ![{\displaystyle \{a_{n}\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \{b_{n}\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle n=0,1,2,\ldots,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (a\circ b)_{n}=\sum _{k=0}^{n}{n \choose k}a_{k}b_{nk},\ \ n=0,1,2 ,\lpuntos }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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 definida por y para sirve como identidad bajo la convolución binomial. Además, es fácil ver que las secuencias poseen una inversa. Así, el conjunto de secuencias forma un grupo abeliano bajo la convolución binomial. ![{\displaystyle \{e_{n}\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle e_{0}=1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle e_{n}=0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle n=1,2,\ldots,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \{a_{n}\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle a_{0}\neq 0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \{a_{n}\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle a_{0}\neq 0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La convolución binomial surge naturalmente del producto de las funciones generadoras exponenciales. De hecho,
![{\displaystyle \left(\sum _{n=0}^{\infty }a_{n}{x^{n} \over n!}\right)\left(\sum _{n=0}^{ \infty }b_{n}{x^{n} \over n!}\right)=\sum _{n=0}^{\infty }(a\circ b)_{n}{x^{n } \sobre n!}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La transformada binomial se puede escribir en términos de convolución binomial. Que y para todos . Entonces ![{\displaystyle \lambda _ {n}=(-1)^{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 1_{n}=1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle n}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (Ta)_{n}=(\lambda a\circ 1)_{n}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La formula
![{\displaystyle t_{n}=\sum _{k=0}^{n}(-1)^{nk}{n \choose k}a_{k}\iff a_{n}=\sum _{k =0}^{n}{n \elegir k}t_{k}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
puede ser interpretado como una fórmula de tipo inversión de Möbius
![{\displaystyle t_{n}=(a\circ \lambda )_{n}\iff a_{n}=(t\circ 1)_{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
puesto que es el inverso de
bajo la convolución binomial. ![{\displaystyle \lambda _ {n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ Displaystyle 1_ {n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
También hay otra convolución binomial en la literatura matemática. La convolución binomial de funciones aritméticas
y se define como![{\displaystyle f}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle g}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\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),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
donde es la factorización canónica de un número entero positivo y es el coeficiente binomial. Esta convolución aparece en el libro de PJ McCarthy (1986) y fue estudiada más a fondo por L. Toth y P. Haukkanen (2009).![{\displaystyle n=\prod _ {p}p^{\nu _ {p}(n)}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle n}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\binom {\nu _ {p}(n)}{\nu _ {p}(d)}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Representación integral
Cuando la secuencia puede interpolarse mediante una función analítica compleja , entonces la transformada binomial de la secuencia se puede representar mediante una integral de Nörlund-Rice en la función de interpolación.
Generalizaciones
Prodinger ofrece una transformación similar a la modular : dejar
![{\displaystyle u_{n}=\sum _ {k=0}^{n}{n \choose k}a^{k}(-c)^{nk}b_{k}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
da
![{\displaystyle U(x)={\frac {1}{cx+1}}B\left({\frac {ax}{cx+1}}\right)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
donde U y B son las funciones generadoras ordinarias asociadas con la serie y , respectivamente.![{\displaystyle \{u_ {n}\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \{b_{n}\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La transformada k -binomial ascendente a veces se define como
![{\displaystyle \sum _{j=0}^{n}{n \choose j}j^{k}a_{j}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La transformada k -binomial descendente es
.
Ambos son homomorfismos del núcleo de la transformada de Hankel de una serie .
En el caso en que la transformada binomial se define como
![{\displaystyle \sum _{i=0}^{n}(-1)^{ni}{\binom {n}{i}}a_{i}=b_{n}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Sea esto igual a la función![{\displaystyle {\mathfrak {J}}(a)_{n}=b_{n}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Si se crea una nueva tabla de diferencias directas y los primeros elementos de cada fila de esta tabla se toman para formar una nueva secuencia , entonces la segunda transformación binomial de la secuencia original es,![{\displaystyle \{b_{n}\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathfrak {J}}^{2}(a)_{n}=\sum _{i=0}^{n}(-2)^{ni}{\binom {n}{i }}ai}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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)^{ni}{\binom {n}{i}}a_{i}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Su inverso es,
![{\displaystyle {\mathfrak {J}}^{-k}(b)_{n}=a_{n}=\sum _{i=0}^{n}k^{ni}{\binom {n }{i}}b_{i}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Esto se puede generalizar como,
![{\displaystyle {\mathfrak {J}}^{k}(a)_{n}=b_{n}=(\mathbf {E} -k)^{n}a_{0}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
¿Dónde está el operador de turno ?![{\displaystyle \mathbf {E} }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Su inverso es
![{\displaystyle {\mathfrak {J}}^{-k}(b)_{n}=a_{n}=(\mathbf {E} +k)^{n}b_{0}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Ver también
Referencias
- ^ Molinero, Allen R.; París, RB (2010). "Transformaciones de tipo Euler para la función hipergeométrica generalizada". Z. Angew. Matemáticas. Física . 62 (1): 31–45. doi :10.1007/s00033-010-0085-0. S2CID 30484300.
- 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, 1992, Alguna información sobre la transformada binomial Archivado el 12 de marzo de 2007 en Wayback Machine.
- Spivey, Michael Z.; Steil, Laura L. (2006). "Las transformadas k-binomiales y la transformada de Hankel". Diario de secuencias enteras . 9 : 06.1.1. Código Bib : 2006JIntS...9...11S.
- Borísov, B.; Shkodrov, V. (2007). "Serie divergente en la transformada binomial generalizada". Adv. Semental. Cont. Matemáticas . 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. Combinatoria y teoría de números 1 (2009), 31-48.
enlaces externos
- Transformada binomial
- Transformaciones de secuencias enteras