数理解析研究所講究録
第 1649 巻 2009 年 181-188

181

文字列の繰り返し構造の平均解析
草野一彦\dagger

松原渉\dagger

石野明\ddagger

篠原歩\dagger

2009 年 2 月 3 日
概要
文字列 $w$ の部分文字列 $w[i..j]$ において任意の $i\leq k\leq j-p$ で $w[k]=w[k+p]$ が成り立っとき, $w[i..j]$を周期 の繰り返し (repetition) と呼ぶ. . 連 (run, maximal repetition) とは左右に延長不可能な繰り返しである. 連の周期に対する長さの比-夢 を連の指数 (exponent) と呼ぶ 近年, 文字列に含まれる
$P$

$g$

連の個数や指数の和について盛んに研究が進められている. Crochemore と Ilie は長される連の指数の和の上界が 2. $9n$ であることを示した力$\nwarrow$$n$ の文字列に含まその最大値は未だ知られていない. 本稿では任意の長さ任意のアルファベットサイズの文字列に含まれる連の指数の和の平均を表す厳密な閉じた式を示し,
文字列の長さが無限大となるときの長さあたりの指数の和の極限値を示す. バイナリ文字列ではこの値はおよそ 113103 である. また, この結果を用いて文字列中のちょうど 2 回の繰り返しである平方の平均個数やその極限値を示す.

1

導入
文字列中の繰り返しはデータ圧縮や遺伝子解析などに応用される重要な問題のーつである.

平方とはちょうど 2 回の繰り返しである. 平方にはいくつかの数え方があるが. 本稿では素な根を持つ平方のみを考え, 平方の種類数ではなく出現数を数える. このように平方を数えた場合, 長さの文字列に含まれ$n$る平方の個数は $O(n\log n)$ であることが知られている [1].

連とは左右に延長不可能な繰り返しである. Kolpakov と Kucherov は長さ
個数 $\rho(n)$ が高々 $cn$ であることを示した [5]. 彼らは定数$n$の文字列に含まれる連の最大について具体的な値を与えなかったが, 近年この定数を下げるための精力的な研究が活発に行われている [2, 4, 9, 12]. 現在, $c\leq 1029$ であることが示されて
おり [3, 4], $c<1$ が予想されている. 連の繰り返し回数を指数 (exponent) と呼び, 指数の和の最大値についても良く研究されている [2, 6, 11]. 指数の和の最大値も長さに対して線形であることが示されている. 現在の最良の上界は 2. $9n$ であり [2], $2n$ 未満であると予想されている.
連の最大個数 $\rho(n)$ が未だ知られていないにも関わらず, Puglisi と Simpson は長さ の文字列に含まれる
$c$

$n$

連の平均個数を与える次の式を示した [10].
$r_{\sigma}(n)= \sum_{p=1}^{g}\sigma^{-2p-1}((n-2p+1)\sigma-(n-2p))\sum_{d|p}\mu(d)\sigma^{\S}$はアルファベットサイズ,

はメビウス関数である.
本稿ではアルファベットサイズ 長さ の文字列に含まれる指数の和の平均に注目し. 以下の等式が成り立つことを証明する.
ここで$\sigma$$\mu(n)$$\sigma$$n$$e_{\sigma}(n)$と平方の平均個数$s_{\sigma}(n)$号$e_{\sigma}(n)= \sum_{p=1}L_{\sigma}(p)(2p(n-2p+1)\sigma^{-2p}-(2p-1)(narrow 2p)\sigma^{-2p-1})$$vn$$s_{\sigma}(n)= \sum_{p=1}L_{\sigma}(p)(p(n-2p+1)\sigma^{-2p})$

ここで,$L_{\sigma}(n)$\dag er 東北大学$t$はアルファベットサイズ

大学院情報科学研究科
Google Japan Inc.

$\sigma$

長さ $n$ のリンドン文字列の個数を表す. さらに, それぞれの極限値

182が次のようになることを示す.
$\lim_{narrow\infty}\frac{e_{\sigma}(n)}{n}=\sum_{d=1}^{\infty}\mu(d)(\frac{2(\sigma-1)}{\sigma^{2d}-\sigma}+\frac{1}{d\sigma}\ln(\frac{\sigma^{2d}}{\sigma^{2d}-\sigma}))$$\lim_{narrow\infty}\frac{s_{\sigma}(n)}{n}=\sum_{d=1}^{\infty}\mu(d)(\frac{\sigma}{\sigma^{2d}-\sigma})$

2

定義
をサイズ

のアルファベットとする. すなわち,

である.

上の文字
列の集合を
と表し, 長さと書く. 文字列 $w=xyz$ について. $x,$ $y,$の全ての文字列ををそれ
ぞれ $w$ の接頭辞 (poefix), 部分文字列 (substring), 接尾辞 (suffix) と呼ぶ. 文字列 $w$ の長さを $|w|$ と表す. 長さの文字列を空文字列と呼ぴ で表す. 文字列 $w$ の 番目の文字を $w[i-1]$ と書く. すなわち,$w=w[0]w[1]\ldots w[|w|-1|$ である. 文字列 $w$ の部分文字列 $w[i]w[i+1]\ldots wU|$ を $w[i..j]$ と表す. 文字列 $w$
において任意の $i\geq 0$ で $w[i]=w[i+p]$ が成り立つ を文字列 $w$ の周期 (period) と呼ぶ.
文字列 $w$ がいかなる文字列と整数 $k\geq 2$ を用いても $w=u^{k}$ と書き表せないとき, 文字列 $w$ は素である (primitive) と言う. 文字列 $w$ が空文字列以外の $w$ の全ての接尾辞の中で辞書順最小であるとき, $w$ をリ
ンドン文字列 (Lyndon word) と呼ぶ [7]. 与えられたアルファベット上の長さ のリンドン文字列の個数をと定義する. 定義よりリンドン文字列は素であり, 長さ の素な文字列の個数は $nL_{\sigma}(n)$ となる. メビ
ウス (M\"obius) 関数 $\mu(n)$ は次のように定義される.
$\Sigma=\{0,1,2, \ldots, \sigma-1\}$$\Sigma^{*}$$\sigma$$|\Sigma|=\sigma$$\Sigma^{n}$

$n$

$0$

$\Sigma$$z$$i$$\epsilon$

$p$

$u$

$n$

$L_{\sigma}(n)$$n$$\mu(n)=\{\begin{array}{ll}0 n hc\Psi\hslash \ovalbox{\tt\small REJECT} \text{で} \delta J \text{りきれ・驀 1 n \text{が}fflg\text{なる}ff\Re ffl\text{の}\mathfrak{F}E\Re \text{をおっ}-1 n \text{が}fflg\text{なる} 5\Re ffl\text{の}aeEX \text{を} \#\text{っ}\end{array}$$L_{\sigma}(n)$は以下のように書き表せることが知られている 8].
$[$$L_{\sigma}(n)= \frac{1}{n}\sum_{d|n}\mu(\frac{n}{d})\sigma^{d}$$d|n$という表記は$d$

が $n$ の約数であることを示す. いくつかの $n$ についての $\mu(n)$ と $L_{2}(n)$ の値は次のようになる.

$\frac{n12345678910}{\mu(n)1-1-10-11-1001}$$L_{2}(n)$

1

2

2

3

9

6

18

30

56

99

文字列 $w$ が周期を持つ, すなわち 2 回以上の繰り返しであるとき, $w$ は周期 で周期的 (pereodic)であるという. 部分文字列 $w[i..j]$ が以下の条件を満たすとき $w[i..j]$ は周期 で左右に延長不可能 (nonextendable) であるという.
$p \leq\bigcup_{2}$

$P$

$P$

$i=0$

$j=n-1$$oror$$ww|_{j+1}^{iarrow 1}]_{\neq w}^{\neq w}|_{j-p+1]}^{i+p-1]}$の部分文字列 $w[i..j]$ が周期的であり左右に延長不可能であるとき, $w[i..j]$ を連 (run, maxemal repetition)と呼ぶ. 連は周期性と延長不可能性を満たす最小の周期 で 1 度のみ数える. 周期 の連 $w[i..j]$ を三項組

$w$

$P$

$(i.j,p)$ で表す.

連の根

$p$

$w[i..i+p-1]$ であり, 連の指数 ( 勾力 nent) は周期に対すに含まれる連の個数を Runs $(w)$ , 連の指数の和を $E\varphi(w)$ と定義する.

$(roo$ のは長さ $P$ の接頭辞

$e$

る長さの比
である. 文字列 $w$
部分文字列 が, 素な文字列 を用いて $v=u^{2}$ と書き表せるとき,を平方 (square) と呼ぶ. 平方の根はであり, 周期 (period) は$w$である. 文字列中の平方を二項組 $(i, |u|)$ で表す. ここで は$w$ 中でのの出現位置である. $w$ 中の平方の個数を $Sqr(w)$ と定義する.
$w=0101010110112120$ に含まれる連と平方を図 1 に例示する. $w[0..7]=01010101$ は周期 4 を持つ 2 回繰り返しであるが, 根 $w[0..3]=0101$ が素ではないため平方とはみなさない. また. $w[0..7]$ は周期 2 の連として 1 度のみ数える. 平方 0101, 1010, 11 は $w$ 中に複数回現われており本稿ではこれらを全て数える.
Runs $(w)=5,$$Sqrt(w)=10$ である.
$\frac{j-:+1}{p}$$v$$(\mathfrak{n})ot)$

$u$

$u$

$v$

$|u|$

$u^{2}$$Exp(w)= \frac{8}{2}+\frac{7}{3}+\frac{2}{1}+\frac{2}{1}+\frac{4}{2}=\frac{37}{3},$$u^{2}$

$i$

183

図1

$w=0101010110112120$ に含まれる連と平方.

3 結果
アルファベットサイズ

方の平均個数$s_{\sigma}(n)$$\sigma$

長さ $n$ の文字列に含まれる, 連の平均個数$r_{\sigma}(n)$をそれぞれ以下のように定義する.

, 連の指数の和の平均$e_{\sigma}(n)$, 平$r_{\sigma}(n)=average\{Runs(w):w\in\Sigma^{n}\}$$e_{\sigma}(n)=average\{Exp(w):w\in\Sigma^{n}\}$$s_{\sigma}(n)=average\{Sqr(w):w\in\Sigma^{n}\}$Puglisi と Simpson は連の平均個数について以下の等式が成り立つことを示した.
定理 1 (Puglisi and Simpson [10]).

$r_{\sigma}(n)= \sum_{p=1}^{n}\sigma^{n-2p-1}((n-2p+1)\sigma-(n-2p))\sum_{d|p}\mu(d)\sigma^{\S}\yen$

本稿では連の指数の和の平均と平方の平均個数について次の等式が成り立つことを証明する.
定理 2.
号$e_{\sigma}(n)= \sum_{p=1}L_{\sigma}(p)(2p(n-2p+1)\sigma^{-2p}-(2p-1)(n-2p)\sigma^{-2p-1})$

系 1.
号$s_{\sigma}(n)= \sum_{p=1}L_{\sigma}(p)(p(n-2p+1)\sigma^{-2p})$

アルファベットサイズ
定義する.

$\sigma$

長さ $n$ の文字列 $w$ と正数 $p$ について長さ $n-p$ の文字列 $d_{\sigma}(w,p)$ を以下のように$d_{\sigma}(w,p)[i]=w[i+p]-w[i]$$(mod \sigma)$

for $0\leq i<n-p$ここで演算子 ‘-, と ‘mod’ は文字を数字と見なして適用する. 例えば, $\Sigma=\{0,1,2\}$ 上の文字列 $w=21010$
について, $d_{\sigma}(w, 1)=2212$ であり $d_{\sigma}(w, 2)=100$ である.
文字列 $w\in\Sigma^{n}$ の部分文字列 $w[i..j]$ が の最大ブロックである, すなわち任意の $t(i\leq t\leq i)$ について
$w[t]=0$ が成り立ち以下の条件を満たすとき. $w[i..j]$ を 0-セグメントと呼ぶ.
$0$

$i=0$

$j=n-1$$oror$$w_{b}w|_{+1]\neq 0}^{i.-1]\neq 0}$

二項組 $(i,j)$ で 0-セグメント表す.

例 1. 文字列 0012000102 に含まれる 0-セグメントは $(0,1),$ $(4,6),$ $(8,8)$ である.

184

補題 1. 任意の文字列 $w$ について, $d_{\sigma}(w,p)$ [i..i] が長さ
り. 部分文字列 $w[i..j+p]$ は周期 の連である.

$P$

以上の 0-セグメントであるときかつその場合に限$P$

証明. 0-セグメント $(i,j)$ が $d_{\sigma}(w,p)$ に存在するとき, $w[t]=w[t+p](i\leq t\leq j)$ が成り立つ. すな
わち, $w[i..j+p]$ は周期 $p$ を持つ. $|d_{\sigma}(w,p)[i..j]|=jarrow i+1\geq P$ が成り立つときかつこの場合に限り$|w[i..j+p]|=j+p-i+1\geq 2p$ である. また, $w[i..j+p]$ は左右に延長不可能である. よって, $w[i..j+p]$は連である. $w[i..j+p]$ は周期 $p$ の連であるときに $d_{\sigma}(w,p)[i..j]$ が 0-セグメントであることは, 自明であ
る

口

なお,

この補題の中での周期 は最小であるとは限らない.
アルファベットサイズ 長さ $n$ の全ての文字列
中の長さ の 0-セグメントの個数を $c_{\sigma}(n,p)$ で,$C_{\sigma}(n,p)$の長さが 以上の O-セグメントの個数をで表す. 定義から, $C_{\sigma}(n,p)= \sum_{i=p}^{n}c_{\sigma}(n, i)$ である.
$P$$\Sigma^{n}$$\sigma$$\Sigma^{n}$

$P$

$p$

中の長さ

$p$

以上の 0-セグメントについて,の合計を$\frac{l}{p}$$E_{\sigma}(r\iota,p)$で表す. ここで,$l$中$\Sigma^{n}$は各 0-セグメント長さである. すなわち $E_{\sigma}(n,p)= \sum_{i=p}^{n}c_{\sigma}(n,i)\frac{i}{p}$ である.

例 2. $\sigma=2$ のとき
メントを下線で示す.

$c_{\sigma}(5,2)$

00000
00001
00010
00011
同様に,
なる.

は 12 である. 以下に長さ 5 の全てのバイナリ文字列に含まれる長さ 2 の 0-セグ

01000
01001
01010
01011

00100
00101
00110
00111

$c_{\sigma}(5,3)=5,$ $c_{\sigma}(5,4)=2$

であり,

01100
01101
01110
01111

$n$

10010
10011

10100
10101
10110
10111

である.

よって. $C_{\sigma}(5,2)=12+5+2+1=20$ と$c_{\sigma}(5,5)=1$$E_{\sigma}(5,2)=12 \cdot\frac{2}{2}+5\cdot\frac{3}{2}+2\cdot\frac{4}{2}+\frac{5}{2}=26$

補題 2. 任意の正数

10000
10001

11000
11001
11010
11011

11100

11101
11110
11111

である.

と $p\leq n$ について以下の式が成り立つ.
$C_{\sigma}(n,p)=(n-p+1)\sigma^{n-p}-(n-p)\sigma^{n-p-1}$$E_{\sigma}(n,p)= \frac{1}{p}(p(n-p+1)\sigma^{n-p}-(p-1)(n-p)\sigma^{n-p-1})$

証明. アルファベットサイズ$\sigma$

長さ$n$の文字列を長さ$P$の 0-セグメントで分割した文字列の組の集合$Q_{\sigma,n,p}$を次のように定義する.
$Q_{\sigma,n,p}=$

長さ

$P$

の 0-セグメントと{ $(u,w)|uvw\in\Sigma^{n}$ and$Q_{\sigma,n,p}$$\Sigma^{n}$に含まれる長さ$\Sigma^{3}=\{000,001,$$c_{\sigma}(3,1)$

は $uvw$ 中の O-セグメント}.

は一対一に対応するので $c_{\sigma}(n,p)=|Q_{\sigma,n,p}|$ である.

例 3. $\sigma=2,$ $n=3,$ $p=1$ について,

O-セグメントの個数$v$は 5 であり,$Q_{\sigma,3,1}$$\underline{0}1_{arrow}0,$$P$の 0-セグメントは以下のようになる.

$\underline{0}11,100,1\underline{0}1,11\underline{0},111\}$は次のようになる.

$Q_{\sigma,3,1}=\{(\epsilon, 10), (01,\epsilon), (\epsilon, 11), (1,1), (11, \epsilon)\}$$c_{\sigma}(n,p)$の表式は$Q_{\sigma,n,p}$に含まれる要素の個数を 2 つの場合について考えることで得られる.

(1) $p\leq n-1$
を 0-セグメントの位置によって次のように$Q_{\sigma,n,p}$$Q_{\sigma,n,p}^{l}$.

$Q_{\sigma,n,p}^{m},$$Q_{\sigma,n,p}^{l}=\{(u,w)\in Q_{\sigma,n,p}|u=\epsilon\}$$Q_{\sigma,n,p}^{m}=\{(u,w)\in Q_{\sigma,n,p}|u\neq\epsilon$,
and$Q_{\sigma,n_{2}p}^{r}=\{(u,w)\in Q_{\sigma_{j}n,p}|w=\epsilon\}$$u=\epsilon$

であるとき,$Q_{\sigma,n,p}^{r}$$w\neq\epsilon\}$の 3 つの集合に分ける.

,.

$|w|=n-p$ かつ $w[0]\neq 0$ であるから, $w[0]$ について $(\sigma-1)$ 通りの $w[1..n-p-1]$について $\sigma^{n-p-1}$ 通りの選び方がある.

よって,

1

$Q_{\sigma,n,p}^{l}|=(\sigma-1)\sigma^{n-p-1}$. 同様に,$w=\epsilon$

のとき

185

である.

$|Q_{\sigma,n,p}^{r}|=(\sigma-1)\sigma^{n-p-1}$$|u|+|w|=n-p$ である.

$0^{p}$

かつである場合, $u[|u|-1]$ と $w[0]$ は ではなく,の位置が $(n-p-1)$ 通りあり, $u[|u|-1]$ と $w[0]$ について $(\sigma-1)$ 通り,$u\neq\epsilon$$w\neq\epsilon$$0$

その他の文字について $\sigma^{n-p-2}$ 通りの選び方がある. すなわち $|Q_{\sigma,n,p}^{m}|=(n-p-1)(\sigma-1)^{2}\sigma^{n-p-2}$となる. $p=narrow 1$ のとき,
もしくは $w$ は であり, $(n-p-1)(\sigma-1)^{2}\sigma^{n-p-2}$ はとなる. ゆえに,$u$$0$$\epsilon$$c_{\sigma}(n,p)=|Q_{\sigma,np})|=|Q_{\sigma,n,p}^{l}|+|Q_{\sigma,n,p}^{m}|+|Q_{\sigma,n,p}^{r}|$$=(n-p+1)\sigma^{n-p}-2(n-p)\sigma^{n-p-1}+(n-p-1)\sigma^{n-p-2}$ .

(2) $p=n$$u=w=\epsilon$ であるから,$Q_{\sigma,n,p}=\{(\epsilon, \epsilon)\}$となり,$c_{\sigma}(n,p)=|Q_{\sigma n,p}\rangle|=1$である.

$P\leq n-1$ のとき,

$C_{\sigma}(n,p)= \sum_{i=p}^{n}c_{\sigma}(n, i)=(n-p+1)\sigma^{n-p}-(n-p)\sigma^{n-p-1}$.

この等式は $C_{\sigma}(n, n)=1$ についても成り立っ.
$P\leq n-1$ のとき,

$E_{\sigma}(n,p)= \sum_{i=p}^{n}c_{\sigma}(n, i)\frac{i}{p}=\frac{1}{p}(p(n-p+1)\sigma^{n-p}-(p-1)(n-p)\sigma^{narrow p-1})$.

この等式は $E_{\sigma}(n, n)=1$ についても成り立つ.

口

補題 3. $d_{\sigma}(w,p)=d_{\sigma}(v,p)$ を満たすような任意の整数$P$と長さ $n$ の文字列 $w$ と$v$$w[i..i+p-1]=v[i..i+p-1]$ が成り立つときその場合に限り $w=v$ である.
証明.
成り立つ.

$(\Rightarrow)$

数学的帰納法により示す. $i\leq j<i+p$ と$(\Leftarrow)$$i$でを整数とする. $k=0$ のとき $wb+kp$] $=vb+kp]$ がのとき, $w|;j+kp]=v[j+kp]$ が成り立つならば, $w\triangleright+(k+1)p]=wb+kp]+d_{\sigma}(w,p)\lfloor i+kp]$$k\geq 1$$k$$(mod \sigma)=v\triangleright+kp]+d_{\sigma}(v,p)b+kp](mod \sigma)=vb+(k+1)p]$ となる.

同様に,について, ある$w[0..i+p-1]=v[0..i+p-1]$ . ゆえに, $w=v$ .

よって, $w[i..n-1]=v[i..narrow 1]$ .

自明である

ロ

ついて $d_{\sigma}(w,p)$ の長さは $n-p$ であり,に含まれる 0-セグメントの個数は $C_{\sigma}(n-p,p)$ であ
補題 1 と 3 からには周期 の連が $\sigma^{p}C_{\sigma}(n-p,p)$ 含まれている. しかし, 連は複数の周期を持ちうる. 例えば, 0101010101 は 2 と 4 の両方の周期を持っている.
このような連を 2 回以上数えることを防ぐた$w\in\Sigma^{n}$$\Sigma^{n-p}$

る.

めに,

$\Sigma^{n}$$p$

連をその最小の周期で数えることを考える.

補題 4. 最小の周期が$p$である連の個数と周期$P$を持つ連の個数の比は$L^{L}\sigma^{p}\omega$である.

証明. 周期 を持つ連の個数は $\sigma^{p}C_{\sigma}(n-p,p)$ である. 周期性補題 [7] より, もし周期 を持つ連が異なる周期 $q<p$ を持つならば, その連は $gcd(p, q)$ も周期として持つ. つまり $w[i..j]$ が $q<p$ を周期として持たないならば, その根は素である. 長さ の素な文字列の個数はである. ゆえに, 最小の周期が である連の個数は $pL_{\sigma}(p)C_{\sigma}(n-p,p)$ である.
口
$P$

$P$

$P$

補題 1 より,の連の指数はに導かれる.

$d_{\sigma}(w,p)$$\frac{l}{p}+1$$pL_{\sigma}(p)$$P$

中の長さ $l(l\geq p)$ の 0-セグメントは $w$ 中の長さ $l+p$ の連に対応している. これら
このことと補題 2, 3, 4 からに含まれる連の指数の和は以下のようである.

$\Sigma^{n}$$\sigma^{n}e_{\sigma}(n)$を$\sigma^{n}e_{\sigma}(n)=\sum_{p=1}pL_{\sigma}(p)(E_{\sigma}(n-p,p)+C_{\sigma}(n-p,p))$$\tau n$$= \sum_{p=1}L_{\sigma}(p)(2p(n-2p+1)\sigma^{n-2p}-(2p-1)(n-2p)\sigma^{n-2p-1})$

186

図2

文字列中の連の指数の和の平均値$e_{\sigma}(n)$n(文字列中の長さあたりの連の指数の和の平均
値図 3–e.

$\sigma$

これより定理 2 が得られる. 図 2 より連の指数の和はが大きくなるにつれほぼ線形に増加するこの収束の様子を図 3 に示す.の極限について次の定理が成り立つ.
$e_{\sigma}(n)$とがわかる.

$\frac{e_{\sigma}(n)}{n}$$n$$e_{\sigma}(n)$定理 3. $narrow\infty$ となるときの$\frac{e_{\sigma}(n)}{n}$の極限は以下の値となる.

$\sum_{d=1}^{\infty}\mu(d)(\frac{2(\sigma-1)}{\sigma^{2d}-\sigma}+\frac{1}{d\sigma}\ln(\frac{\sigma^{2d}}{\sigma^{2d}-\sigma}))$

この定理を証明するために$\frac{e_{\sigma}(n)}{n}$を書き換える.

主張 1.
$\frac{e_{\sigma}(n)}{n}=\sum_{d=1}^{g}\mu(d)\sum_{p=1}^{n}\sigma^{-2pd+p-1}\pi(2(\sigma-1)-\frac{4pd}{n}(\sigma-1)+\frac{1}{pd}+\frac{2}{n}(\sigma-1))$

証明. $2p(n-2p+1)\sigma^{-2p}-(2p-1)(n-2p)\sigma^{-2p-1}$ を $f(p)$ と置く.
$e_{\sigma}(n)= \sum_{p=1}^{\}L_{\sigma}(p)f(p)$$\tau n$$= \sum_{p=1}\sum_{d|p}\mu(\frac{p}{d})\sigma^{d}\frac{f(p)}{p}$$= \mu(1)\sigma^{1}\frac{f(1)}{A3,A4ff_{2)}}+\mu(3)\sigma^{1}+\mu(1)\sigma^{3}\frac{f(3)}{3}+\mu(4)\sigma^{1}+\mu(2)\sigma^{2}+\mu(1)\sigma_{4}^{4\angle\zeta 4\lrcorner}+\mu(2)\sigma^{1}\frac+\mu(1)\sigma^{2}\frac{f(2)}{\omega_{4}42}$$I_{\mu}^{\mu}\{5)\sigma^{1}\frac{f\not\in)}{ff6),6}6$$+\mu(1)\sigma^{5\perp_{5}1_{+\mu(1)\sigma^{6}\frac{f(6)}{6}}}f5$:$= \sum_{d=1}^{\S}\mu(d)\sum_{p=1}^{\ } \sigma^{p}\frac{f(pd)}{pd}$( $\mu(d)$ を括り出した)$= \sum_{d=1}^{n}\mu(d)\sum_{p=1}^{i\S}\frac{1}{pd}v(2pd(n-2pd+1)\sigma^{-2pd+p}-(2pd-1)(n-2pd)\sigma^{-2pd+parrow 1})$$\frac{e_{\sigma}(n)}{n}=\sum_{d=1}^{\}\mu(d)\sum_{p=1}^{r^{n}a}\sigma^{-2pd+p-1}(2(\sigma-1)-\frac{4pd}{n}(\sigma-1)+\frac{1}{pd}+\frac{2}{n}(\sigma-1))$

口

187

定理 3 を証明する.
証明. (定理 3)
き無視できる.

$p_{\frac{d}{n}}$を考慮すべきときは $\sigma^{-2pd+p-1}$ が充分小さくなるため, 項$Tn$$\sigma_{n}^{-2pd+4}p-1_{-A_{-}^{d}}$は $narrow\infty$ のと$z^{n}a$$\lim_{narrow\infty}\frac{e_{\sigma}(n)}{n}=\lim_{narrow\infty}\sum_{d=1}\mu(d)\sum_{p=1}\sigma^{-2pd+p-1}(2(\sigma-1)+\frac{1}{pd})$$r\mathfrak{n}$$= \lim_{narrow\infty}\sum_{d=1}\mu(d)(\frac{2\sigma^{-2d}(\sigma-1)}{1-\sigma^{1-2d}}-\frac{1}{d\sigma}\ln(1-\sigma^{1-2d}))$$= \sum_{d=1}^{\infty}\mu(d)(\frac{2(\sigma-1)}{\sigma^{2d}-\sigma}+\frac{1}{d\sigma}\ln(\frac{\sigma^{2d}}{\sigma^{2d}arrow\sigma}))$口

平方の個数は連の個数と指数の和に関係しているため,
補題 5. 任意の文字列 $w$ と任意の文字列

.

$p$

にっいて,

$r_{\sigma}(n)$$w$

run $(w,p)$ 指数の和 $exp(w,p)$ は次の公式を満たす.

と$e_{\sigma}(n)$の式を用いて$s_{\sigma}(n)$を導ける.

中の周期 $p$ の平方の個数 $sqr(w,p)$ と連の個数$sqr(w,p)=pexp(w,p)-(2p-1)run(w,p)$
例 4. 文字列 001001101101100 に含まれる周期 3 の連は $(0,5,3)$ と 4, 13, 3) である. 連の個数は 2 であり, 指数の和は 13 である. この文字列に含まれる周期 3 の平方は $(0,3),$ $(4,3),$ $(5,3),$ $(6,3),$ $(7,3),$ $(8,3)$ である.
$($

証明. $w$ 中の連 $(i, j,p)$ について, 連の定義より $w[l]=w[l+p](i\leq l\leq j-p)$ であるから $w[k..k+p-1]=$$w[k+p..k+2p-1](i\leq k\leq j-2p+1)$ が成り立つ. 各 $w[k..k+p-1]$ は $w[i..i+p-1]$ と共役であり素である. 指数 $e= \frac{j-i+1}{p}$ の連は $j-i-2p+2$ 個の平方を含む. 平方は周期的なので周期 を持つ平方は必ず周
期 の連に含まれる. よって, 連 $(i,j,p)$ に含まれる平方の個数 について次の等式が成り立つ.
$P$

$p$

$s$

$s=j-i-2p+2=pe-(2p-1)$$w$

中の各連について両辺を足し合わせることで, 補題 5 が得られる.

口

Puglisi と Simpson の結果 [10] を我々の形に合わせて書き換えると以下のようになる.
$r_{\sigma}(n)= \sum_{p=1}^{n}L_{\sigma}(p)(p(n-2p+1)\sigma^{-2p}\tauarrow(n-2p)\sigma^{-2p-1})$

補題 5 を各文字列$w\in\Sigma^{n}$に適用することで系 1 を得る.

証明. (系 1)号$\sigma^{n}s_{\sigma}(n)=\sum_{p=1}(pL_{\sigma}(p)(2p(n-2p+1)\sigma^{n-2p}-(2p-1)(n-2p)\sigma^{n-2p-1})$$-(2p-1)L_{\sigma}(p)(p(n-2p+1)\sigma^{n-2p}-p(n-2p)\sigma^{n-2p-1}))$号$= \sum_{p=1}L_{\sigma}(p)(p(n-2p+1)\sigma^{n-2p})$号$s_{\sigma}(n)= \sum_{p=1}L_{\sigma}(p)(p(n-2p+1)\sigma^{-2p})$

口平方の平均個数が得られる$s_{\sigma}(n)$もまた $n$ が大きくなるにつれて線形に増加する.

$\frac{e_{\sigma}(n)}{n}$と同様にして$\frac{s_{\sigma}(n)}{n}$

の極限値

188

表1

$\frac{e_{\sigma}(n)}{n},$$\frac{r_{\sigma}\langle n)}{n},$$\frac{s_{\sigma}(n)}{n}$

の極限値.

系 2.
$\lim_{narrow\infty}\frac{s_{\sigma}(n)}{n}=\sum_{d=1}^{\infty}\mu(d)(\frac{\sigma}{\sigma^{2d}-\sigma})$

表1に

4$\frac{e_{\sigma}(n)}{n},$$\frac{r_{\sigma}(n)}{n},$$\frac{s_{\sigma}(n)}{n}$の極限値を示す.

結論

本稿では上界が未解決問題であるにも関わらず, 文字列中の連の指数の和の平均および平方の平均個数を厳密に求めた. これは, 1 つの文字列の中で連がどのように組み合うかはわからないものの, 全ての文字列に含まれるある周期を持つ連の個数やその中で根が素であるものの割合が計算できるためである. さらに本稿では文字列長が無限大に近づ ときの長さあたりのこれらの値の極限値を与えた. 無限長のバイナリアルファベッ
トでは, 長さあたりの指数の和の平均はおよそ 1.13103 であり, 平方の平均個数はおよそ 0.82330 である.
$\langle$

参考文献[1] M. Crochemore. An optimal algorithm for computing the repetitions in a word. Information Processing Letters, $12:2u-250$ , 1981.
[2] M. Crochemore and L. Ilie. Analysis of Maximal Repetitions in Strings. In Proc. $S2nd$ Intemational
Symposium on Mathematical Foundations of Computer Science (MFCS 2007), volume 4708 of LNCS,
pages, 2007.
[3] M. Crochemore, L. Ilie, and L. Tinta. The “runs” conjecture.
http: $//www$ . csd. uwo. $ca/\sim ilie/ruris$ . html.
[4] M. Crochemore, L. Ilie, and L. Tinta. Towards a solution to the “runs” conjecture. In Proceedingsof the 19th Annual Symposium on Combinatorial Pattem Matching $(CPM$ 2008 , volume 5029 of
LNCS, pages $2\Re\vdash 302$ , 2008.
[5] R. Kolpakov and G. Kucherov. Finding Maximal Repetitions in a Word in Linear Time. In Proc.
40th Annual Symposium on Foundations of Computer Science (FOCS 1999), pages 596-604, 1999.
[6] R. Kolpakov and G. Kucherov. On the sum of exponents of maximal repetitions in a word. Technical
Report 99-R-034, LORIA, France, 1999.
[7] M. Lothaire. Algebraic combinatorics on words. Cambridge University Press New York, 2002.
[8] M. Lothaire. Applied Combinatoncs on Words. Cambridge University Press New York, 2005.
[9] S. Puglisi, J. Simpson, and W. Smyth. How many runs can a string contain? Theoretical Computer
Science, 401 (1-3): 165-171, 2008.
[10] S. J. Puglisi and J. Simpson. The expected number of runs in a word. Australasian Joumal of$465\triangleleft 76$$)$

Combinatori $cs,$ $42:45-54$ , 2008.

[11] W. Rytter. The number of runs in a string: Improved analysis of the linear upper bound. In Proc.
$2Srd$ Annual Symposium on tZ7ieoretical Aspectsof Computer Science (STACS 2006), volume 3884
of LNCS, pages 184-195, 2006.
[12] W. Rytter. The number of runs in a string. Infomation and Computation, $205(9):1459-1469$ , 2007.