数学A 場合の数 問題 17 解説

方針・初手

順序を区別するので、これは「順序つきの分割」、すなわち自然数 $n$ の分け方を考える問題である。

$n$ 個の $1$ を横に並べて、

$$ 1+1+\cdots+1 $$

隣り合う $1$ と $1$ の間に「区切りを入れるか入れないか」を考えると、すべての表し方を数えることができる。

解法1

自然数 $n$ を $1$ の和として

$$ n=1+1+\cdots+1 $$

と表す。このとき、$1$ は全部で $n$ 個あるので、隣り合う $1$ の間は $n-1$ か所ある。

各すき間について、区切るか区切らないかを選ぶ。

たとえば $n=5$ の場合、

$$ 1\mid 1+1\mid 1\mid 1 $$

のように区切ると、

$$ 1+2+1+1 $$

という表し方に対応する。

したがって、$n-1$ か所それぞれについて「区切る」「区切らない」の $2$ 通りがあるので、全体では

$$ 2^{n-1} $$

通りになる。

ただし、この中にはどこにも区切りを入れない場合が含まれている。この場合は

$$ n $$

という1項だけの表し方になるが、問題では「$n$ をそれより小さい自然数の和として表す」ので、これは認められない。

よって、求める表し方の数は

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

である。

したがって、

$$ \begin{aligned} n=4 &\text{ のとき } 2^{3}-1=7,\\ n=5 &\text{ のとき } 2^{4}-1=15 \end{aligned} $$

となる。

解法2

$n$ の表し方を、最初の数によって分類する。

最初の数を $k$ とする。ただし $1\leq k\leq n-1$ である。残りは $n-k$ を順序つきに表せばよい。

ここで、残りの $n-k$ は、1項で表してもよい。つまり、自然数 $m$ を順序つきの正の整数の和として表す方法の総数を $b_m$ とすると、これは

$$ b_m=2^{m-1} $$

である。

したがって、$n$ の表し方の数を $a_n$ とすると、

$$ a_n=\sum_{k=1}^{n-1} b_{n-k} $$

である。よって、

$$ \begin{aligned} a_n &=\sum_{k=1}^{n-1}2^{n-k-1}\\ &=2^{n-2}+2^{n-3}+\cdots+2^0\\ &=2^{n-1}-1 \end{aligned} $$

となる。

したがって、

$$ a_4=2^3-1=7 $$

$$ a_5=2^4-1=15 $$

である。

解説

この問題は、普通の「分割」と違って順序を区別する点が重要である。したがって、$4=1+3$ と $4=3+1$ は別の表し方として数える。

順序を区別する和の問題では、「$1$ を並べて、すき間に区切りを入れる」という考え方が有効である。$n$ 個の $1$ の間には $n-1$ 個のすき間があり、それぞれを区切るかどうかで表し方が決まる。

ただし、どこにも区切りを入れない場合は $n$ そのものになるため、問題の条件に合わない。この1通りを除くことが最後の注意点である。

答え

(1)

$7$ 通り

(2)

$15$ 通り

(3)

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