【１】逆転数の母関数

　ｎ個の要素をもつ順列のうち，ｋ個の逆転数をもつものがいくつＩn（ｋ）あるか？

　その母関数は

　　Ｇn（ｚ）＝Ｉn（０）＋Ｉn（１）ｚ＋Ｉn（２）ｚ^2＋・・・

　　Ｇn（ｚ）＝（１＋ｚ＋・・・＋ｚ^n-1）Ｇn-1（ｚ）

　　（１＋ｚ＋・・・＋ｚ^n-1）・・・（１＋ｚ）＝（１−ｚ^n）・・・（１−ｚ^2）（１−ｚ）／（１−ｚ）^n

　したがって，

ｋ＜ｎ→　Ｉn（ｋ）＝Ｉn（ｋ−１）＋Ｉn-1（ｋ）

Ｉn（２）＝（ｎ，２）−１

Ｉn（３）＝（ｎ＋１，３）−（ｎ，１）

Ｉn（４）＝（ｎ＋２，４）−（ｎ＋１，２）

Ｉn（５）＝（ｎ＋３，５）−（ｎ＋２，３）＋１

一般にＩn（ｋ）〜１．６√ｋ

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝