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

方針・初手

順序を区別して正の整数の和に分ける問題であるから、これは「順序つき分割」である。

$n$ を $k$ 個の正の整数の和として表すには、$n$ 個のものを一列に並べ、その間にある $n-1$ 個のすき間から $k-1$ 個を選んで仕切ればよい。

解法1

$n$ 個のものを

$$ \underbrace{\circ\ \circ\ \cdots\ \circ}_{n\text{個}} $$

のように一列に並べる。この $n$ 個の間には、仕切りを入れられる場所が $n-1$ 個ある。

ここから $k-1$ 個の場所を選んで仕切ると、列は $k$ 個のまとまりに分かれる。それぞれのまとまりの個数が、和として現れる $k$ 個の正の整数になる。

逆に、$n$ を $k$ 個の正の整数の和として表したものが1つ与えられれば、その各項の区切り位置は一意に決まる。

したがって、$n$ を $k$ 個の正の整数の和として表す方法の数は

$$ {}*{{n-1}}C*{{k-1}} $$

である。

(1)

$6$ を $4$ 個の正の整数の和で表す場合、$6$ 個のものの間にある $5$ 個のすき間から、$3$ 個の仕切り位置を選べばよい。

よって、求める数は

$$ {}_5C_3=10 $$

である。

(2)

$n$ を $4$ 個の正の整数の和で表す場合、$n-1$ 個のすき間から $3$ 個の仕切り位置を選べばよい。

したがって、求める数は

$$ {}_{n-1}C_3 $$

である。

(3)

$n$ を $k$ 個の正の整数の和で表す場合、$n-1$ 個のすき間から $k-1$ 個の仕切り位置を選べばよい。

ただし、$2\leqq k\leqq n$ であるから、仕切り位置は実際に選べる。

よって

$$ a(k)={}*{n-1}C*{k-1} $$

である。

(4)

(3)より、

$$ \begin{aligned} \sum_{k=2}^{n}a(k) &= \sum_{k=2}^{n}{}*{n-1}C*{k-1} \end{aligned} $$

である。

ここで $j=k-1$ とおくと、$k=2$ のとき $j=1$、$k=n$ のとき $j=n-1$ であるから、

$$ \begin{aligned} \sum_{k=2}^{n}{}*{n-1}C*{k-1} &= \sum_{j=1}^{n-1}{}_{n-1}C_j \end{aligned} $$

となる。

二項定理より、

$$ \begin{aligned} \sum_{j=0}^{n-1}{}_{n-1}C_j &= 2^{n-1} \end{aligned} $$

である。ここから $j=0$ の項を除けばよいので、

$$ \begin{aligned} \sum_{j=1}^{n-1}{}_{n-1}C_j &= 2^{n-1}-1 \end{aligned} $$

である。

したがって、

$$ \sum_{k=2}^{n}a(k)=2^{n-1}-1 $$

である。

解説

正の整数の和に分ける問題では、まず「各項が少なくとも $1$ である」ことに注意する必要がある。

この問題では順序を区別するので、整数の組を並び順つきで数える。したがって、単なる整数の分割ではなく、仕切りを使った数え上げが有効である。

$n$ 個を一列に並べると、仕切りを入れられる場所は $n-1$ 個ある。$k$ 個の正の整数に分けるには、仕切りが $k-1$ 個必要である。この対応により、問題は組合せ

$$ {}*{n-1}C*{k-1} $$

を数える問題に帰着する。

最後の和では、添字を $j=k-1$ に変換し、二項係数の和

$$ \sum_{j=0}^{m}{}_mC_j=2^m $$

を用いる。今回は $j=0$ の項だけ含まれないので、$1$ を引く。

答え

(1)

$$ 10 $$

(2)

$$ {}_{n-1}C_3 $$

(3)

$$ a(k)={}*{n-1}C*{k-1} $$

(4)

$$ \sum_{k=2}^{n}a(k)=2^{n-1}-1 $$