1から8を並べる。「左よりも右が小さい」は1ヶ所だけ /「算数にチャレンジ!!」第1081問

問題概略
グループ分けして数える
各グループの最大値，最小値から数える
漸化式を作る

問題概略

次の条件をみたす 8 ケタの整数は何個あるでしょうか。

1 ～ 8 までの数字を 1 回ずつ使う。

2 つの連続したケタを選んだとき，ある。

http://www.sansu.org/used-html/index1081.html

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

グループ分けして数える

まず 1～8 を空でない 2 つのグループ $L$ , $R$ に分けます。
この分け方は $2^8-2=254$ 通り。

次に $L$ , $R$ 内の数を小さいものから順に並べて $L_{\max}=a$ , $R_{\min}=b$ とします。

$a>b$ をみたすものを数えるより，余事象の方が数えやすいです。
$a>b$ をみたす $(a,\,b)$ が存在しないのは， $L$ が 1 から $a$ までの連続する数からなっているときです。
このような分け方は $L=\left\{1,\, 2\right\}$ から $L=\left\{1,\, 2,\, \cdots,\, 8\right\}$ までの 7 通り。

求める個数は $254-7$ の「247 通り」です。

各グループの最大値，最小値から数える

$a>b$ をみたす $(a,\,b)$ を選んでから $L$ , $R$ を作ることもできます。

1 ～ $a-1$ のうち 1 ～ $b-1$ は $L$ に入る
$b$ は $R$ に入る
$b+1$ ～ $a-1$ の $a-b-1$ 個は $L$ , $R$ のどちらに入ってもいい

この場合の $L$ , $R$ の作り方は $2^{a-b-1}$ 通りです。求める個数は次のようにして求められます。
\begin{align*}
\sum_{1\leqq b< a\leqq 8} 2^{a-b-1}=\sum_{a=2}^8 \sum_{b=1}^{a-1} 2^{a-b-1}=247
\end{align*}

漸化式を作る

$n$ 文字の場合の個数を $f(n)$ とおきます。 $f(1)=0$ , $f(2)=1$ は明らか。

条件をみたす $n$ 文字の列から条件をみたす $n+1$ 文字の列を作る方法は 2 通りあります。

「 $a$ , $b$ 」の部分を「 $a$ , $n+1$ , $b$ 」に変える（＝ $L$ の右端に $n+1$ をおく）
$R$ の右端に $n+1$ をおく

このようにしてできる $n+1$ 文字の列は $2f(n)$ 個。

他に $n$ : 文字の時点では条件をみたしていない列から条件をみたす $n+1$ 文字の列を作る方法もあります。
1 ～ $n$ を小さい方から並べた列に対して，図の $\wedge$ のどこかに $n+1$ をおきます。
\begin{align*}
\wedge 1 \wedge 2 \wedge \cdots \wedge n
\end{align*}