■ポアンカレ多項式(その10)

【1】逆転数の母関数

 n個の要素をもつ順列のうち,k個の逆転数をもつものがいくつIn(k)あるか?

 その母関数は

  Gn(z)=In(0)+In(1)z+In(2)z^2+・・・

  Gn(z)=(1+z+・・・+z^n-1)Gn-1(z)

  (1+z+・・・+z^n-1)・・・(1+z)=(1-z^n)・・・(1-z^2)(1-z)/(1-z)^n

 したがって,

k<n→ In(k)=In(k-1)+In-1(k)

In(2)=(n,2)-1

In(3)=(n+1,3)-(n,1)

In(4)=(n+2,4)-(n+1,2)

In(5)=(n+3,5)-(n+2,3)+1

一般にIn(k)~1.6√k

===================================