自然数$n$に対し，$3$個の数字$1,\ 2,\ 3$から重複を許して$n$個並べたもの$(x_1,\ x_2,\ \cdots,\ x_n)$の全体の集合を$S_n$とおく．$S_n$の要素$(x_1,\ x_2,\ \cdots,\ x_n)$に対し，次の$2$つの条件を考える．
条件$\mathrm{C}_{12}$：$1 \leqq i<j \leqq n$である整数$i,\ j$の組で，$x_i=1$，$x_j=2$を満たすものが少なくとも$1$つ存在する．
条件$\mathrm{C}_{123}$：$1 \leqq i<j<k \leqq n$である整数$i,\ j,\ k$の組で，$x_i=1$，$x_j=2$，$x_k=3$を満たすものが少なくとも$1$つ存在する．
例えば，$S_4$の要素$(3,\ 1,\ 2,\ 2)$は条件$\mathrm{C}_{12}$を満たすが，条件$\mathrm{C}_{123}$は満たさない．
$S_n$の要素$(x_1,\ x_2,\ \cdots,\ x_n)$のうち，条件$\mathrm{C}_{12}$を満たさないものの個数を$f(n)$，条件$\mathrm{C}_{123}$を満たさないものの個数を$g(n)$とおく．このとき以下の各問いに答えよ．
(1) $f(4)$と$g(4)$を求めよ．
(2) $f(n)$を$n$を用いて表せ．
(3) $g(n+1)$を$g(n)$と$f(n)$を用いて表せ．
(4) $g(n)$を$n$を用いて表せ．