CDのランダム再生に関する創作問題〜解けるものなら解いてみやがれ〜

昨日思いついた問題。
いや、「思いついてしまった問題」とでも言おうか。

思いついたあと、答えをぬるぬると考えていたのですが、思いのほか難問でした。
高校数学に触れてないから時間がかかっただけかな……。
もしかしたらあっさり解いてしまう人もいるかもしれない。そういう人、ときどきいるけど本当にすごいと思う。コツを教えてほしいものです。

さて、前置きは置いといて。
問題は以下のようなものです。
iTunesで音楽を聴いていて思いつきました。

*****
［問］
1曲目からn曲目まで収められているCDをランダム再生する。
ランダム再生は「元の曲でk番目だった曲の次にk+1番目の曲が再生されることはない」という条件で、ランダムに順番を変えて再生を行う。同じ曲が2度流れることはない。
例えばn=1ならば再生の仕方は1通り、n=2でも1通り、n=3ならば3通りである。
n曲分のランダム再生の仕方をP_nとする。
n≧3のとき、P_nを(P_n-1)と(P_n-2)を用いて表せ。
*****
（条件の抜け落ちや表記の稚拙さがあるかもしれませんが、そこはご了承を。）

iPod等でランダム再生をしたことのある方ならイメージしやすいと思うのですが、ランダム再生ではときどき「お、この曲とこの曲CDの順と同じだ」と思うことがあります。
その曲と曲の繋がりが自分の好きなものだったりすると嬉しくなりますよね。
個人的にはミスチルの「IT'S A WONDERFUL WORLD」の『Drawing』→『君が好き』の流れとか、好きです。

でも今回は「それってランダムちゃうやん！」ということで「ランダムに選ぶんだけど、元のCDのように曲が連続することだけはない」という条件にしたときの曲の再生の仕方を問題にしてみました。

具体的にいうと、例えば5曲の場合。
元のCDの1曲目を1、2曲目を2、……5曲目を5とすると、元のCDの並びは

12345

です。
今回のランダム再生で許されるのは、例えば

35421

みたいな並び。

35412

は「12」で元の順で連続してしまうのでダメ。

35241

では「4が元のCDの位置＝4曲目に入ってる！」と思うかもしれませんが、これはOK。4の前に3がきたり、4の後に5がきたりして順番になっちゃったらダメということです。

n=3まで書き出してみます。

〈n=1の場合（元：1）〉
1
のみ。

〈n=2の場合（元：12）〉
21
のみ。

〈n=3の場合（元：123）〉
132
213
321
の3通り。

逆に
123：12と23でアウト。
231：23でアウト。
312：12でアウト。

といった感じです。

問題の説明は以上です。
お時間ある方はぜひ挑戦してみてください。
答えが出ましたらぜひコメント欄に。

反応あるかなあ……。
解答は次に気力があるときに。たぶん次の日曜です。

ではでは、今週も元気に乗り切っていきましょう。