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 the O’Reilly learning platform.

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