Inversion (Diskrete Mathematik)

In d​er diskreten Mathematik bezeichnet e​ine Inversion e​ine Koordinatentransformation zwischen verschiedenen Zahlenfolgen. Eine wichtige Klasse dieser Koordinatentransformationen i​st die Binomialinversion.

Inversionsformel

Seien ${\displaystyle p_{0},p_{1},\ldots ,}$ und ${\displaystyle q_{0},q_{1},\ldots ,}$ zwei Folgen von Polynomen mit ${\displaystyle \operatorname {Grad} (p_{n})=\operatorname {Grad} (q_{n})=n}$. Das heißt, die Menge ${\displaystyle p_{0},\ldots ,p_{n}}$ und die Menge ${\displaystyle q_{0},\ldots ,q_{n}}$ bilden jeweils eine Basis des Vektorraums aller Polynome vom Grad kleinergleich ${\displaystyle n}$. Mit Hilfe der Inversionsformel kann jedes ${\displaystyle q_{n}}$ eindeutig durch ${\displaystyle p_{0},\ldots ,p_{n}}$ beziehungsweise jedes ${\displaystyle p_{n}}$ eindeutig durch ${\displaystyle q_{0},\ldots ,q_{n}}$ausgedrückt werden. Das heißt, es gibt eindeutig bestimmte Koeffizienten ${\displaystyle a_{nk}}$ und ${\displaystyle b_{nk}}$ mit

${\displaystyle q_{n}(x)=\sum _{k=0}^{n}a_{nk}p_{k}(x)}$

beziehungsweise mit

${\displaystyle p_{n}(x)=\sum _{k=0}^{n}b_{nk}q_{k}(x)\,.}$

Die Koeffizienten ${\displaystyle a_{nk}}$ und ${\displaystyle b_{nk}}$ heißen Zusammenhangskoeffizienten. Setzt man ${\displaystyle a_{nk}=b_{nk}=0}$ für ${\displaystyle n<k}$, dann erhält man zwei (unendlich große) Dreiecksmatrizen, die zueinander invers sind. Sei also ${\displaystyle A=(a_{ij})}$ und ${\displaystyle B=(b_{ij})}$ dann gilt ${\displaystyle A=B^{-1}}$. Aus diesem Grund gilt für alle Zahlenfolgen ${\displaystyle u_{1},u_{2},\ldots }$ und ${\displaystyle v_{1},v_{2}\ldots }$:

${\displaystyle v_{n}=\sum _{k=0}^{n}a_{nk}u_{k}\Longleftrightarrow u_{n}=\sum _{k=0}^{n}b_{nk}v_{k}\,.}$

Beispiel

Über dem Vektorraum der Polynome bis zum Grad n stellen sowohl die Monome ${\displaystyle 1,x,x^{2},...,x^{n}}$ als auch die Polynome ${\displaystyle 1,x-1,(x-1)^{2},...,(x-1)^{n}}$ eine Basis dar. Jedes Polynom aus der ersten Folge kann also als Linearkombination der Polynome der zweiten Folge dargestellt werden, und umgekehrt. Die Inversionsformeln dazu lauten

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

und

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

Dies ist ein Beispiel der Binomial-Inversion. Allgemein gilt für alle Familien ${\displaystyle u_{1},\ldots u_{n}}$ und ${\displaystyle v_{1},\ldots ,v_{n}}$, dass

${\displaystyle u_{n}=\sum _{k=0}^{n}{\binom {n}{k}}(-1)^{n-k}v_{k}\Longleftrightarrow v_{n}=\sum _{k=0}^{n}{\binom {n}{k}}u_{k}}$.

Quellen

• Martin Aigner: Diskrete Mathematik, 6., korrigierte Auflage, Vieweg, Wiesbaden 2006, ISBN 978-3-8348-0084-8, Kap. 2.3.