【１】逆転数の母関数

　ｎ個の要素をもつ順列のうち，ｋ個の逆転数をもつものがいくつＩ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（ｋ）～１．６√ｋ

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