Inversion (Diskrete Mathematik)

Grundidee der Inversion

Eine Inversion ist in der diskreten Mathematik eine Koordinatentransformation zwischen verschiedenen Zahlenfolgen. Sie beschreibt, wie sich eine Folge mithilfe bestimmter Koeffizienten in eine andere Folge umrechnen und diese Umrechnung eindeutig rückgängig machen lässt. Eine wichtige Form ist die Binomialinversion.

Inversionsformel und Zusammenhangskoeffizienten

Seien p_0,p_1,\ldots und q_0,q_1,\ldots zwei Folgen von Polynomen mit \operatorname{Grad}(p_n)=\operatorname{Grad}(q_n)=n. Für jedes n bilden sowohl p_0,\ldots,p_n als auch q_0,\ldots,q_n eine Basis des Vektorraums aller Polynome vom Grad höchstens n. Eine Basis ist eine Menge von Polynomen, aus denen sich jedes Polynom dieses Vektorraums eindeutig als Linearkombination zusammensetzen lässt.

Daher gibt es eindeutig bestimmte Koeffizienten a_{nk} und b_{nk}, sodass q_n(x)=\sum_{k=0}^{n}a_{nk}p_k(x) und p_n(x)=\sum_{k=0}^{n}b_{nk}q_k(x). Diese Zahlen heißen Zusammenhangskoeffizienten.

Inverse Dreiecksmatrizen und Zahlenfolgen

Setzt man a_{nk}=b_{nk}=0 für n<k, entstehen zwei unendlich große Dreiecksmatrizen A=(a_{ij}) und B=(b_{ij}). Sie sind invers zueinander, also A=B^{-1}. Das bedeutet, dass die eine Transformation die andere rückgängig macht.

Für alle Zahlenfolgen u_1,u_2,\ldots und v_1,v_2,\ldots gilt deshalb: v_n=\sum_{k=0}^{n}a_{nk}u_k\quad\Longleftrightarrow\quad u_n=\sum_{k=0}^{n}b_{nk}v_k. Kennt man eine der beiden Folgen und die passenden Zusammenhangskoeffizienten, lässt sich somit die andere Folge bestimmen.

Beispiel mit verschobenen Monomen

Im Vektorraum der Polynome bis zum Grad n sind sowohl die Monome 1,x,x^2,\ldots,x^n als auch die verschobenen Potenzen 1,x-1,(x-1)^2,\ldots,(x-1)^n eine Basis. Deshalb kann jedes Polynom der einen Folge als Linearkombination der Polynome der anderen Folge dargestellt werden.

Nach dem binomischen Lehrsatz gelten die beiden zueinander inversen Darstellungen (x-1)^n=\sum_{k=0}^{n}{n\choose k}(-1)^{n-k}x^k und x^n=\sum_{k=0}^{n}{n\choose k}(x-1)^k. Dabei ist {n\choose k} der Binomialkoeffizient. Dieses Paar von Umrechnungsformeln ist ein Beispiel für die Binomialinversion.

Allgemeine Binomialinversion

Allgemein gilt für Familien u_1,\ldots,u_n und v_1,\ldots,v_n: u_n=\sum_{k=0}^{n}{\binom{n}{k}}(-1)^{n-k}v_k\quad\Longleftrightarrow\quad v_n=\sum_{k=0}^{n}{\binom{n}{k}}u_k. Die erste Formel verwendet zusätzlich das wechselnde Vorzeichen (-1)^{n-k}. Beide Formeln bilden ein Inversionspaar: Jede von ihnen ermöglicht es, die durch die jeweils andere Formel ausgeführte Transformation umzukehren.