3高知大学 2017年 数学 第3問解答・解説

準備（下降位置の記法）

順列 $\pi=(\pi_1,\pi_2,\ldots,\pi_n)$ に対し，$1\le i\le n-1$ を満たす位置 $i$ が下降位置であるとは $\pi_i>\pi_{i+1}$ が成り立つことをいう．下降位置の個数が $\pi$ の下降回数である．

補題　 $1\le k\le n-1$ を満たす整数 $k$ を固定する．$\{1,2,\ldots,n\}$ の部分集合 $S$（$|S|=k$）に対し，$S$ の要素を小さい順に並べたものを第 $1$ 項から第 $k$ 項とし，補集合 $S^{c}=\{1,\ldots,n\}\setminus S$ の要素を小さい順に並べたものを第 $k+1$ 項から第 $n$ 項として結合した順列を $\pi(S)$ とする．このとき次が成り立つ．

(i) $S\mapsto\pi(S)$ は，「位置 $1,\ldots,k-1$ にも位置 $k+1,\ldots,n-1$ にも下降がない順列」（すなわち下降が起こりうるのは位置 $k$ だけである順列）全体との間の一対一の対応であり，その総数は ${}_{n}C_{k}$ である．

(ii) $S=\{1,2,\ldots,k\}$ のとき，かつそのときに限り $\pi(S)$ は下降回数 $0$（恒等順列 $1,2,\ldots,n$）である．それ以外の ${}_{n}C_{k}-1$ 個の $S$ に対しては，$\pi(S)$ の下降回数はちょうど $1$ で，その下降位置は $k$ である．

証明．前半 $k$ 項，後半 $n-k$ 項はそれぞれ小さい順（増加列）に並んでいるから，位置 $1,\ldots,k-1$ と位置 $k+1,\ldots,n-1$ には下降がない．したがって $\pi(S)$ の下降回数は，位置 $k$（$\pi(S)_k$ と $\pi(S)_{k+1}$ の間）で下降が起こるかどうかだけで決まり，$0$ か $1$ である．位置 $k$ で下降が起こる条件は $$\displaystyle \pi(S)_k>\pi(S)_{k+1}\text{であるための必要十分条件は} \max S>\min S^{c}$$ である．

$S=\{1,\ldots,k\}$ のときは $\displaystyle \max S=k$，$S^{c}=\{k+1,\ldots,n\}$ より $\displaystyle \min S^{c}=k+1>k$ なので上の不等式は成り立たず，位置 $k$ に下降はない．よってこのとき $\pi(S)=(1,2,\ldots,n)$ で下降回数は $0$ である．

逆に $S\neq\{1,\ldots,k\}$ とする．もし $S$ の要素がすべて $k$ 以下ならば $S\subset\{1,\ldots,k\}$ かつ $|S|=k$ より $S=\{1,\ldots,k\}$ となり矛盾するから，$S$ は $k+1$ 以上の要素を少なくとも $1$ つ含む．同様に，もし $\{1,\ldots,k\}$ の要素がすべて $S$ に含まれるならば $|S|=k$ より $S=\{1,\ldots,k\}$ となり矛盾するから，$S^{c}$ は $k$ 以下の要素を少なくとも $1$ つ含む．ゆえに $\displaystyle \max S\ge k+1>k\ge\min S^{c}$ となり，位置 $k$ で下降が起こる．したがって $\pi(S)$ の下降回数はちょうど $1$ で，下降位置は $k$ である．

対応 $S\mapsto\pi(S)$ が一対一の対応であることは，$\pi(S)$ の最初の $k$ 項の集合がちょうど $S$ に一致し，$S$ から $\pi(S)$ が一意に定まることから従う．よって（i），（ii）が示された．$\blacksquare$

系　 $1\le j\le n-1$ に対し，下降位置がただ $1$ つで，それが位置 $j$ であるような順列の個数は ${}_{n}C_{j}-1$ である．（補題(ii)そのもの．）

(1)　$a_4$ を求める．

下降回数が $1$ である順列は，下降位置がただ $1$ つの位置 $k=1,2,3$ のいずれかにある順列である．系より，位置 $k$ がただ $1$ つの下降位置である順列の個数は ${}_{4}C_{k}-1$ であり，これらは $k$ ごとに排反（下降位置は一意に定まる）だから $$a_4=({}_{4}C_{1}-1)+({}_{4}C_{2}-1)+({}_{4}C_{3}-1)=(4-1)+(6-1)+(4-1)=3+5+3=11 .$$

（検算：具体的に列挙すると，$k=1$：$2134,3124,4123$　 $k=2$：$1324,1423,2314,2413,3412$　 $k=3$：$1243,1342,2341$ の合計 $3+5+3=11$ 個であり，実際にいずれも下降回数が $1$ であることが直接確認できる．）

$$a_4=11 .$$

(2)　$\displaystyle a_n=\displaystyle\sum\limits _{k=0}^{n}\left({}_{n}C_{k}-1\right)$ を示す．

下降回数が $1$ である順列は下降位置をただ $1$ つ持ち，その位置は $\{1,\ldots,n-1\}$ のいずれかである．下降位置は各順列に対して一意に定まるから，位置ごとの場合分けは排反であり，系より $$\displaystyle a_n=\sum\limits _{j=1}^{n-1}\left({}_{n}C_{j}-1\right) .$$ ここで ${}_{n}C_{0}-1=1-1=0$，${}_{n}C_{n}-1=1-1=0$ であるから，$k=0$ と $k=n$ の項を付け加えても和の値は変わらない．よって $$\displaystyle a_n=\sum\limits _{k=0}^{n}\left({}_{n}C_{k}-1\right)$$ が成り立つ．$\blacksquare$

(3)　$a_n$ を求める．

二項定理（または $\{1,\ldots,n\}$ の部分集合の総数）より $\displaystyle\sum\limits _{k=0}^{n}{}_{n}C_{k}=2^{n}$ であるから，(2)の結果より $$\displaystyle a_n=\sum\limits _{k=0}^{n}{}_{n}C_{k}-\sum\limits _{k=0}^{n}1=2^{n}-(n+1)=2^{n}-n-1 .$$

（検算：$n=4$ のとき $2^4-4-1=16-5=11$ で(1)の結果と一致する．$n=1$ のとき $2-1-1=0$（長さ $1$ の順列は下降回数が常に $0$ であり整合），$n=2$ のとき $2^2-2-1=1$（順列 $21$ のみが下降回数 $1$），$n=3$ のとき $2^3-3-1=4$（実際 $132,213,231,312$ の $4$ 個）と，いずれも実際の値と一致する．）

$$a_n=2^{n}-n-1 .$$

(4)　$n\ge2$ のとき $\displaystyle b_n=\sum\limits _{k=1}^{n-1}{}_{n}C_{k}\,a_{n-k}-\sum\limits _{m=1}^{n-1}(m-1)\left({}_{n}C_{m}-1\right)$ であることを示す．

$1\le k\le n-1$ を満たす整数 $k$ を固定するごとに，次の組 $(S,\tau)$ を考える：$S$ は $\{1,\ldots,n\}$ の $k$ 元部分集合，$\tau=(\tau_1,\ldots,\tau_{n-k})$ は $\{1,\ldots,n-k\}$ の順列で下降回数がちょうど $1$ のもの（このような $\tau$ は定義より $a_{n-k}$ 個ある．$1\le n-k\le n-1$ なので $a_{n-k}$ はすでに定義済みの量である）．

$S^{c}=\{1,\ldots,n\}\setminus S$ の要素を小さい順に $s_1<s_2<\cdots<s_{n-k}$ とし，$\tau$ から作った順列 $$\pi(S,\tau)=\bigl(\underbrace{S\text{ を小さい順に並べたもの}}_{\text{第 }1\text{ 項から第 }k\text{ 項}},\ s_{\tau_1},s_{\tau_2},\ldots,s_{\tau_{n-k}}\bigr)$$ を対応させる．（$j\mapsto s_{\tau_j}$ は $\{1,\ldots,n-k\}$ から $S^c$ への大小関係を保つ対応 $j\mapsto s_j$ に $\tau$ を合成したものだから，後半 $n-k$ 項のうちの下降位置は，$\tau$ の下降位置とちょうど同じ個数・同じ相対位置に現れる．）

固定した $k$ に対し，$(S,\tau)\mapsto\pi(S,\tau)$ は「前半 $k$ 項が増加列であり，後半 $n-k$ 項の内部（位置 $k+1,\ldots,n-1$）の下降回数がちょうど $1$ であるような順列」全体との間の一対一の対応であり，その個数は ${}_{n}C_{k}\cdot a_{n-k}$ である．ゆえに，$k=1,\ldots,n-1$ の組 $(k,S,\tau)$ の総数は $$\displaystyle \sum\limits _{k=1}^{n-1}{}_{n}C_{k}\,a_{n-k}$$ である．

$\pi(S,\tau)$ の下降回数を調べる．前半 $k$ 項は増加列だから位置 $1,\ldots,k-1$ に下降はなく，後半 $n-k$ 項の内部（位置 $k+1,\ldots,n-1$）には $\tau$ による下降がちょうど $1$ 個ある．よって残るのは位置 $k$（前半と後半の境目）だけであり， $$\pi(S,\tau)\text{ の下降回数}=1+\begin{cases}1 & (\pi(S,\tau)_k>\pi(S,\tau)_{k+1}\text{，すなわち境目にも下降がある場合)}\\ 0 & (\text{境目に下降がない場合})\end{cases}$$ すなわち，$\pi(S,\tau)$ の下降回数は必ず $1$ か $2$ のいずれかである．

以下，この対応で作られる順列を，下降回数がちょうど $2$ になる場合（境目にも下降がある場合）と，下降回数がちょうど $1$ になる場合（境目に下降がない場合）とに分けて数え直す．

(a) 下降回数が $2$ である順列は，この対応でちょうど $1$ 回ずつ現れる．

下降回数が $2$ である任意の順列 $\pi$ をとり，その $2$ つの下降位置を $i<j$（$1\le i<j\le n-1$）とする．$\pi$ は位置 $1,\ldots,i$，位置 $i+1,\ldots,j$，位置 $j+1,\ldots,n$ の各区間で増加列である．

$k=i$ ととり，$S=\{\pi_1,\ldots,\pi_i\}$（前半 $i$ 項の集合），$\tau$ を後半 $n-i$ 項 $(\pi_{i+1},\ldots,\pi_n)$ の大小関係のパターンとする．前半 $i$ 項は増加列だから条件を満たし，後半 $n-i$ 項の内部（位置 $i+1,\ldots,n-1$）に含まれる下降は $\pi$ の下降のうち位置 $j$（$j>i$ なので後半の内部に入る）のみであるから，ちょうど $1$ 個であり，$\tau$ は下降回数 $1$ の順列である．また境目の位置 $i$ はもとより $\pi$ の下降位置だから，$\pi(S,\tau)=\pi$ であり，下降回数は $1(\text{内部})+1(\text{境目})=2$ で一致する．

逆に，$k<i$ を取ると，後半 $n-k$ 項の内部（位置 $k+1,\ldots,n-1$）には $\pi$ の下降位置 $i,j$ が両方含まれてしまい（$k<i<j\le n-1$ なので），内部の下降が $2$ 個になって「下降回数ちょうど $1$ の $\tau$」という条件に反する．また $k\ge j$ をとると，前半 $k$ 項の内部（位置 $1,\ldots,k-1$）に $\pi$ の下降位置 $i$（$i<j\le k$）が入ってしまい，前半が増加列にならない．$k$ が $i<k<j$ の場合も同様に前半に位置 $i$ の下降が入り増加列にならない．よって，この $\pi$ を再現できる $k$ は $k=i$ のみである．

以上より，下降回数が $2$ である順列は，この対応でちょうど $1$ 回（$k=i$，すなわちその順列の最初の下降位置に対応する $k$）だけ現れる．

(b) 下降回数が $1$ である順列で，その下降位置が $j$（$1\le j\le n-1$）であるものは，この対応で $j-1$ 回現れる．

そのような順列 $\pi'$（下降回数 $1$，下降位置 $j$ のみ）を考える．$\pi'$ は位置 $1,\ldots,j$ で増加列，位置 $j+1,\ldots,n$ で増加列である．

$1\le k\le j-1$ を任意にとる．前半 $k$ 項（位置 $1,\ldots,k$）は $\pi'$ の増加区間 $1,\ldots,j$ の一部だから増加列である．後半 $n-k$ 項の内部（位置 $k+1,\ldots,n-1$）には，$\pi'$ の唯一の下降位置 $j$ が（$k<j\le n-1$ より）含まれ，それ以外に下降はないから，内部の下降はちょうど $1$ 個で，条件を満たす．また境目の位置 $k$ は増加区間 $1,\ldots,j$ の内部（$k<j$）にあるから下降ではない．したがって $S=\{\pi'_1,\ldots,\pi'_k\}$，$\tau=$ 後半 $n-k$ 項のパターンとして $\pi(S,\tau)=\pi'$ が再現され，このとき境目に下降がないので下降回数の合計は $1$ となり，$\pi'$ 自身の下降回数と一致する．

$k=j$ の場合，後半 $n-j$ 項の内部（位置 $j+1,\ldots,n-1$）には下降位置 $j$ が含まれず，$\pi'$ の下降はこれのみだったから後半内部の下降は $0$ 個になり，「下降回数ちょうど $1$ の $\tau$」という条件を満たさない．よって $k=j$ はこの対応の対象にならない．$k>j$ の場合は前半 $k$ 項の内部（位置 $1,\ldots,k-1$）に下降位置 $j$（$j<k$）が入ってしまい，前半が増加列という条件を満たさない．

以上より，$\pi'$ を再現できる $k$ は $k=1,2,\ldots,j-1$ のちょうど $j-1$ 個である．

(c) 集計

(a)(b)より $$\displaystyle \sum\limits _{k=1}^{n-1}{}_{n}C_{k}\,a_{n-k} =\underbrace{b_n}_{\text{下降回数2の順列，各1回}}\ +\ \underbrace{\sum\limits _{j=1}^{n-1}(j-1)\bigl({}_{n}C_{j}-1\bigr)}_{\text{下降回数1・下降位置}j\text{の順列，各}(j-1)\text{回（系より個数}{}_{n}C_{j}-1)}$$ であるから，$m$ で書き直して $$\displaystyle b_n=\sum\limits _{k=1}^{n-1}{}_{n}C_{k}\,a_{n-k}-\sum\limits _{m=1}^{n-1}(m-1)\left({}_{n}C_{m}-1\right)$$ が成り立つ．$\blacksquare$

（検算：$n=2$ のとき，右辺 $={}_{2}C_{1}a_1-(1-1)({}_{2}C_{1}-1)=2\cdot0-0=0$．長さ $2$ の順列の下降回数は $0$ か $1$ しかないから $b_2=0$ で一致．

$n=3$ のとき，右辺 $={}_{3}C_{1}a_2+{}_{3}C_{2}a_1-\bigl[(1-1)({}_{3}C_{1}-1)+(2-1)({}_{3}C_{2}-1)\bigr]=3\cdot1+3\cdot0-\bigl[0+1\cdot2\bigr]=3-2=1$．実際，長さ $3$ の順列で下降回数が $2$ であるものは $321$ のみだから $b_3=1$ で一致．

$n=4$ のとき，右辺 $={}_{4}C_{1}a_3+{}_{4}C_{2}a_2+{}_{4}C_{3}a_1-\bigl[(1-1)({}_{4}C_{1}-1)+(2-1)({}_{4}C_{2}-1)+(3-1)({}_{4}C_{3}-1)\bigr]$ $=4\cdot4+6\cdot1+4\cdot0-\bigl[0+1\cdot5+2\cdot3\bigr]=16+6+0-(5+6)=22-11=11$． これは全順列 $24$ 個のうち下降回数 $0,1,2,3$ のものがそれぞれ $1,11,11,1$ 個（合計 $24$）であることと整合する．）