i
i
main”—2013/4/10—15:19—page161—#173
i
i
i
i
i
i
Der Satz von Fine und Wilf 161
Der folgende Satz von Roger Conant Lyndon (1917–1988) und Marcel-Paul Schüt-
zenberger (1920–1996) ist grundlegend für die Kombinatorik auf Wörtern. Er be-
schreibt die Struktur von konjugierten Wörtern. Im zweiten Teil des Satzes geht es
um mit e inander kommutierende Wörter.
Satz 6.3 (Lyndon, Schützenberger 1962). Seien
x,y,z Σ
rter .
(a) Wenn
x ε und zx = yz gilt, dann existieren r,s Σ
und k N mit x = sr,
y = rs und z = (r s)
k
r . Insbesondere stimmt die Konjugation mit der Transposi-
tion überein; und beides sind Äquivalenzrelationen.
(b) Wenn
xy = yx gilt, dann sind x und y beide Potenzen eines Wortes r Σ
.
Beweis. Zu (a): Wenn
|z|≤|x| gilt, dann ist z ein Suffix von x, also existiert entspre-
chend dem folgenden Bild ein Wort
s mit x = sz und y = zs. Die Aussage gilt nun
mit
z = r und k = 0.
z x
z
y
s
Sei nun |z| > |x|. Dann ergibt sich das folgende Bild:
y
z
xz
z
Also ist z = z
x = yz
und |z
| < |z|,dax ε. Mit Induktion nach |z| existieren
nun
r,s Σ
und k
N mit x = sr, y = rs und z
= (r s)
k
r . Die Aussage gilt
also mit
k = k
+ 1.
Zu (b): Wenn
x = ε gilt, dann ist die Aussage mit r = y erfüllt. Andernfalls
können wir aus Symmetriegründen annehmen, dass
x und y beide nicht leer sind.
Mit Teil (a) erhalten wir
x = st = ts und y = (st)
k
s. Mit Induktion nach |xy|sind s
und t Potenzen desselben Wortes r . Das gleiche trifft damit auch auf x und y zu.
6.2 Der Satz von Fine und Wilf
Offensichtlich gilt in Satz 6.3 (b) a uch die Umkehrung: Wenn u und v Potenzen des-
selben Wortes sind, dann ist
uv = vu. Der folgende Satz von Nathan Jacob Fine
(1916–1994) und Herbert Saul Wilf (1931–2012) gibt eine andere hinreichende Bedin-
g ung r Kommutativität: Wenn
u
m
und v
n
einen genügend langen Präfix gemein-
i
i
main”—2013/4/10—15:19—page162—#174
i
i
i
i
i
i
162 Kombinatorik auf Wörtern
sam haben, dann kommutieren u und v. Um eine komfortablere Induktionsvoraus-
setzung zu erhalten, zeigen wir eine etwas stärkere Aussage. Der hier vorgestellte Be-
weis stammt von Jeffrey Outlaw Shallit (geb. 1957).
Satz 6.4. Seien
u, v Σ
nichtleere Wörter, s u{u, v}
und t v{u, v}
.Wenn
s und t einen gemeinsamen Präfix der Länge |u|+|v|−ggT(|u|, |v|) haben, dann
gilt
uv = vu.
Beweis. Ohne Einschränkung gilt
|u|≤|v|. Die Aussage ist trivial für |u|=0,also
gilt
1 ≤|u|≤|v|. Weg en ggT(|u|, |v|) ≤|v| folgt v = uw.Zuzeigenistuw =
wu
,dennhierausfolgtuv = u(uw) = u(wu) = (uw)u = vu. Die Aussage
uw = wu ist trivial für |w|=0. Wegen |s|≥|u|+|v|−ggT(|u|, |v|)>|u|
gilt s uu{u, w}
. Zusammen mit t uw{u, w}
folgt s
u{u, w}
und
t
w{u, w}
für die Wörter s
,t
mit s = us
und t = ut
.EsgiltggT(|u|, |v|) =
ggT(|u|, |w|)
und |v|=|u|+|w|,alsohabens
und t
einen gemeinsamen Präfix
der Länge
|u|+|w|−ggT(|u|, |w|). Mit Induktion folgt uw = wu und damit die
Behauptung.
Für alle positi ven ganzen Zahlen p,q definieren wir das Wortpaar σ(p,q)
{a, b}
×{a, b}
induktiv wie folgt:
σ(p,q) =
(a
p
,a
p1
b) falls p = q
(v, u)
falls p>qund σ(q,p) = (u, v)
(u, uv)
falls p<qund σ(p,qp) = (u, v)
Das Wortpaar (u, v) = σ(p,q) hat die Eigenschaften |u|=p, |v|=q, uv vu
und die Wörter u und v stimmenaufdenerstenp + q ggT(p, q) 1 Zeichen
überein. Deshalb ist die Schranke
|u|+|v|−ggT(|u|, |v|) im Satz von Fine und
Wilf bestmöglich.
Eine natürliche Zahl
p 1 ist eine Periode des Wortes a
1
···a
n
mit a
i
Σ,
wenn
a
i
= a
i+p
für alle 1 i n p gilt. Beispielsweise hat das Wort aabaaba
die Perioden 3, 6 und 7. Die Länge |u| ist stets eine Periode eines nichtleeren Wortes
u. Der Satz von Fine und Wilf wird häufig in der Form von Korollar 6.5 formuliert:
Wenn ein genügend langes Wort
w zwei Perioden besitzt, dann ist auch deren größte r
gemeinsamer Teiler eine Periode von
w.
Korollar 6.5 (Fine, Wilf 1965). Wenn ein Wort
w mit |w|≥p + q ggT(p, q) zwei
Perioden
p und q besitzt, dann ist auch ggT(p, q) eine Periode von w.
Beweis. Sei
w sowohl ein Präfix von s = u
k
als auch von t = v
mit |u|=p und
|v|=q. Mit Satz 6.4 gilt uv = vu. Nach Satz 6.3 (b) sind u und v beides Potenzen
eines Wortes
x. Damit ist auch s eine Potenz von x,und|x| sowie jedes Vielfache
sind Perioden von
w.DieLängevonx te ilt sowohl p als auch q. Damit ist |x| auch
ein Teiler von
ggT(p, q).

Get Diskrete algebraische Methoden now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.