考える問題

大きさ（長さ）$N$の文字列の部分文字列の数は？（ただし，空文字列を含まない．）

連続した文字列であることに注意してね

結論

部分文字列の数は，

\frac{N (N+1)}{2}

となります．

考え方

ポイント

部分文字列を一つに決めるためには，その部分文字列の最左端の位置と最右端の位置を決めればいいです．

ここで注意したいのは，最左端と最右端の位置は重複してもいいということです．理由は，部分文字列の大きさが1の場合を考えればおわかりいただけると思います．

つまり，

(部分文字列の選び方)=(重複を許してN個から2個選ぶ場合の数)

となります．

重複組合せ

では，「重複を許して$N$個から2個選ぶ場合の数」はどのように表されるでしょうか？このような問題は重複組合せとよばれます．重複組合せの考え方は2つあります．

考え方1（公式を使う）

$n$個から重複を許して$r$個選ぶ組み合わせの数を${}_n \mathrm{H}_r$と表すと，以下の公式が成り立ちます．

{}_n \mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r

この公式において　$n=N, r=2$とすれば，

{}_N \mathrm{H}_2 = {}_{N+2-1}\mathrm{C}_2 = \frac{N(N+1)}{2}

となります．

考え方２（原理的に考える）

重複組合せの原理は，仕切りの考え方を用いることで説明できます．今回のような問題においては，部分文字列の選び方の数は，「2つの仕切りを異なる文字列間（両端含む）に入れる場合の数」に一致します．仕切りをいれる位置は以下の図に示すとおりです．

部分文字列を仕切りに挟まれた部分の文字列と考えれば，部分文字列と仕切りの選び方が1対1に対応します．

仕切りをいれることのできる位置の場合の数は，文字列の大きさ$N$を用いて，$N+1$と表せます（図の例で言うと，文字列数8に対して，仕切りをいれることのできる場所の数は8+1=9箇所となります）．

よって，仕切りの選び方の場合の数は，$N+1$個の箇所から，重複をせずに2箇所選ぶ組み合わせの数となるので，

{}_{N+1}\mathrm{C}_2 = \frac{N(N+1)}{2}

となります．したがって，大きさ$N$の文字列の部分文字列の数が$\frac{N (N+1)}{2}$となることが導けました．

ここで重要なのは「重複組合せ問題から重複を排除し，単純な組み合わせ問題に帰着させた」という点です．考え方1の公式と本質的な考え方は同じです．考え方2では$n=N, r=2$の場合においてのみ，原理的に考えるという方法を用いましたが，任意の$n, r$において同様の考え方が可能です．