Inversion (Diskrete Mathematik)

In der diskreten Mathematik bezeichnet eine Inversion eine Koordinatentransformation zwischen verschiedenen Zahlenfolgen.

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 existieren Zahlenfolgen $u_1, u_2, \ldots$ und $v_1, v_2 \ldots$ mit

$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²,...,xⁿ als auch die Polynome 1,x − 1,(x − 1)²,...,(x − 1)ⁿ eine Basis dar. Jedes Polynom aus der ersten Folge kann also als Linearkombination der Polynome der zweiten Folge dargestellt werden, und umgekehrt. Die Inversionsformelen 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 existieren also Familien $u_1, \ldots u_n$ und $v_1, \ldots , v_n$, so 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$

gilt.

Quellen

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