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,\dots ,$ und $q_0,q_1,\dots ,$ zwei Folgen von Polynomen mit $\mathrm{Grad}(p_n)=\mathrm{Grad}(q_n)=n$. Das heißt, die Menge $p_0,\dots ,p_n$ und die Menge $q_0,\dots ,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,\dots ,p_n$ beziehungsweise jedes $p_n$ eindeutig durch $q_0,\dots ,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,\dots$ und $v_1,v_2\dots$:

$v_n=\sum _{k=0}^n{a}_{nk}{u}_k⟺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(\genfrac{}{}{0ex}{}{n}{k})(-1{)}^{n-k}{x}^k$

und

$x^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})(x-1{)}^k.$

Dies ist ein Beispiel der Binomial-Inversion. Allgemein gilt für alle Familien $u_1,\dots u_n$ und $v_1,\dots ,v_n$, dass

$u_n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})(-1{)}^{n-k}{v}_k⟺v_n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})u_k$.

Quellen

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