北海道大学 2007年度 前期日程 第2次学力試験文系数学 第3問

(1)
(i) $$a_1\leqq a_2\leqq \cdots \leqq a_n=1$$ なら，すべての項が1でなければならない。したがって $A_n(1)=1$ である。 $$a_1\leqq \cdots \leqq a_n=2$$ の場合，列は$$\underset{r\text{ 個}}{\underbrace{1,\dots ,1}},\underset{n-r\text{ 個}}{\underbrace{2,\dots ,2}}$$の形で，最後が2なので $0\leqq r\leqq n-1$ である。よって $A_n(2)=n$ である。
(ii) $n\geqq 2$ とする。最後の項が3である非減少列の，直前までの最後の値は1,2,3のいずれかである。したがって $$A_n(3)=A_{n-1}(1)+A_{n-1}(2)+A_{n-1}(3)$$ である。
また，$A_n(3)$ を直接数えると，最後の3を1つ固定した後，残り $n-1$ 個の中に1,2,3がそれぞれ何個あるかを決めればよい。1,2,3の個数を $r_1,r_2,r_3$ とすると $r_1+r_2+r_3=n-1$ であり，非負整数解の個数は $${}_{n+1}{\mathrm{C}}_2={\displaystyle \frac{n(n+1)}{2}}$$ である。よって $$A_n(3)={\displaystyle \frac{n(n+1)}{2}}$$ である。
(2) $$a_1\leqq \cdots \leqq a_{n-1}$$ であり，さらに $a_{n-1}>a_n$ である。$a_{n-1}=1$ では最後にそれより小さい数を選べないので不可能である。 $a_{n-1}=2$ のとき，前半 $a_1,\dots ,a_{n-1}$ は $A_{n-1}(2)=n-1$ 通りで，$a_n$ は1のみである。したがって $n-1$ 通りである。 $a_{n-1}=3$ のとき，前半は $$A_{n-1}(3)={\displaystyle \frac{(n-1)n}{2}}$$ 通りで，$a_n$ は1または2の2通りである。したがって $$2\cdot {\displaystyle \frac{(n-1)n}{2}}=n(n-1)$$ 通りである。
合計して $$(n-1)+n(n-1)=(n-1)(n+1)=n^2-1$$ 通りである。

非減少列を数字の個数で表す。末尾が $j$ であることは $j$ が1個以上あることなので，最後の1個を固定した後の非負整数解として一度に数える。(2)では末尾直前の値を2と3に分ける。

(1)

(i) 末尾が1なら全項が1なので$$A_n(1)=1.$$末尾が2なら，1の個数を $0,1,\dots ,n-1$ から選べるので$$A_n(2)=n\mathrm{.}$$(ii) 末尾の3を1個固定する。残る $n-1$ 個に現れる1，2，3の個数を $r_1,r_2,r_3$ とすると$$r_1+r_2+r_3=n-1,r_i\geqq 0.$$よって$$A_n(3)={}_{n+1}{\mathrm{C}}_2={\displaystyle \frac{n(n+1)}{2}}\mathrm{.}$$また，末尾の3を除けば長さ $n-1$ の非減少列になるので$$A_n(3)=A_{n-1}(1)+A_{n-1}(2)+A_{n-1}(3)$$も同時に得られる。
(2) $a_{n-1}=2$ なら前半は$$A_{n-1}(2)=n-1$$通りで，最後は1に限る。$a_{n-1}=3$ なら前半は$$A_{n-1}(3)={\displaystyle \frac{(n-1)n}{2}}$$通りで，最後は1または2の2通りである。したがって総数は$$(n-1)+2\cdot {\displaystyle \frac{(n-1)n}{2}}=(n-1)(n+1)$$通りである。