3徳島大学 2014年 数学 第3問解答・解説

$\text{(1)}\quad$ $a_3$ は左側の2枚より大きく、右側の2枚よりも大きいので、全体の最大値5である。残りの$\{1,2,3,4\}$から左側に置く2枚を選べば、左側は小さい順、右側は残りを大きい順に置くしかない。したがって $$\displaystyle \binom{4}{2}=6$$ 通りである。

$\text{(2)}\quad$ $k$ を固定すると、$a_k$ は列全体の最大値 $n$ である。左側の $k-1$ 枚を$\{1,2,\ldots,n-1\}$から選ぶと、その並びは小さい順に定まり、残りは右側に大きい順に定まる。よってこの $k$ に対する並べ方は$\displaystyle \binom{n-1}{k-1}$通りである。最大値の位置 $k$ は一意なので、異なる $k$ の場合は重ならない。したがって求める総数は $$\displaystyle \sum\limits _{k=2}^{n-1}\binom{n-1}{k-1} =\sum\limits _{r=1}^{n-2}\binom{n-1}{r} =2^{n-1}-\binom{n-1}{0}-\binom{n-1}{n-1} =2^{n-1}-2$$ 通りである。

$\text{(3)}\quad$ $p,q$ を固定する。$a_1=n,\ a_p=1$ であり、$a_1>a_2>\cdots>a_p$ だから、位置$2$から $p-1$ には$\{2,3,\ldots,n-1\}$から選んだ $p-2$ 個を大きい順に置く。選び方は$\displaystyle \binom{n-2}{p-2}$通りである。残る $n-p$ 個の数を位置 p+1 から n に置くが、条件より $a_q$ はその最大値であり、位置 $q$ の左側は小さい順、右側は大きい順に定まる。最大値以外の n-p-1 個から、位置 $p+1$ から $q-1$ に置く $q-p-1$ 個を選べばよい。したがって固定した $p,q$ に対する数は $$\displaystyle \binom{n-2}{p-2}\binom{n-p-1}{q-p-1}$$ である。1 の位置 $p$ と、残った列の最大値の位置 $q$ はそれぞれ一意だから、全体は $$\displaystyle \begin{aligned} N_n &=\sum\limits _{p=2}^{n-2}\sum\limits _{q=p+1}^{n-1} \binom{n-2}{p-2}\binom{n-p-1}{q-p-1}\\ &=\sum\limits _{p=2}^{n-2}\binom{n-2}{p-2} \left(2^{n-p-1}-1\right). \end{aligned}$$ ここで $m=n-2,\ j=p-2$ とおくと $$\displaystyle \begin{aligned} N_n &=\sum\limits _{j=0}^{m-2}\binom{m}{j}\left(2^{m-1-j}-1\right)\\ &=\left(\frac{3^m}{2}-m-\frac12\right) -\left(2^m-m-1\right)\\ &=\frac{3^m-2^{m+1}+1}{2} =\frac{3^{n-2}-2^{n-1}+1}{2}. \end{aligned}$$ したがって求める総数は$\displaystyle \frac{3^{n-2}-2^{n-1}+1}{2}$通りである。