隣どうしの入れかえを往復して小さい順に並ぶ札の並び方の数と漸化式

$n$ を $2$ 以上の整数とする。$1$ から $n$ までの数字が書かれた札が各 $1$ 枚ずつ合計 $n$ 枚あり，横一列におかれている。$1$ 以上 $(n - 1)$ 以下の整数 $i$ に対して，次の操作 $(\mathrm{T}_i)$ を考える。

$(\mathrm{T}_i)$　左から $i$ 番目の札の数字が，左から $(i + 1)$ 番目の札の数字よりも大きければ，これら $2$ 枚の札の位置を入れかえる。そうでなければ，札の位置をかえない。

最初の状態において札の数字は左から $A_1, A_2, \ldots, A_n$ であったとする。この状態から $(n - 1)$ 回の操作 $(\mathrm{T}_1), (\mathrm{T}_2), \ldots, (\mathrm{T}_{n-1})$ を順に行った後，続けて $(n - 1)$ 回の操作 $(\mathrm{T}_{n-1}), \ldots, (\mathrm{T}_2), (\mathrm{T}_1)$ を順に行ったところ，札の数字は左から $1, 2, \ldots, n$ と小さい順に並んだ。以下の問いに答えよ。

(1) $A_1$ と $A_2$ のうち少なくとも一方は $2$ 以下であることを示せ。

(2) 最初の状態としてありうる札の数字の並び方 $A_1, A_2, \ldots, A_n$ の総数を $c_n$ とする。$n$ が $4$ 以上の整数であるとき，$c_n$ を $c_{n-1}$ と $c_{n-2}$ を用いて表せ。