自然数 \(n\) に対し, \(3\) 個の数字 \(1, 2, 3\) から重複を許して \(n\) 個並べたもの \(( x _ 1 , x _ 2 , \cdots , x _ n)\) の全体の集合を \(S _ n\) とおく. \(S _ n\) の要素 \(( x _ 1 , x _ 2 , \cdots , x _ n)\) に対し, 次の \(2\) つの条件を考える.
条件 \( \text{C} {} _ {12}\) : \(1 \leqq i \lt j \leqq n\) である整数 \(i , j\) の組で, \(x _ i = 1\) , \(x _ j = 2\) を満たすものが少なくとも \(1\) つ存在する.
条件 \( \text{C} {} _ {123}\) : \(1 \leqq i \lt j \lt k \leqq n\) である整数 \(i , j , k\) の組で, \(x _ i = 1\) , \(x _ j = 2\) , \(x _ k = 3\) を満たすものが少なくとも \(1\) つ存在する.
例えば, \(S _ 4\) の要素 \(( 3, 1, 2, 2 )\) は条件 \( \text{C} {} _ {12}\) を満たすが, 条件 \( \text{C} {} _ {123}\) は満たさない.
\(S _ n\) の要素 \(( x _ 1 , x _ 2 , \cdots , x _ n)\) のうち, 条件 \( \text{C} {} _ {12}\) を満たさないものの個数を \(f(n)\) , 条件 \( \text{C} {} _ {123}\) を満たさないものの個数を \(g(n)\) とおく. このとき以下の各問いに答えよ.
(1) \(f(4)\) と \(g(4)\) を求めよ.
(2) \(f(n)\) を \(n\) を用いて表せ.
(3) \(g(n+1)\) を \(g(n)\) と \(f(n)\) を用いて表せ.
(4) \(g(n)\) を \(n\) を用いて表せ.
【 解 答 】
(1)
\(S _ 4\) の要素の数は全部で \[ 3^4 = 81 \ \text{通り} \ . \]
\(f(4)\) について
条件 \( \text{C} {} _ {12}\) を満たす要素の数を, \(S _ 4\) に含まれる数字の組合せで場合分けして, 数える.1* \(S _ n = \{ 1, 1, 1, 2 \}\) のとき
\({} _ 4 \text{C} {} _ 1 = 4\) 通りの要素があり, \(( 2, 1, 1, 1 )\) 以外は条件を満たすので \[ 4 -1 = 3 \ \text{通り} \ . \]2* \(S _ n = \{ 1, 1, 2, 2 \}\) のとき
\({} _ 4 \text{C} {} _ 2 = 6\) 通りの要素があり, \(( 2, 2, 1, 1 )\) 以外は条件を満たすので \[ 6 -1 = 5 \ \text{通り} \ . \]3* \(S _ n = \{ 1, 2, 2, 2 \}\) のとき
\({} _ 4 \text{C} {} _ 1 = 4\) 通りの要素があり, \(( 2, 2, 2, 1 )\) 以外は条件を満たすので \[ 4 -1 = 3 \ \text{通り} \ . \]4* \(S _ n = \{ 1, 1, 2, 3 \}\) のとき
「 \(1, 1, 2\) 」または「 \(1, 2, 1\) 」という並びに, \(3\) を追加する方法が \({} _ 4 \text{C} {} _ 1 = 4\) 通りあるので \[ 2 \cdot 4= 8 \ \text{通り} \ . \]5* \(S _ n = \{ 1, 1, 2, 3 \}\) のとき
4*と同様に考えて \[ 2 \cdot 4= 8 \ \text{通り} \ . \]6* \(S _ n = \{ 1, 2, 3, 3 \}\) のとき
「 \(1, 2\) 」という並びに, \(2\) つの \(3\) を追加する方法を考えればよいので \[ {} _ 3 \text{C} {} _ 1 + {} _ 3 \text{C} {} _ 2 = 6 \ \text{通り} \ . \]
上記以外の数字の組合せは条件を満たさない.
よって, 求める値は \[ f(4) = 81 -( 3+5+3+8+8+6 ) = \underline{48} \ . \]\(g(4)\) について
\(f(4)\) と同様に考える.1* \(S _ n = \{ 1, 1, 2, 3 \}\) のとき
「 \(1, 2, 3\) 」という並びに, \(1\) を追加する方法が \({} _ 4 \text{C} {} _ 1 = 4\) 通りあり, ただし \(( 1, 1, 2, 3 )\) が重複するので \[ 4 -1 = 3 \ \text{通り} \ . \]2* \(S _ n = \{ 1, 2, 2, 3 \}\) のとき
1*と同様に考えて \[ 4 -1 = 3 \ \text{通り} \ . \]3* \(S _ n = \{ 1, 2, 3, 3 \}\) のとき
1*と同様に考えて \[ 4 -1 = 3 \ \text{通り} \ . \]
上記以外の数字の組合せは条件を満たさない.
よって, 求める値は \[ g(4) = 81 -3 \cdot 3 = \underline{72} \ . \]
(2)
- 条件 \( \text{C} {} _ 1\) : \(x _ i = 1 \ ( 1 \leqq i \leqq n )\) を満たすものが少なくとも \(1\) つ存在する.
とおく.
\(\text{C} {} _ 1\) を満たさない \(S _ n\) の要素の個数を \(d(n)\) とおくと
\[
d(n) = 2^n \quad ... [1] \ .
\]
集合 \(S _ {n+1}\) の中で, 条件 \( \text{C} {} _ {12}\) を満たさないもののうち
\(x _ {n+1} = 2\) である要素は, \(S _ n\) が条件 \( \text{C} {} _ 1\) を満たしていない.
\(x _ {n+1} = 1 , 3\) である要素は, \(S _ n\) が条件 \( \text{C} {} _ {12}\) を満たしていない.
ゆえに, [1] も用いれば \[\begin{align} f(n+1) & = d(n) +2 f(n) \\ \text{∴} \quad \dfrac{f(n+1)}{2^{n+1}} & = \dfrac{1}{2} +\dfrac{f(n)}{2^n} \ . \end{align}\] 数列 \(\left\{ \dfrac{f(n)}{2^n} \right\}\) は, 初項 \(\dfrac{f(1)}{2} = \dfrac{3}{2}\) , 公差 \(\dfrac{1}{2}\) の等差数列なので \[\begin{align} \dfrac{f(n)}{2^n} & = \dfrac{3}{2} +\dfrac{n-1}{2} = \dfrac{n+2}{2} \\ \text{∴} \quad f(n) & = \underline{(n+2) 2^{n-1}} \ . \end{align}\]
(3)
(2) と同様に考えて, 集合 \(S _ {n+1}\) の中で, 条件 \( \text{C} {} _ {123}\) を満たさないもののうち
\(x _ {n+1} = 3\) である要素は, \(S _ n\) が条件 \( \text{C} {} _ {12}\) を満たしていない.
\(x _ {n+1} = 1 , 2\) である要素は, \(S _ n\) が条件 \( \text{C} {} _ {123}\) を満たしていない.
よって \[ g(n+1) = \underline{f(n) +2 g(n)} \ . \]
(4)
(2) の結果も用いて, (3) の結果を変形すると \[ \dfrac{g(n+1)}{2^{n+1}} = \dfrac{g(n)}{2^n} +\dfrac{n+2}{4} \ . \] したがって, 数列 \(\left\{ \dfrac{g(n)}{2^n} \right\}\) の階差数列を考えれば \[\begin{align} \dfrac{g(n)}{2^n} & = \dfrac{g(1)}{2} +\textstyle\sum\limits _ {k=1}^{n-1} \dfrac{k+2}{4} \\ & = \dfrac{3}{2} +\dfrac{1}{4} \left\{ \dfrac{n (n-1)}{2} +2 (n-1) \right\} \\ & = \dfrac{n^2 +3n +8}{8} \\ \text{∴} \quad g(n) & = \underline{\left( n^2 +3n +8 \right) 2^{n-3}} \ . \end{align}\]
【 別 解 】
(2)
条件 \( \text{C} {} _ {12}\) を満たす \(S _ n\) の要素の個数 \(\overline{f(n)}\) を考える.
\(S _ n\) のうち, 最も左にある（項番が小さい） \(1\) を \(a _ k = 1 \ ( 1 \leqq k \leqq n-1 )\) とする.
このとき
\(a _ 1 , \cdots , a _ {k-1}\) は, \(2 , 3\) のみで, \(2^{k-1}\) 通り. （ \(k = 1\) のときも満たす. ）
\(a _ {k+1} , \cdots , a _ n\) は, 少なくとも \(1\) つの \(2\) を含むので, \(3^{n-k} -2^{n-k}\) 通り.
したがって \[\begin{align} \overline{f(n)} & = \textstyle\sum\limits _ {k=1}^{n-1} 2^{k-1} \left( 3^{n-k} -2^{n-k} \right) \\ & = \textstyle\sum\limits _ {k=1}^{n-1} \left\{ 3^{n-1} \left( \dfrac{2}{3} \right)^{k-1} -2^{n-1} \right\} \\ & = 3^{n-1} \cdot \dfrac{1 -\left( \frac{2}{3} \right)^{n-1}}{1 -\frac{2}{3}} -(n-1) 2^{n-1} \\ & = 3^n -3 \cdot 2^{n-1} -(n-1) 2^{n-1} \\ & = 3^n -(n+2) 2^{n-1} \ . \end{align}\] よって \[ f(n) = 3^n -\overline{f(n)} = \underline{(n+2) 2^{n-1}} \ . \]
(4)
(2) と同様に, 条件 \( \text{C} {} _ {123}\) を満たす \(S _ n\) の要素の個数 \(\overline{g(n)}\) を考える.
\(S _ n\) のうち, 最も左にある \(1\) , これよりも右にある中で最も左にある \(2\) をそれぞれ \(a _ k = 1 , \ a _ {\ell} = 2 \ ( 1 \leqq k \lt \ell \leqq n-1 )\) とする.
このとき
\(a _ 1 , \cdots , a _ {k-1}\) は, \(2 , 3\) のみで, \(2^{k-1}\) 通り. （ \(k = 1\) のときも満たす. ）
\(a _ {k+1} , \cdots , a _ {\ell -1}\) は, \(1 , 3\) のみで, \(2^{\ell -k-1}\) 通り. （ \(\ell -k = 1\) のときも満たす. ）
\(a _ {\ell +1} , \cdots , a _ n\) は, 少なくとも \(1\) つの \(3\) を含むので, \(3^{n -\ell} -2^{n -\ell}\) 通り.
したがって \[\begin{align} \overline{g(n)} & = \textstyle\sum\limits _ {\ell = 2}^{n-1} \textstyle\sum\limits _ {k=1}^{\ell -1} 2^{k-1} \cdot 2^{\ell -k-1} \left( 3^{n -\ell} -2^{n -\ell} \right) \\ & = \textstyle\sum\limits _ {\ell = 2}^{n-1} ( \ell -1 ) 2^{\ell -2} \left( 3^{n -\ell} -2^{n -\ell} \right) \\ & = \textstyle\sum\limits _ {\ell = 1}^{n-2} \ell \cdot 2^{\ell -1} \left( 3^{n -\ell -1} -2^{n -\ell -1} \right) \\ & = \textstyle\sum\limits _ {\ell = 1}^{n-2} \left\{ 3^{n-2} \ell \left( \dfrac{2}{3} \right)^{\ell -1} -2^{n-2} \ell \right\} \\ & = 3^{n-2} \underline{\textstyle\sum\limits _ {\ell = 1}^{n-2} \ell \left( \dfrac{2}{3} \right)^{\ell -1}} _ {[2]} -2^{n-2} \cdot \dfrac{(n-1)(n-2)}{2} \ . \end{align}\] ここで, 下線部 [2] について \[\begin{align} [2] & = 1 \cdot 1 +2 \cdot \dfrac{2}{3} + \cdots +(n-2) \left( \dfrac{2}{3} \right)^{n-3} \quad ... [3] , \\ [2] \times \dfrac{2}{3} & = 1 \cdot \dfrac{2}{3} + \cdots +(n-3) \left( \dfrac{2}{3} \right)^{n-3} +(n-2) \left( \dfrac{2}{3} \right)^{n-2} \quad ... [4] \ . \end{align}\] \(( [3] -[4] ) \times 3\) より \[\begin{align} [2] & = 3 \left\{ 1 +\dfrac{2}{3} + \cdots +\left( \dfrac{2}{3} \right)^{n-3} -(n-2)\left( \dfrac{2}{3} \right)^{n-2} \right\} \\ & = 3 \cdot \dfrac{1 -\left( \frac{2}{3} \right)^{n-2}}{1 -\frac{2}{3}} -3 (n-2) \left( \dfrac{2}{3} \right)^{n-2} \\ & = 3^2 -3 (n+1) \left( \dfrac{2}{3} \right)^{n-2} \ . \end{align}\] ゆえに \[\begin{align} \overline{g(n)} & = 3^{n} -3 (n+1) 2^{n-2} -(n-1)(n-2) 2^{n-3} \\ & = 3^n -\left( n^2 +3n +8 \right) 2^{n-3} \ . \end{align}\] よって \[ g(n) = 3^n -\overline{g(n)} = \underline{\left( n^2 +3n +8 \right) 2^{n-3}} \ . \]