Inversion (Discrete Mathematics)

In discrete mathematics , an inversion describes a coordinate transformation between different sequences of numbers. An important class of these coordinate transformations is the binomial inversion .

Inversion formula

Let and be two sequences of polynomials with . That is, the set and the set each form a basis of the vector space of all polynomials of degree less than or equal . With the help of the inversion formula each can be expressed uniquely by or each uniquely by . That is, there are clearly certain coefficients and with ${\displaystyle p_{0},p_{1},\ldots ,}$ ${\displaystyle q_{0},q_{1},\ldots ,}$ ${\displaystyle \operatorname {Grad} (p_{n})=\operatorname {Grad} (q_{n})=n}$ ${\displaystyle p_{0},\ldots ,p_{n}}$ ${\displaystyle q_{0},\ldots ,q_{n}}$ ${\displaystyle n}$ ${\displaystyle q_{n}}$ ${\displaystyle p_{0},\ldots ,p_{n}}$ ${\displaystyle p_{n}}$ ${\displaystyle q_{0},\ldots ,q_{n}}$ ${\displaystyle a_{nk}}$ ${\displaystyle b_{nk}}$

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

or with

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

The coefficients and are called the connection coefficients . If one sets for , then one obtains two (infinitely large) triangular matrices that are inverse to one another . So be and then applies . For this reason, the following applies to all sequences of numbers and : ${\displaystyle a_{nk}}$ ${\displaystyle b_{nk}}$ ${\displaystyle a_{nk}=b_{nk}=0}$ ${\displaystyle n<k}$ ${\displaystyle A=(a_{ij})}$ ${\displaystyle B=(b_{ij})}$ ${\displaystyle A=B^{-1}}$ ${\displaystyle u_{1},u_{2},\ldots }$ ${\displaystyle v_{1},v_{2}\ldots }$

${\displaystyle v_{n}=\sum _{k=0}^{n}a_{nk}u_{k}\Longleftrightarrow u_{n}=\sum _{k=0}^{n}b_{nk}v_{k}\,.}$

example

Both the monomials and the polynomials represent a basis over the vector space of the polynomials up to degree n . Each polynomial from the first sequence can therefore be represented as a linear combination of the polynomials of the second sequence, and vice versa. The inversion formulas for this are ${\displaystyle 1,x,x^{2},...,x^{n}}$ ${\displaystyle 1,x-1,(x-1)^{2},...,(x-1)^{n}}$

${\displaystyle (x-1)^{n}=\sum _{k=0}^{n}{n \choose k}(-1)^{n-k}x^{k}}$

and

${\displaystyle x^{n}=\sum _{k=0}^{n}{n \choose k}(x-1)^{k}\,.}$

This is an example of binomial inversion. Generally applies to all families and that ${\displaystyle u_{1},\ldots u_{n}}$ ${\displaystyle v_{1},\ldots ,v_{n}}$

${\displaystyle 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}}$.

swell

• Martin Aigner: Diskrete Mathematik , 6th, corrected edition, Vieweg, Wiesbaden 2006, ISBN 978-3-8348-0084-8 , chap. 2.3.