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

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

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

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

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

$1,2,3,\cdots,n$ を並び替えて出来る数列$c_1,c_2,c_3,\cdots,c_n$ について、$1$以上$n$以下の任意の整数$i$に対し$c_i\neq i$ が成り立つようなものの個数を$D_n$とする。
$D_n$を$D_{n-2}$と$D_{n-1}$および$n$を用いて表せ。

（完全順列、有名問題）

$n$ を正の整数とする。赤玉と白玉がそれぞれ $n$ 個ずつ入った $1$ つの袋から $1$ 個の玉を取り出す操作を考える。取り出した玉はもとに戻さず，袋の中が空になるまでこの操作を繰り返す。$i=1,2,\cdots,2n$ として，$i$ 回の操作後に取り出した赤玉と白玉の個数をそれぞれ $r_i,\ w_i$ とする。また，次の条件を満たす場合の数を $a_n$ とする。

すべての $i=1,2,\cdots,2n$ に対して，$r_i \ge w_i$

(1)　$a_3,\ a_4,\ a_5$ を求めよ。

(2)　$a_n$ を求めよ。

(3)　${}_{2n}C_n$ を二項係数とするとき，$\displaystyle\frac{1}{2\sqrt{n}} \le \frac{{}_{2n}C_n}{4^n} \le \frac{1}{\sqrt{2n+1}}$ を示せ。

(4)　$N$ を正の整数とするとき，$\displaystyle\frac{N}{2(N+1)} \le \sum_{n=1}^{N} \frac{a_n}{4^n\cdot\sqrt{n}} \le \frac{N}{\sqrt{2}(N+1)}$ を示せ。

（旭川医大、カタラン数）