Im Rahmen des hier geplanten Forschungsvorhabens sollten verschiedene
Untersuchungen aus der Dissertation
[7][6]
von Herrn Dr. H. Fripertinger fortgesetzt werden. Es
handelt sich dabei um folgende Problemstellungen:
- Weitere Verallgemeinerung und theoretische Untersuchungen von
verschiedenen Abzähltheoremen.
- Implementation auf Computern (PC oder WS) von Ergebnissen der
Abzähltheorie und von Repräsentantenkonstruktionen in ein
mathematisches Programmpaket.
- Weitere Anwendung bei konkreten Konstruktionsaufgaben und
Anzahlbestimmungen (insbesondere in der Mathematischen Musiktheorie).
Diese neuen Fragestellungen sind zum Teil auf natürliche Weise aus der
Dissertation hervorgegangen, zum anderen aber auch in Diskussionen mit Herrn
Prof. Dr. A. Kerber (Universität Bayreuth) und Herrn Dr. habil.
G. Mazzola (ETH Zürich) angeregt worden.
Zusammenfassend kann man die Aufgaben als
konstruktive Aspekte endlicher Strukturen
bezeichnen.
Einführend soll nun anhand eines trivialen Beispiels -- der Färbung der
Seitenflächen eines Würfels -- eine grundlegende Methode, die Abzähltheorie
von Pólya [22][23],
vorgestellt werden:
Es sei ein Würfel gegeben, dessen
Seitenflächen rot oder blau gefärbt sein sollen. Zwei Würfel werden als
wesentlich verschieden bezeichnet, falls man den einen Würfel nicht durch
beliebige Drehung in den anderen überführen kann.
Es können Fälle auftreten, daß zwei Würfel verschieden gefärbt
sind, wenn jedoch einer von ihnen gedreht wird, sie gleich aussehen.
Wieviele wesentlich verschiedene Würfelfärbungen
gibt es? Diese Fragestellung kann noch ohne Verwendung der mathematischen
Theorie gelöst werden. Man erhält dabei die folgende Aufstellung wesentlich
verschiedener Färbungen. In Klammern wird jeweils die Anzahl der
verschiedenen Färbungen angegeben, die man durch Rotation des Würfels
erhält:
- Alle Seitenflächen sind rot. (1)
- Fünf Seitenflächen sind rot, eine Seite ist blau. (6)
- Zwei gegenüberliegende Seitenflächen sind blau, der Rest ist rot. (3)
- Zwei aneinanderstoßende Seitenflächen sind blau, der Rest ist rot. (12)
- Drei Seitenflächen um eine Ecke sind rot, die restlichen sind blau. (8)
- Zwei gegenüberliegende Seitenflächen und eine weitere sind rot, der
Rest ist blau. (12)
- Analog zu 4., jedoch sind rot und blau zu vertauschen. (12)
- Analog zu 3., jedoch sind rot und blau zu vertauschen. (3)
- Analog zu 2., jedoch sind rot und blau zu vertauschen. (6)
- Analog zu 1., jedoch sind rot und blau zu vertauschen. (1)
Will man dies nun mathematisch nachvollziehen, so entspricht jeder Färbung
des Würfels eine Abbildung f der Form
f:{1,2,...,6} -> {r,b} ,
wobei die 6 Seitenflächen des Würfels mit den Nummern 1,2,...,6
durchnumeriert sind, und {r,b} die Menge der 2 Farben "rot" und
"blau" darstellt. Die Rotationen des Würfels bilden eine Gruppe, die
Oktaedergruppe W, deren Operation auf den Würfelflächen im
Zyklenzeiger Z(W(F)) zusammengefaßt wird.
Z(W(F);x1,x2,...
,x6)=(1)/(24)(x16+3x12x22+6x12 x4+6x23+8x32).
Um die Anzahl der wesentlich verschiedenen Färbungen zu bestimmen, muß man
nach dem Hauptsatz von Pólya im Zyklenzeiger Z(W(F)) für
xi den Ausdruck |{r,b} |=2 substituieren. Dies liefert nun:
Z(W(F);2,2,...,2)=10.
Interessiert man sich auch für die genauere Gestalt dieser wesentlich
verschiedenen Färbungen, so seien nun r und b als Unbestimmte über Q
aufgefaßt, dann enthält
Z(W(F);r+b,r2+b2,...,r6+b6)=
r6+r5b+2r4b2+2r3b3+2r2b4+rb5+b6
die gewünschte Information.
Nicht mehr so trivial ist es, die 2226 wesentlich verschiedenen Färbungen
eines Würfels mit 6 Farben f1,f2,...,f6
aus allen möglichen 66= 46656 Färbungen zu bestimmen. Diese
werden im folgenden beschrieben:
Z(f1+f2+f3+f4+f5+f6,f12+f22+f32+f42+f52+f62,f13+f23+f33+f43+f53+f6
3,f14+f24+f34+f44+f54+f64,f15+f25+f35+f45+f55+f65,f16+f26+f36+f
46+f56+f66)=
f16+f15 (f2+f3+f4+f5+f6)+2 f14 (f22+f2 (f3+f4+f5+f6)+f32+f3 (f4+f5+f6)+f4
2+f4 (f5+f6)+f52+f5 f6+f62)+f13 (2 f23+3 f22 (f3+f4+f5+f6)+f2 (3 f32+5
f3 (f4+f5+f6)+3 f42+5 f4 (f5+f6)+3 f52+5 f5 f6+3 f62)+2 f33+3 f32 (f4+f5+
f6)+f3 (3 f42+5 f4 (f5+f6)+3 f52+5 f5 f6+3 f62)+2 f43+3 f42 (f5+f6)+f4 (3
f52+5 f5 f6+3 f62)+2 f53+3 f52 f6+3 f5 f62+2 f63)+f12 (2 f24+3 f23 (
f3+f4+f5+f6)+2 f22 (3 f32+4 f3 (f4+f5+f6)+3 f42+4 f4 (f5+f6)+3 f52+4 f5 f6
+3 f62)+f2 (3 f33+8 f32 (f4+f5+f6)+f3 (8 f42+15 f4 (f5+f6)+8 f52+15 f5 f6
+8 f62)+(f4+f5+f6) (3 f42+5 f4 (f5+f6)+3 f52+5 f5 f6+3 f62))+2 f34+3 f33
(f4+f5+f6)+2 f32 (3 f42+4 f4 (f5+f6)+3 f52+4 f5 f6+3 f62)+f3 (f4+f5+f6) (
3 f42+5 f4 (f5+f6)+3 f52+5 f5 f6+3 f62)+2 f44+3 f43 (f5+f6)+2 f42 (3 f5
2+4 f5 f6+3 f62)+f4 (f5+f6) (3 f52+5 f5 f6+3 f62)+2 f54+3 f53 f6+6 f52 f
62+3 f5 f63+2 f64)+f1 (f25+2 f24 (f3+f4+f5+f6)+f23 (3 f32+5 f3 (f4+f5+f
6)+3 f42+5 f4 (f5+f6)+3 f52+5 f5 f6+3 f62)+f22 (3 f33+8 f32 (f4+f5+f6)+f
3 (8 f42+15 f4 (f5+f6)+8 f52+15 f5 f6+8 f62)+(f4+f5+f6) (3 f42+5 f4 (f5+f6
)+3 f52+5 f5 f6+3 f62))+f2 (2 f34+5 f33 (f4+f5+f6)+f32 (8 f42+15 f4 (f5+
f6)+8 f52+15 f5 f6+8 f62)+5 f3 (f4+f5+f6)3+2 f44+5 f43 (f5+f6)+f42 (8 f5
2+15 f5 f6+8 f62)+5 f4 (f5+f6)3+2 f54+5 f53 f6+8 f52 f62+5 f5 f63+2 f6
4)+f35+2 f34 (f4+f5+f6)+f33 (3 f42+5 f4 (f5+f6)+3 f52+5 f5 f6+3 f62)+f3
2 (f4+f5+f6) (3 f42+5 f4 (f5+f6)+3 f52+5 f5 f6+3 f62)+f3 (2 f44+5 f43 (f
5+f6)+f42 (8 f52+15 f5 f6+8 f62)+5 f4 (f5+f6)3+2 f54+5 f53 f6+8 f52 f6
2+5 f5 f63+2 f64)+(f4+f5+f6) (f44+f43 (f5+f6)+f42 (2 f52+3 f5 f6+2 f62)
+f4 (f5+f6)3+f54+f53 f6+2 f52 f62+f5 f63+f64))+f26+f25 (f3+f4+f5+f6)+
2 f24 (f32+f3 (f4+f5+f6)+f42+f4 (f5+f6)+f52+f5 f6+f62)+f23 (2 f33+3 f3
2 (f4+f5+f6)+f3 (3 f42+5 f4 (f5+f6)+3 f52+5 f5 f6+3 f62)+2 f43+3 f42 (f5+
f6)+f4 (3 f52+5 f5 f6+3 f62)+2 f53+3 f52 f6+3 f5 f62+2 f63)+f22 (2 f34
+3 f33 (f4+f5+f6)+2 f32 (3 f42+4 f4 (f5+f6)+3 f52+4 f5 f6+3 f62)+f3 (f4+f
5+f6) (3 f42+5 f4 (f5+f6)+3 f52+5 f5 f6+3 f62)+2 f44+3 f43 (f5+f6)+2 f42
(3 f52+4 f5 f6+3 f62)+f4 (f5+f6) (3 f52+5 f5 f6+3 f62)+2 f54+3 f53 f6+6
f52 f62+3 f5 f63+2 f64)+f2 (f35+2 f34 (f4+f5+f6)+f33 (3 f42+5 f4 (f5+
f6)+3 f52+5 f5 f6+3 f62)+f32 (f4+f5+f6) (3 f42+5 f4 (f5+f6)+3 f52+5 f5 f6
+3 f62)+f3 (2 f44+5 f43 (f5+f6)+f42 (8 f52+15 f5 f6+8 f62)+5 f4 (f5+f6)
3+2 f54+5 f53 f6+8 f52 f62+5 f5 f63+2 f64)+(f4+f5+f6) (f44+f43 (f5+f6)
+f42 (2 f52+3 f5 f6+2 f62)+f4 (f5+f6)3+f54+f53 f6+2 f52 f62+f5 f63+f6
4))+f36+f35 (f4+f5+f6)+2 f34 (f42+f4 (f5+f6)+f52+f5 f6+f62)+f33 (2 f4
3+3 f42 (f5+f6)+f4 (3 f52+5 f5 f6+3 f62)+2 f53+3 f52 f6+3 f5 f62+2 f63)
+f32 (2 f44+3 f43 (f5+f6)+2 f42 (3 f52+4 f5 f6+3 f62)+f4 (f5+f6) (3 f52
+5 f5 f6+3 f62)+2 f54+3 f53 f6+6 f52 f62+3 f5 f63+2 f64)+f3 (f4+f5+f6)
(f44+f43 (f5+f6)+f42 (2 f52+3 f5 f6+2 f62)+f4 (f5+f6)3+f54+f53 f6+2 f5
2 f62+f5 f63+f64)+f46+f45 (f5+f6)+2 f44 (f52+f5 f6+f62)+f43 (2 f53+
3 f52 f6+3 f5 f62+2 f63)+f42 (2 f54+3 f53 f6+6 f52 f62+3 f5 f63+2 f6
4)+f4 (f5+f6) (f54+f53 f6+2 f52 f62+f5 f63+f64)+f56+f55 f6+2 f54 f62
+2 f53 f63+2 f52 f64+f5 f65+f66.
Nun aber zurück zur Situation mit 2 Farben.
Es könnte Situationen geben, daß zwei wesentlich verschiedene Färbungen als
gleich angesehen werden, falls man die eine durch Vertauschen der Farben aus
der anderen erhält. Dieses Problem löst ein Satz von N.G. de Bruijn
(siehe [4]), der angewendet auf dieses Beispiel folgende Formel liefert:
Z.(W(F);(¶)/(¶x1),(¶)/(¶
x2),...,(¶)/(¶
x6))Z(S2;es1,es2) | x1=x2=...=x6=0,
wobei sj:=xj+x2j+....
Diese Formel liefert als Ergebnis, daß es 6 wesentlich verschiedene Färbungen
gibt. Eine andere Formel von N.G. de Bruijn [4] erlaubt die Anzahl der
wesentlich verschiedenen Färbungen zu berechnen, die bei Vertauschung der zwei Farben
rot und blau nicht verändert werden. Diese Anzahl errechnet man als
Z(W(F);0,2,0,2,0,2)=2.
Die hier und im folgenden dargestellte Theorie erlaubt verschiedenste
Anwendungen: Bereits Pólya widmete in seiner berühmten Arbeit [22]
den Anwendungen in der Graphentheorie (als mathematische Anwendung) und in
der Chemie (zur Bestimmung der maximalen Anzahl von Isomeren und ähnlichen
Berechnungen) große Abschnitte. Auf diesen Gebieten erschien seitdem eine
wahre Flut von Publikationen. Es gibt z.B. auch Anwendungen dieser Theorie
zur Klassifikation von Schaltfunktionen und Boolschen Funktionen
[28][11].
Herr Kerber befaßte sich mit Anwendungen in der Begriffsanalyse [17]
und plant eine Publikation mit Anwendungen in der Physik (bei Bestimmung von
Kristallstrukturen oder Spin-Konfigurationen). Abschließend sei noch auf Anwendungen
in der Musiktheorie
[26][10][9][8],
bei
Telekommunikations-Netzwerken [2] in der Zahlentheorie [3] oder beim
Abzählen von Lateinischen Quadraten [15] hingewiesen.
Im folgenden Abschnitt sollen nun der Stand der Forschung und die
Problemstellung genau dargelegt werden.
harald.fripertinger@kfunigraz.ac.at,
last changed: January 28, 2002