ｎを２以上の整数とし、１からｎまでの相異なるｎ個の整数を
横一列にに並べて得られる各順列ρに対して
左からi番目の数字をρ（i）と記す。
このとき条件１≦i≦j≦nかつρ(i)>ρ(j)を満たす整数の対（i,j）の
個数をl（ρ)とおく。さらに１からｎまでの順列ρ全体のなす集合をＳとする。
順列ρがＳ全体を動くときl（ρ）の総和を求めよという問題で、

答えはn(n-1)n!/4で、その別解が、
求める値をa[n]とすると、
a[k+1]=(k+1)a[k]+(1+2+3…k)k!となるから　とあるんですが、
なぜこの式が成り立つのか分かりません。

k個の順列で題意を満たすものそれぞれについて、
１番左端にk+1を挿入すると、題意を満たす内左端にこれを挿入したものの数は、(k+1)a[k]
だと分かります。（k+1が最も大きいから。）
しかし次に、左端から２番目にk+1をそれぞれ挿入すると、
その右側にあるk個の数全てに勝っているため、題意を満たす内ここに挿入したものはka[k]になると思います。
結果、a[k+1]は、
(k+1+k+k-1+k-2…1)a[k]とかになると思います。
何が違うんでしょうか。