北海道大学 2002年 理系 第2問 解説

方針・初手

ちょうど2種類の数字から成る $n$ 桁の自然数を数える。$0$ を使わない場合と、$0$ を使う場合に分けるのが最短である。

解法1

(1)

$1000$ から $9999$ までの4桁の自然数のうち、ちょうど2種類の数字から成るものを数える。

0 を使わない場合

$1,2,\dots,9$ から異なる2個の数字を選ぶ方法は

$$ {}_9\mathrm{C}_{2}=36 $$

通りある。

選んだ2個の数字だけを使って4桁を作る方法は $2^4$ 通りだが、片方の数字だけしか現れないものは2通りあるので、両方の数字が現れるものは

$$ 2^4-2=14 $$

通りである。

したがってこの場合の個数は

$$ 36\times 14=504 $$

通り。

0 を使う場合

このとき使う数字は $0$ と、$1,2,\dots,9$ のうちの1個であるから、その非零の数字の選び方は $9$ 通り。

4桁の自然数なので、千の位は必ずその非零の数字でなければならない。残り3桁は $0$ またはその数字のどちらかだが、全部その数字だと 0 を使わず1種類の数字になってしまう。したがって残り3桁の決め方は

$$ 2^3-1=7 $$

通りである。

よってこの場合の個数は

$$ 9\times 7=63 $$

通り。

以上より求める個数は

$$ 504+63=567 $$

通りである。

(2)

$n$ 桁の自然数について同様に数える。

0 を使わない場合

数字の選び方は

$$ {}_9\mathrm{C}_{2}=36 $$

通り。

選んだ2個の数字だけを使って $n$ 桁を作る方法は $2^n$ 通りだが、片方の数字だけしか現れないものを除くので

$$ 2^n-2 $$

通り。

したがってこの場合の個数は

$$ 36(2^n-2) $$

通り。

0 を使う場合

非零の数字の選び方は $9$ 通り。

先頭の1桁はその非零の数字に決まり、残り $n-1$ 桁は $0$ またはその数字のどちらかである。ただし全部その数字だと1種類だけになるので除く。よって残りの決め方は

$$ 2^{n-1}-1 $$

通り。

したがってこの場合の個数は

$$ 9(2^{n-1}-1) $$

通り。

よって全体では

$$ \begin{aligned} 36(2^n-2)+9(2^{n-1}-1) &=72\cdot 2^{n-1}-72+9\cdot 2^{n-1}-9\\ &=81\cdot 2^{n-1}-81\\ &=81(2^{n-1}-1) \end{aligned} $$

となる。

解説

「使う数字の種類数を固定して並べる」問題では、先に数字集合を選び、その後に並べ方を数える。ここでは 0 の扱いだけが例外なので、0 を含む場合だけ別に処理すればよい。

答え

(1) $567$ 個

(2) $81(2^{n-1}-1)$ 個