Inversion (Diskrete Mathematik)

In der diskreten Mathematik bezeichnet die Inversion eine Koordinatentransformation zwischen verschiedenen Zahlenfolgen. Eine wichtige Klasse dieser Koordinatentransformationen ist die Binomialinversion.

Inversionsformel

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$. Das heißt, die Menge $p_{0},\ldots ,p_{n}$ und die Menge $q_{0},\ldots ,q_{n}$ bilden jeweils eine Basis des Vektorraums aller Polynome vom Grad kleinergleich $n$. Mit Hilfe der Inversionsformel kann jedes $q_{n}$ eindeutig durch $p_{0},\ldots ,p_{n}$ beziehungsweise jedes $p_{n}$ eindeutig durch $q_{0},\ldots ,q_{n}$ausgedrückt werden. Das heißt, es gibt eindeutig bestimmte Koeffizienten $a_{nk}$ und $b_{nk}$ mit

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

beziehungsweise mit

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

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

$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 $1,x,x^{2},...,x^{n}$ als auch die Polynome $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

$(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}\,.$

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

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