トップ› 北海道大学› 1977年› 理系第6問

北海道大学 1977年理系第6問解説

方針・初手

単調非減少という条件から、関数 $f$ の値域を決定したとき、各値をとる定義域の要素の個数が決まれば $f$ が一意に定まることに着目する。
したがって、「値域の要素の選び方」と「各要素をとる回数の割り当て方」の積として $\alpha(k)$ を求める。

解法1

(1)

$\alpha(1)$ について、関数 $f$ の値域が $1$ 個の値のみからなる場合を考える。 $f(1) = f(2) = \cdots = f(n) = a$ （$a \in N$）となる場合であり、値 $a$ の選び方は $1$ から $n$ までの $n$ 通りである。したがって、

$$ \alpha(1) = n $$

である。

次に $\alpha(2)$ について、値域が $2$ 個の相異なる値からなる場合を考える。その $2$ つの値を $a, b$ （$a < b$，$a, b \in N$）とする。 $a, b$ の選び方は $N$ の要素 $n$ 個から $2$ 個を選ぶ組み合わせなので、${}_n \mathrm{C}_2$ 通りである。条件 $f(1) \leqq f(2) \leqq \cdots \leqq f(n)$ を満たし、かつ値域が $\{a, b\}$ であるためには、ある整数 $m$ （$1 \leqq m \leqq n-1$）が存在して、

$$ \begin{aligned} f(1) &= f(2) = \cdots = f(m) = a \\ f(m+1) &= f(m+2) = \cdots = f(n) = b \end{aligned} $$

となる必要がある。このような $m$ の選び方は、$1$ から $n-1$ までの $(n-1)$ 通りである。したがって、

$$ \alpha(2) = {}_n \mathrm{C}_2 \times (n-1) = \frac{n(n-1)}{2} \times (n-1) = \frac{n(n-1)^2}{2} $$

である。

(2)

$f$ のとる相異なる値がちょうど $k$ 個であるとする。この $k$ 個の値を $y_1, y_2, \cdots, y_k$ （$y_1 < y_2 < \cdots < y_k$）とする。これらは $N$ の要素であるから、選び方は ${}_n \mathrm{C}_k$ 通りである。

各 $y_i$ （$1 \leqq i \leqq k$）に対して、$f(x) = y_i$ を満たす $x \in N$ の個数を $c_i$ とおく。値域がちょうどこの $k$ 個の値であるため、各 $c_i$ は $c_i \geqq 1$ を満たす自然数である。また、定義域 $N$ の要素数は $n$ であるから、

$$ c_1 + c_2 + \cdots + c_k = n $$

が成り立つ。関数 $f$ は単調非減少（$i < j \implies f(i) \leqq f(j)$）であるため、各値をとる個数 $c_1, c_2, \cdots, c_k$ が定まれば、関数 $f$ の対応は一意に定まる。

方程式 $c_1 + c_2 + \cdots + c_k = n$ を満たす自然数 $c_i$ の組の個数は、$n$ 個のものを $1$ 列に並べ、その間の $(n-1)$ 個の隙間から $(k-1)$ 箇所を選んで仕切りを入れる方法の数に等しく、${}_{n-1} \mathrm{C}_{k-1}$ 通りである。したがって、値域の選び方と合わせて、

$$ \alpha(k) = {}_n \mathrm{C}_k \times {}_{n-1} \mathrm{C}_{k-1} $$

となる。

(3)

$\frac{n}{2} \leqq k \leqq n-1$ のとき、$\alpha(k)$ と $\alpha(k+1)$ の大小を比較する。 (2) の結果より、$\alpha(k) > 0$ であり、

$$ \alpha(k) = \frac{n!}{k!(n-k)!} \times \frac{(n-1)!}{(k-1)!(n-k)!} $$

$$ \alpha(k+1) = \frac{n!}{(k+1)!(n-k-1)!} \times \frac{(n-1)!}{k!(n-k-1)!} $$

である。両者の比をとると、

$$ \begin{aligned} \frac{\alpha(k+1)}{\alpha(k)} &= \frac{\frac{n!}{(k+1)!(n-k-1)!} \times \frac{(n-1)!}{k!(n-k-1)!}}{\frac{n!}{k!(n-k)!} \times \frac{(n-1)!}{(k-1)!(n-k)!}} \\ &= \frac{k!(n-k)!}{(k+1)!(n-k-1)!} \times \frac{(k-1)!(n-k)!}{k!(n-k-1)!} \\ &= \frac{n-k}{k+1} \times \frac{n-k}{k} \\ &= \frac{(n-k)^2}{k(k+1)} \end{aligned} $$

となる。

ここで、条件 $\frac{n}{2} \leqq k \leqq n-1$ を用いて分母と分子の大きさを比べる。 $k \geqq \frac{n}{2}$ より $2k \geqq n$、すなわち $k \geqq n-k$ である。さらに $n \geqq 2$ と $k \geqq \frac{n}{2}$ より、$k$ は自然数であるから $k > 0$ であり、また $k \leqq n-1$ より $n-k \geqq 1 > 0$ である。したがって、

$$ k+1 > k \geqq n-k > 0 $$

が成り立つため、両辺が正であることから平方したり積をとったりしても不等号の向きは変わらず、

$$ k(k+1) > k^2 \geqq (n-k)^2 $$

となる。ゆえに、$\frac{(n-k)^2}{k(k+1)} < 1$ となるため、

$$ \frac{\alpha(k+1)}{\alpha(k)} < 1 $$

が成り立つ。 $\alpha(k) > 0$ より、両辺に $\alpha(k)$ を掛けて、

$$ \alpha(k) > \alpha(k+1) $$

を得る。

解説

広義単調増加関数の個数を数える典型問題である。
「値域を固定し、各値をとる定義域の要素の個数を数える」というアプローチをとると、重複組合せや仕切りを用いた自然数解の個数の問題に帰着できる。
(1) を具体的に考えることで、(2) の一般化への見通しが立ちやすくなる。(1) で直接 (2) の考え方を用いて $\alpha(1) = {}_n \mathrm{C}_1 {}_{n-1} \mathrm{C}_0$, $\alpha(2) = {}_n \mathrm{C}_2 {}_{n-1} \mathrm{C}_1$ と求めてもよい。
(3) では階乗を含む式の大小比較を行うため、比をとって $1$ と比較する手法が定石となる。範囲の条件 $k \geqq \frac{n}{2}$ を適切に用いて不等式を評価することが重要である。