一列に並んだ$3$つの部屋$\mathrm{A}$，$\mathrm{B}$，$\mathrm{C}$があり，$2$頭の象がいる．$2$頭の象は毎日$1$つの部屋から隣の部屋に，次のルールに従って移動する．

$0<p<1$とし，象が部屋$\mathrm{A}$と部屋$\mathrm{B}$にいるとき，部屋$\mathrm{A}$にいる象は部屋$\mathrm{A}$に留まり，部屋$\mathrm{B}$にいる象が確率$p$で部屋$\mathrm{C}$に移る．象が部屋$\mathrm{B}$と部屋$\mathrm{C}$にいるとき，部屋$\mathrm{C}$にいる象は部屋$\mathrm{C}$に留まり，部屋$\mathrm{B}$にいる象が確率$1-p$で部屋$\mathrm{A}$に移る．象が部屋$\mathrm{A}$と部屋$\mathrm{C}$にいるとき，部屋$\mathrm{A}$にいる象が確率$p$で部屋$\mathrm{B}$に移り，移らない場合は部屋$\mathrm{C}$にいる象が部屋$\mathrm{B}$に移る．$2$頭の象が同時に同じ部屋にいることはできない．
はじめに$2$頭の象はそれぞれ部屋$\mathrm{A}$と部屋$\mathrm{B}$にいるものとし，$2n$日後に象が部屋$\mathrm{A}$にいる確率を$a_n (n=1,\ 2,\ \cdots)$とおく．このとき，次の問いに答えよ．

(1)$a_1$を求めよ．
(2)$a_{n+1}$を$a_n$を用いて表せ．
(3)$\displaystyle p=\frac{2}{3}$のとき，$a_n$を求めよ．

$1$から$4$までの数字が$1$つずつ書かれた赤球が$4$個，$1$から$3$までの数字が$1$つずつ書かれた青球が$3$個，$1$から$2$までの数字が$1$つずつ書かれた白球が$2$個，合計$9$個の球がある．球の大きさはすべて同じである．次の場合の数を求めなさい．

(1)$9$個の球の中から$5$個の球を取り出す組合せの数
(2)$9$個の球の中から赤球を$2$個だけ含めて$5$個の球を取り出す組合せの数
(3)$9$個の球に書かれた数字をすべて消し，色だけに注目して$5$個の球を取り出す組合せの数
(4)$(3)$の条件で$5$個の球を取り出し，一列に並べる場合の数

以下の問いに答えなさい．

(1)赤，白，黒の玉がそれぞれ$3$個ずつあり，一列に並べるものとする．合計$9$個の玉の並べ方は何通りあるか求めなさい．なお，同じ色の玉は区別しないものとする．
(2)(1)の並べ方のうちで，先頭の$3$個の玉が同じ色であるか，末尾の$3$個の玉が同じ色であるか，少なくとも一方が成り立つ並べ方は何通りあるか求めなさい．
(3)空間において座標$(x,\ y,\ z)$にある点$\mathrm{P}$を$1$回の操作で$(x+1,\ y,\ z)$，$(x,\ y+1,\ z)$，$(x,\ y,\ z+1)$のいずれかを選んでその座標に移動させる．最初に$(0,\ 0,\ 0)$にある点$\mathrm{P}$を，$9$回の操作で$(3,\ 3,\ 3)$に移動させる選び方のうち，$(3,\ 0,\ 0)$，$(0,\ 3,\ 0)$，$(0,\ 0,\ 3)$，$(3,\ 3,\ 0)$，$(3,\ 0,\ 3)$，$(0,\ 3,\ 3)$のいずれも経由しないものは何通りあるか求めなさい．