Inversion (Diskrete Mathematik)

aus Freepedia, der freien Wissensdatenbank

In der diskreten Mathematik bezeichnet eine Inversion die wechselseitige Darstellung von Zahlenfolgen durch Summen. So gilt z.B.

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

Daraus kann man nun die sogenannte Binomialinversion ableiten: Über dem Vektorraum der Polynome bis zum Grad n stellen sowohl die Polynome <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 Koeffizienten nennt man auch Zusammenhangskoeffizienten.

Fasst man die Koeffizienten beider Zusammenhänge in Matrizen A und B zusammen, so sind A und B invers zueinander, da sie Basiswechselmatrizen zwischen den beiden Basisfolgen darstellen.

Daraus folgt nun für beliebige Zahlenfolgen:

<math> a_n = \sum_{k=0}^n {n \choose k} (-1)^{n-k} b_k \Longleftrightarrow

      b_n = \sum_{k=0}^n {n \choose k} a_k </math>

Dieses Verfahren lässt sich auch auf andere Basisfolgen, z.B. <math>1,x,x(x-1),x(x-2)(x-3),...</math> anwenden.