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 <math>p_0, p_1, \ldots,</math> und <math>q_0, q_1, \ldots,</math> zwei Folgen von Polynomen mit <math>\operatorname{Grad}(p_n) = \operatorname{Grad}(q_n) = n</math>. Das heißt, die Menge <math>p_0, \ldots, p_n</math> und die Menge <math>q_0, \ldots, q_n</math> bilden jeweils eine Basis des Vektorraums aller Polynome vom Grad kleinergleich <math>n</math>. Mit Hilfe der Inversionsformel kann jedes <math>q_n</math> eindeutig durch <math>p_0, \ldots, p_n</math> beziehungsweise jedes <math>p_n</math> eindeutig durch <math>q_0, \ldots, q_n</math>ausgedrückt werden. Das heißt, es gibt eindeutig bestimmte Koeffizienten <math>a_{nk}</math> und <math>b_{nk}</math> mit

<math>q_n(x) = \sum_{k=0}^n a_{nk} p_k(x)</math>

beziehungsweise mit

<math>p_n(x) = \sum_{k=0}^n b_{nk} q_k(x)\,.</math>

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

<math> v_n = \sum_{k=0}^n a_{nk} u_k \Longleftrightarrow

      u_n = \sum_{k=0}^n b_{nk} v_k \,.</math>

Beispiel

Über dem Vektorraum der Polynome bis zum Grad n stellen sowohl die Monome <math> 1,x,x^2,...,x^n </math> als auch die Polynome <math> 1,x-1,(x-1)^2,...,(x-1)^n </math> 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

<math> (x-1)^n = \sum_{k=0}^n {n \choose k} (-1)^{n-k} x^k </math>

und

<math> x^n = \sum_{k=0}^n {n \choose k} (x-1)^k\,.</math>

Dies ist ein Beispiel der Binomial-Inversion. Allgemein gilt für alle Familien <math>u_1, \ldots u_n</math> und <math>v_1, \ldots , v_n</math>, dass

<math> 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 </math>.

Quellen

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