面白い問題おしえて〜な 十五問目

数日前に質問スレで、以下の趣旨の問題が投下され、解決することなく流れていた。

「1〜nの番号がついた玉を無作為に一列に並べたとき、連続するどの2つの番号も、
その順番通りに隣接して配置されない順列のパターン数は？」
（もとの問題は楽曲のシャッフル演奏が題材だった）

n=3の場合、12も23も現れない配置ということで、132、213、321の3通りとなる。
帰納的な考察により、そのようなパターン数をa(n)とおいたとき、
a(1)=a(2)=1として、a(n)=(n-1)*a(n-1)+(n-2)*a(n-2)となることがわかった。

これって解けるのかな。
閉じた式じゃなくても、再帰構造が排除できればいいとして。

>>209
不完全ガンマ関数Γ(m+1,x) := ∫[x,∞] t^m exp(-t) dt を使うと
　a(n) = Γ(n+2,-1) / (n e) になる．
不完全ガンマの展開公式
　exp(x) Γ(n+2,x) = Γ(n+2) Σ[k=0,n+1] x^k/k!
を使えば
　a(n) = ( (n+1)! Σ[k=0,n+1] (-1)/k! ) / n
になる．例えば n = 3 だと 4! (1 - 1/2 + 1/3! - 1/4!) / 3 = 3．

>>210
なんか違わない？計算が合わないんだけど。

>>209
y = x + y' (x^2+x^3) ていう微分方程式を解けば、各係数がその数列のなっているはず。

>>211
ん、あわない？具体的に指摘頼む。
漸化式と一致してることは、小さい n に対しては確認したつもりだけど。

>>212
> 漸化式と一致してることは、小さい n に対しては確認したつもりだけど。
> 漸化式と一致してることは、小さい n に対しては確認したつもりだけど。
> 漸化式と一致してることは、小さい n に対しては確認したつもりだけど。
> 漸化式と一致してることは、小さい n に対しては確認したつもりだけど。
> 漸化式と一致してることは、小さい n に対しては確認したつもりだけど。
> 漸化式と一致してることは、小さい n に対しては確認したつもりだけど。
> 漸化式と一致してることは、小さい n に対しては確認したつもりだけど。

>>209
b[n]=n*a[n]とおけば、その漸化式はb[n]=n*b[n-1]+n*b[n-2]と表せる。
b[n]-(n+1)*b[n-1]=-(b[n-1]-n*b[n-2])　と書けるので、n≧3とすれば
b[n]-(n+1)*b[n-1]=(-1)^(n-2)*(2*1-3*1*1)=(-1)^(n-1)　となる。
これはn=2でも正しいので、以下n≧2とする。
b[n]=(n+1)b[n-1]+(-1)^(n-1)　の両辺を(n+1)!で割れば
b[n]/(n+1)!=b[n-1]/n!+(-1)^(n-1)/(n+1)!
b[n]=(n+1)!*{Σ[k=2,n](-1)^(k-1)/(k+1)!+b[1]/2!}
　　　=(n+1)!*Σ[k=1,n](-1)^(k-1)/(k+1)!
よってa[n]=(n+1)!/n*Σ[k=1,n](-1)^(k-1)/(k+1)!=
これはn=1でも成り立つ。