■増加列の長さの平均(その13)

 包除原理は

  Mt=Nt−(n,1)Nt-1+(n,2)Nt-2+・・・

で表されるが,ここでは,ヤング図に関係する漸化式を紹介したい.

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

  tn=tn-1+(n−1)tn-2

  tn=Σtn(k),tn(k)=n!/(n−2k)!2^kk!

  Σtnz^n/n!=xexp(z+z^2/2) 

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