Transformación binomial

En combinatoria , la transformada binomial es una transformación de secuencia (es decir, una transformada de una secuencia ) que calcula sus diferencias 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 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}.}$

Formalmente, se 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,

${\estilo de visualización TT=1}$

o, utilizando la notación de índice,

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

¿Dónde está el delta de Kronecker ? La serie original se puede recuperar mediante${\displaystyle \delta _{nm}}$

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

La transformada binomial de una secuencia es simplemente la n- ésima diferencia hacia adelante de la secuencia, donde las diferencias impares tienen un signo negativo, es decir:

${\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 hacia adelante .

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

cuya inversa es

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

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

Ambas versiones de la transformada binomial aparecen en las 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 la ecuación diferencial 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 de inicio 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 de inicio 1485 es { s _n } = 1485, 1161, 900, 692, 528, 400, ... { s _n } es la transformada binomial involutiva de { b _n }.

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

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 . Suele presentarse de dos formas diferentes. En una forma, se utiliza para acelerar la convergencia de una serie alternada . Es decir, se 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}}}}$

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, mucho más rápido, lo que permite una suma numérica rápida.

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 \choose n}{\frac {(\Delta ^{n}a)_{0}}{2^{n+p+1}}},}$

donde p = 0, 1, 2,…

La transformada de Euler también se aplica con frecuencia a la integral hipergeométrica de Euler . En este caso, la transformada de Euler adopta la forma:${\displaystyle \,_{2}F_{1}}$

${\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 transformación binomial, y su variación como la transformación de Euler, se destaca por su conexión con la representación de fracción continua de un número. Sea la representación de fracción continua${\displaystyle 0<x<1}$

${\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 generadora ordinaria en la función generadora exponencial.

Sean y , secuencias de números complejos. Su convolución binomial está definida por ${\displaystyle \{a_{n}\}}$${\displaystyle \{b_{n}\}}$${\displaystyle n=0,1,2,\ldots ,}$

${\displaystyle (a\circ b)_{n}=\sum _{k=0}^{n}{n \choose 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 definida por y para sirve como identidad bajo la convolución binomial. Además, es fácil ver que las secuencias con poseen una inversa. Por lo tanto, el conjunto de secuencias con forma un grupo abeliano bajo la convolución binomial. ${\displaystyle \{e_{n}\}}$${\displaystyle e_{0}=1}$${\displaystyle e_{n}=0}$${\displaystyle n=1,2,\ldots ,}$${\displaystyle \{a_{n}\}}$${\displaystyle a_{0}\neq 0}$${\displaystyle \{a_{n}\}}$${\displaystyle a_{0}\neq 0}$

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} \over n!}.}$

La transformada binomial se puede escribir en términos de convolución binomial. Sea y para todo . Entonces ${\displaystyle \lambda _{n}=(-1)^{n}}$${\displaystyle 1_{n}=1}$${\displaystyle n}$

${\displaystyle (Ta)_{n}=(\lambda a\circ 1)_{n}.}$

La fórmula

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

Puede interpretarse 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}}$

ya que es la inversa de bajo la convolución binomial. ${\displaystyle \lambda _{n}}$${\displaystyle 1_{n}}$

También existe otra convolución binomial en la literatura matemática. La convolución binomial de funciones aritméticas se define como${\displaystyle f}$${\displaystyle g}$

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

donde es la factorización canónica de un 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)}}$${\displaystyle n}$${\displaystyle {\binom {\nu _{p}(n)}{\nu _{p}(d)}}}$

Cuando la secuencia se puede interpolar 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.

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

${\displaystyle u_{n}=\sum _{k=0}^{n}{n \choose k}a^{k}(-c)^{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 las series y , respectivamente.${\displaystyle \{u_{n}\}}$${\displaystyle \{b_{n}\}}$

La transformada k -binomial ascendente a veces se define como

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

La transformada k -binomial descendente es

${\displaystyle \sum _{j=0}^{n}{n \choose 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 transformada binomial se define como

${\displaystyle \sum _{i=0}^{n}(-1)^{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 , entonces la segunda transformada binomial de la secuencia original es,${\displaystyle \{b_{n}\}}$

${\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 está el operador de desplazamiento ?${\displaystyle \mathbf {E} }$

Su inversa es

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

• Serie de Newton
• Matriz de Hankel
• Transformada de Möbius
• Transformada de Stirling
• Suma 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, 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". Journal of Integer Sequences . 9 : 06.1.1. Código Bibliográfico :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 ciencia 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).

• Transformada binomial
• Transformaciones de secuencias enteras