Binomialtransformation

In der Kombinatorik ist die Binomialtransformation eine Sequenztransformation (d. h. eine Transformation einer Folge ), die deren Vorwärtsdifferenzen berechnet . Sie ist eng mit der Euler-Transformation verwandt , welche das Ergebnis der Anwendung der Binomialtransformation auf die zu ihrer gewöhnlichen erzeugenden Funktion gehörige Folge ist .

Die Binomialtransformation T einer Folge { a_n } ist die Folge { s _{_n} } , die definiert ist durch

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

Formal kann man schreiben

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

für die Transformation, wobei T ein unendlichdimensionaler Operator mit Matrixelementen T _nk ist . Die Transformation ist eine Involution , d.h.

$${\displaystyle TT=1}$$

oder, unter Verwendung der Indexnotation ,

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

Wo befindet sich das Kronecker-Delta ? Die ursprüngliche Reihe kann wiederhergestellt werden durch ${\displaystyle \delta _{nm}}$

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

Die Binomialtransformation einer Folge ist einfach die n -te Vorwärtsdifferenz der Folge, wobei ungerade Differenzen ein negatives Vorzeichen tragen, nämlich:

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

wobei Δ der Vorwärtsdifferenzoperator ist .

Manche Autoren definieren die Binomialtransformation mit einem zusätzlichen Vorzeichen, sodass sie nicht selbstinvers ist:

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

deren Umkehrung ist

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

In diesem Fall wird die erstgenannte Transformation als inverse Binomialtransformation bezeichnet , die letztgenannte hingegen einfach als Binomialtransformation . Dies entspricht dem üblichen Sprachgebrauch, beispielsweise in der Online-Enzyklopädie der Zahlenfolgen .

Beide Varianten der Binomialtransformation finden sich in Differenztabellen. Betrachten Sie die folgende Differenztabelle:

Jede Zeile ist die Differenz der vorherigen Zeile. (Die n -te Zahl in der m -ten Zeile ist a _{m , n} = 3 ^{n −2} (2 ^{m +1} n ² + 2 ^m (1+6 m ) n + 2 ^{m -1} 9 m ² ), und es gilt die Differenzengleichung a _{m +1, n} = a _{m , n +1} - a _{m , n} .)

Die oberste Zeile, von links nach rechts gelesen, lautet { a _n } = 0, 1, 10, 63, 324, 1485, ... Die Diagonale mit demselben Startpunkt 0 lautet { t _n } = 0, 1, 8, 36, 128, 400, ... { t _n } ist die nichtinvolutive Binomialtransformation von { a _n }.

Die oberste Zeile, von rechts nach links gelesen, lautet { b _n } = 1485, 324, 63, 10, 1, 0, ... Die Kreuzdiagonale mit demselben Startpunkt 1485 lautet { s _n } = 1485, 1161, 900, 692, 528, 400, ... { s _n } ist die involutive Binomialtransformation von { b _n }.

Die Transformation verbindet die zur Reihe gehörigen erzeugenden Funktionen . Für die gewöhnliche erzeugende Funktion sei

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

Und

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

Dann

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

Die Beziehung zwischen den gewöhnlichen erzeugenden Funktionen wird manchmal als Euler-Transformation bezeichnet . Sie tritt üblicherweise in zwei verschiedenen Formen auf. In einer Form wird sie verwendet, um die Konvergenz einer alternierenden Reihe zu beschleunigen . Das heißt, man hat die Identität

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

Dies erhält man, indem man x = 1/2 in die letzte Formel oben einsetzt. Die Terme auf der rechten Seite werden typischerweise viel kleiner und viel schneller, was eine rasche numerische Summation ermöglicht.

Die Euler-Transformation kann verallgemeinert werden (Borisov B. und 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}}},}$$

wobei p = 0, 1, 2,... .

Die Euler-Transformation wird auch häufig auf das Euler-hypergeometrische Integral angewendet . Hier hat die Euler-Transformation die folgende Form: ${\displaystyle \,_{2}F_{1}}$

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

[Siehe ^{[ 1 ]} für Verallgemeinerungen auf andere hypergeometrische Reihen.]

Die Binomialtransformation und ihre Variante, die Euler-Transformation, zeichnen sich durch ihren Zusammenhang mit der Kettenbruchdarstellung einer Zahl aus. Sei die Kettenbruchdarstellung gegeben. ${\displaystyle 0<x<1}$

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

Dann

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

Und

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

Für die exponentielle erzeugende Funktion sei

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

Und

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

Dann

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

Die Borel-Transformation wandelt die gewöhnliche erzeugende Funktion in die exponentielle erzeugende Funktion um.

Seien und Folgen komplexer Zahlen . Ihre Binomialfaltung ist definiert durch . Diese Faltung findet sich in dem Buch „ Concrete Mathematics : A Foundation for Computer Science“ von R. L. Graham, D. E. Knuth und O. Patashnik, Addison-Wesley (1989). Man sieht leicht, dass die Binomialfaltung assoziativ und kommutativ ist, und die durch und für definierte Folge dient als neutrales Element unter der Binomialfaltung. Weiterhin ist leicht zu sehen, dass die Folgen mit ein Inverses besitzen. Somit bildet die Menge der Folgen mit eine abelsche Gruppe bezüglich der Binomialfaltung. ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$${\displaystyle (b_{n})_{n\in \mathbb {N} }}$$${\displaystyle (a\circ b)_{n}=\sum _{k=0}^{n}{\binom {n}{k}}a_{k}b_{nk},\ \ n=0,1,2,\ldots }$$${\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}$

Die Binomialfaltung ergibt sich auf natürliche Weise aus dem Produkt der exponentiellen erzeugenden Funktionen. Tatsächlich $${\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!}}.}$$

Die Binomialtransformation lässt sich mithilfe der Binomialfaltung ausdrücken. Seien und für alle . Dann gilt . Die Formel kann als Möbius-Inversionsformel interpretiert werden, da die Inverse von unter der Binomialfaltung ist. ${\displaystyle \lambda _{n}=(-1)^{n}}$${\displaystyle 1_{n}=1}$${\displaystyle n}$$${\displaystyle (Ta)_{n}=(\lambda a\circ 1)_{n}.}$$$${\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}}$$$${\displaystyle t_{n}=(a\circ \lambda )_{n}\iff a_{n}=(t\circ 1)_{n}}$$${\displaystyle \lambda _{n}}$${\displaystyle 1_{n}}$

In der mathematischen Literatur findet sich auch eine weitere Binomialfaltung. Die Binomialfaltung arithmetischer Funktionen f und g ist definiert als f(x) = f(x) + g(x ), wobei x die kanonische Faktorisierung einer positiven ganzen Zahl und g der Binomialkoeffizient ist . Diese Faltung wurde erstmals in dem Buch von P. J. McCarthy (1986) beschrieben und von L. Toth und P. Haukkanen (2009) weiter untersucht. ${\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),}$$${\displaystyle n=\prod _{p}p^{\nu _{p}(n)}}$${\displaystyle n}$${\displaystyle {\binom {\nu _{p}(n)}{\nu _{p}(d)}}}$

Wenn die Folge durch eine komplexe analytische Funktion interpoliert werden kann , dann kann die Binomialtransformation der Folge mittels eines Nörlund-Rice-Integrals über die interpolierende Funktion dargestellt werden.

Prodinger liefert eine verwandte, modulare Transformation: das Lassen

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

gibt

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

wobei U und B die gewöhnlichen erzeugenden Funktionen sind, die mit den Reihen und assoziiert sind. ${\displaystyle \{u_{n}\}}$${\displaystyle \{b_{n}\}}$

Die steigende k -Binomialtransformation wird manchmal definiert als

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

Die fallende k -Binomialtransformation ist

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

Beide sind Homomorphismen des Kerns der Hankel-Transformation einer Reihe .

In dem Fall, dass die Binomialtransformation wie folgt definiert ist

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

Sei dies gleich der Funktion${\displaystyle {\mathfrak {J}}(a)_{n}=b_{n}.}$

Wenn eine neue Vorwärtsdifferenztabelle erstellt wird und die ersten Elemente jeder Zeile dieser Tabelle zu einer neuen Folge zusammengefasst werden , dann ist die zweite Binomialtransformation der ursprünglichen Folge: ${\displaystyle \{b_{n}\}}$

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

Wenn derselbe Vorgang k -mal wiederholt wird, dann folgt daraus,

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

Das Umgekehrte ist:

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

Dies lässt sich verallgemeinern als:

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

Wo ist der Schichtführer ? ${\displaystyle \mathbf {E} }$

Seine Umkehrung ist

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

• Newton-Serie
• Hankel-Matrix
• Möbius-Transformation
• Stirling transform
• Euler-Summation
• Binomial QMF
• Riemann-Liouville-Integral
• Liste der Themen zu Fakultäten und Binomialverteilungen

• John H. Conway und Richard K. Guy, 1996, Das Buch Numeri
• Donald E. Knuth, Die Kunst der Computerprogrammierung, Band 3 , (1973) Addison-Wesley, Reading, MA.
• Helmut Prodinger, Einige Informationen über die Binomialtransformation , The Fibonacci Quarterly 32 (1994), 412–415.
• Spivey, Michael Z.; Steil, Laura L. (2006). „Die k-Binomialtransformationen und die Hankel-Transformation“ . Journal of Integer Sequences . 9 : 06.1.1. Bibcode : 2006JIntS...9...11S .
• Borisov, B.; Shkodrov, V. (2007). „Divergente Reihen in der verallgemeinerten Binomialtransformation“ . Adv. Stud. Cont. Math . 14 (1): 77–82 .
• Khristo N. Boyadzhiev, Anmerkungen zur Binomialtransformation , Theorie und Tabelle, mit Anhang zur Stirling-Transformation (2018), World Scientific.
• RL Graham, DE Knuth und O. Patashnik: Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley (1989).
• PJ McCarthy, Einführung in arithmetische Funktionen, Springer-Verlag, 1986.
• P. Haukkanen, Über eine binomiale Faltung arithmetischer Funktionen, Nieuw Arch. Wisk. (IV) 14 (1996), Nr. 2, 209–216.
• L. Toth und P. Haukkanen, Über die Binomialfaltung arithmetischer Funktionen, J. Combinatorics and Number Theory 1(2009), 31–48.
• P. Haukkanen, Einige Binomialinversionen mithilfe gewöhnlicher erzeugender Funktionen. Publ. Math. Debr. 47, Nr. 1-2, 181-191 (1995).

• Binomialtransformation auf Wolfram MathWorld
• Binomialtransformation im OEIS- Wiki