\(n = \abs{S}\) とする. \(S\) の部分文字列の数は \(\homoprod{n}{2}\) である.

\(S\) の部分文字列のうち a が \(1\) つ以上含まれる数 \(c_a\) を考える. これは a を \(1\) つも含まない部分文字列の数を全体から引けばいい. よって, a の位置 (0-indexed) を \(a_1, a_2, \dots, a_{n_a}\) とすると,

\[c_a = \homoprod{n}{2} - \homoprod{a_1}{2} - \homoprod{a_2-a_1-1}{2} - \cdots - \homoprod{n-a_{n_a}}{2}\]

となる. これをすべての文字で計算する.

平均の種類数は \((\sum c_i) / \homoprod{n}{2}\) で求められる.