Pólya-Abzählung - Anwendungen mit mehreren Gewichtsfunktionen?

08/09/2011 - 22:23 von IV | Report spam
Hallo,

bei der Kombinatorischen Abzàhlung mit dem Pólyaschen
Abzàhlungstheorem wird die Symmetrie der zu verteilenden Figuren durch
eine Gewichtsfunktion beschrieben („Farbenpolynom“). Ist die
Erweiterung mit mehreren Gewichtsfunktionen irgendwo systematisch
behandelt, und welche Anwendungen dieser Erweiterung sind beschrieben
worden, z. B. auch für die Abzàhlung komplexerer Graphen-Invarianten
oder für Strukturen, die keine Graphen sind?
Ich habe im Moment nur die gleichzeitige Abzàhlung von Bàumen nach
Knotengrad und Höhe gefunden (Höhe des Baumes allgemein, Randic-Index
und Estrada-Index).

Danke.
 

Lesen sie die antworten

#1 Ivo Siekmann
15/09/2011 - 02:44 | Warnen spam
Hallo IV,
Ist die Erweiterung mit mehreren Gewichtsfunktionen irgendwo systematisch
behandelt, und welche Anwendungen dieser Erweiterung sind beschrieben
worden,[...]


Hierzu ein kurzes Beispiel aus Harary/Palmer (S. 46): Das Einfaerben
einer Halskette aus vier Perlen mit drei Farben - z.B. rot, blau, gelb
(siehe auch meinen frueheren Post zum Einfaerben einer "Halskette" aus
vier Perlen mit zwei Farben).

Das Zyklenpolynom fuer einen Graphen, der einen Ring aus vier Perlen
bildet, ist

=Z = s[1]^4/8 + 1/4 s[1]^2 s[2] + (3 s[2]^2)/8 + s[4]/4
(das Zyklenpolynom der Diedergruppe D_4).

Nun kann man entweder einfach 3 fuer alle s[i] einsetzen - damit erhaelt
man insgesamt 21 Moeglichkeiten. Wenn man es genauer wissen will, muss
man s[i] durch 1+x[i]^i+x[2]^i ersetzen, wobei der Exponent von x[1]
jeweils die Anzahl der roten, der Exponent von x[2] die Anzahl der
blauen angeben - der Rest ist einfach gelb.

Man berechnet einfach, z.B. mit Mathematica:
In[23]:= Z /. s[i_] -> 1 + x[1]^i + x[2]^i // Expand

Out[23]= 1 + x[1] + 2 x[1]^2 + x[1]^3 + x[1]^4 + x[2] + 2 x[1] x[2] +
2 x[1]^2 x[2] + x[1]^3 x[2] + 2 x[2]^2 + 2 x[1] x[2]^2 +
2 x[1]^2 x[2]^2 + x[2]^3 + x[1] x[2]^3 + x[2]^4

Setzt man jeweils eins fuer beide Variablen ein, erhaelt man die
Gesamtzahl (21 moeglichkeiten), alternativ kann man schon im
Zyklenpolynom Z direkt 3 (drei Farben) fuer alle s[i] einsetzen.

Gruesse
Ivo


Ohne Kombinatoriker zu sein, ist mein Eindruck, dass SYSTEMATIK gerade
die Crux bei Abzarhlproblemen mit Polya ist, siehe z.B. Storch/Wiebe,
Lehrbuch der Mathematik Band 2:
"Die Kunst bei der Anwendung von 9.A.17 [der Polyaschen Abzaehlformel]
besteht darin, die Menge der Farben und ihre Gewichte dem Problem
gemaess geschickt zu waehlen. Die groesste Schwierigkeit bereitet aber
in der Regel die Bestimmung des Zyklenpolynoms \psi(G)"

Also gleich DREI Schwierigkeiten:

Ähnliche fragen