Sorbaállítások k inverzióval
 

Jelölések:

Definíció: Legyen s az {1,2,...,n} halmaz egy sorbaállítása. Az s sorbaállításban egy i,j (i < j) pár inverizóban áll, ha j megelőzi i-t.

Jelölés: Legyen s az {1,2,...,n} halmaz egy sorbaállítása. inv(s) azon i,j párok száma (i < j), amelyek inverzióban állnak az s sorbaállításban.

Megjegyzés: Legyen s az {1,2,...,n} halmaz egy sorbaállítása. 0<=inv(s)<=(n2).

Definíció: Az {1,2,...,n} halmaz k inverziót tartalmazó permutációinak száma i(n,k).


Formula:

Nem vizsgáljuk.


Rekurzió:

Tétel: i(n,k)=i(n-1,k)+i(n-1,k-1)+i(n-1,k-2)+i(n-1,k-3)+...+i(n-1,k*), ahol k< n esetén k*=0, míg k>=n esetén k*=k-n+1.


Polinommá fűzés

Tétel: i(n,0)+i(n,1)x+i(n,2)x2+i(n,3)x3+i(n,4)x4+... =1.(1+x).(1+x+x2).(1+x+x2+x3)... (1+x+x2+...+xn-1)

Lemma: Minden s sorbaállításhoz rendeljünk, hozzá egy {ti:i=1,2,...,n} sorozatot, ahol ti az s-ben i mögé került, i-nél kisebb számok száma. Ez egy bijekció az {1,2,...,n} halmaz összes sorbaállítása és a {0}×{0,1}×{0,1,2}×{0,1,2,3}×...×{0,1,2,3,...,n-1}-beli sorozatok között.