平成21年度 春期 午前 問4

✓ これが正解イn(n+1)／2+1

解説

位置と長さの選び方を数え、空文字列を1つ足します。

部分文字列を数える手筋は、空でないものと空文字列に分けて扱うと見通しがつきます。空でない部分文字列は、切り出す先頭の位置と長さの組で一意に決まります。長さが 1 のものは、先頭を 1 文字目から n 文字目までずらせるので n 通り、長さが 2 のものは、末尾が外へはみ出さない範囲でずらして 1 つ縮んだ n−1 通り、と続き、最後は長さが n の 1 通りで終わります。等差の和として n から 1 までを足し合わせた形になり、その和は n(n+1)/2 という決まった式で書けます。ここに、問題文が仲間に含めている空文字列 1 つ分を足すと、部分文字列の総数の式が導けます。

ほかの選択肢はなぜ違うのか

• ア2ⁿ−1：2 のべきから 1 を引いた形を挙げています。長さ n の並びから選ぶ部分集合の総数から空集合を除いた式で、要素をとびとびに選ぶ場合の数え方に当たり、連続した部分列を切り出す数え方とは別物です。
• ウn(n−1)+1：n(n−1) に 1 を足した形を挙げています。順序を区別した 2 要素の並び方に空文字列を足した形に見えますが、先頭と長さの組み合わせを足し上げると得られる 1 から n までの和の値とは一致しません。
• エn!+1：n の階乗に 1 を足した形を挙げています。n 個のものを一列に並べる並べ方に空文字列を足した式で、連続した部分列の個数を数える問いに対する答えの形にはなりません。