5人のキャッチボール

問題の観察

一般的な状況に対して，場合の数を求める標準的な問題です．
まずは状況をきちんと把握することから始めましょう．キャッチボールなので，問題文の通り自分自身にボールを投げることはありません．ボールが$n$回移動することを$n$パスと呼ぶことにしましょう．問題文の条件から，$n$パス後には$A$の手にボールがあります．

例えば，$n=5$の時は，$A→B→A→D→A$などがありえます．
このように途中で$A$にボールが渡ってもよいことには注意してください．さて，ここでは漸化式を用いる解法を紹介します．

求めるべきものを文字でおく

漸化式を立てるときに重要なのは，何を文字に置くかということです．基本的には，問題で問われているものをそのまま文字で置くとうまくいくことが多いです．

$a_n$:$n$パス後に$A$がボールを持っている場合の数とする．

求めるべき答えは$a_n$です．しかしこれだけでは漸化式を立てることはできません．そこで，この$a_n$と相性のいい文字をさらにおいてみます．

$b_n$:$n$パス後に$A$以外の$4$人のいずれかがボールを持っている場合の数とする．

$a_2=4,b_2=12$であることは容易に確認できます．さて，実際に漸化式を立ててみましょう．

漸化式を立てる

$n$パス後に$A$がボールを持っているという制約を抜きにして，ボールが$n$回自由に移動する場合の数を考えると， $$a_n+b_n=4^n$$ が成り立ちます．また，$n+1$パス後に$A$がボールを持っているためには，$n$パス後に$A$以外の$4$人のいずれかがボールを持っていることが必要十分なので， $$a_{n+1}=b_n$$ これらより， $$a_{n+1}=4^n-a_n　,　a_2=4$$ これを解けば良いということになります．実際にこの漸化式を解くと， $$\color{red}{a_n=\frac{1}{5}(4^n+(-1)^n4)}$$ となります．

別の漸化式の立て方

他にも漸化式の立て方があります．
$n+1$パス後に$A$以外のいずれか$4$人がボールを持っている場合の数を考えると， $$b_{n+1}=4a_n+3b_n$$ が成り立ちます．これと$a_{n+1}=b_n$より， $$a_{n+2}=3a_{n+1}+4a_n　,　a_2=4$$ となるので，この隣接$2$項間漸化式を解いても良いです．

文字の置き方と漸化式の立て方に工夫が必要です．