完全順列(モンモール数)の2項間漸化式の組合せ論的解釈

質問

http://ja.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E9%A0%86%E5%88%97
より、
完全順列とは、整数{1,2,3,…,n}を要素とする順列において、i番目(i≦n)がiでない順列のことであり、その総数をモンモール数という。

その総数をa[n]とすると、上記のサイトに、3項間漸化式
a[n]=(n-1)(a[n-1]+a[n-2])
の組合せ論的解釈が書かれています。

また、2項間漸化式
a[n]=n*a[n-1]+(-1)^n
が成り立つのですが、普通は3項間漸化式を元に代数的に変形して示します。
しかし、これを直接に組合せ論的解釈したいのです。

いろいろ考えても、いろいろ調べてもわかりません。
興味ある方はどうか教えてください。

回答No.2

noname#102340

S[n,i]をi文字目がiであるn文字の文字列からなる集合とすると
(例えば、15234∈s[5,1])
a[n] = n! - (｜S[n,1] ∪ S[n,2] … ∪ S[n,n]｜)
後ろの｜｜を包除原理とかふるい分け公式といわれてるやつで数えると、提示されたサイトの
a[n]=Σ[k=2…n](-1)^k*n!/k!　(n≧2)
が導ける。目的の漸化式もこれからすぐに導ける。

dfhsdsさんの言われる組合せ論的解釈ではないかもしれませんが。

参考URL：

http://ja.wikipedia.org/wiki/%E5%8C%85%E9%99%A4%E5%8E%9F%E7%90%86

回答No.1

nag0720

示されたサイトによると、
a[n]=(n-1)(a[n-1]+a[n-2])
の漸化式を解くと、
a[n]=Σ[k=2…n](-1)^k*n!/k!
とあります。
この式の組合せ論的解釈と、nP(n-k)=n*(n-1)P(n-1-k)　とから
a[n]=n*a[n-1]+(-1)^n
が導かれるというのではダメなんでしょうか？