Θεώρημα Απαρίθμησης του Πόλια (Pólya Enumeration Theorem)

Το Θεώρημα Απαρίθμησης του Πόλια αποτελεί σημαντική γενίκευση του Λήμματος του Burnside και χρησιμοποιείται για την απαρίθμηση χρωματισμών ενός συνόλου όταν λαμβάνονται υπόψη οι συμμετρίες μιας ομάδας που δρα πάνω του.

Πλαίσιο και βασικοί ορισμοί

Έστω πεπερασμένη ομάδα $G$ που δρα σε πεπερασμένο σύνολο $\mathcal X$ με $|\mathcal X|=N$. Κάθε στοιχείο $g\in G$ επάγει μια αποσύνθεση του $\mathcal X$ σε τροχιές (κύκλους)· ο τύπος κύκλων του $g$ είναι τα μεγέθη αυτών των κύκλων. Αν $c_k(g)$ είναι ο αριθμός των κύκλων μήκους $k$ που δημιουργεί το $g$, ορίζεται το μονώνυμο

$$z_g(t_1,\dots ,t_N)=\prod _{k=1}^N{t}_k^{c_k(g)}\mathrm{.}$$

Ο δείκτης κύκλων (cycle index) της δράσης $G\curvearrowright \mathcal X$ είναι το γεννήτορο

$$Z(t_1,\dots ,t_N)=\frac{1}{\mathrm{\mid }G\mathrm{\mid }}\sum _{g\in G}{z}_g(t_1,\dots ,t_N)=\frac{1}{\mathrm{\mid }G\mathrm{\mid }}\sum _{g\in G}\prod _{k=1}^N{t}_k^{c_k(g)}\mathrm{.}$$

Το $Z$ κωδικοποιεί συμπαγώς τις συμμετρίες της ομάδας σε σχέση με τις τροχιές της δράσης της.

Διατύπωση του θεωρήματος

Αν $G$ δρα στο $\mathcal X$ και $Z(t_1,\dots,t_N)$ είναι ο δείκτης κύκλων, τότε ο γεννήτορας για το πλήθος των χρωματισμών του $\mathcal X$ με χρώματα $a_1,a_2,\dots,a_n$ μέχρι ισοδυναμία υπό τη δράση του $G$ προκύπτει με την αντικατάσταση

$$t_k=a_1^k+a_2^k+\cdots +a_n^k(k=1,\dots ,N)$$

μέσα στο $Z(t_1,\dots,t_N)$.

Χρήσιμες εξειδικεύσεις

Αν υπάρχουν $n$ ισοδύναμα χρώματα, θέτοντας $a_1=\cdots=a_n=1$ (ώστε $t_k=n$ για κάθε $k$) προκύπτει ο συνολικός αριθμός διαφορετικών χρωματισμών (μέχρι συμμετρία):

$$\#(\text{χρωματισμών}/G)=Z(\underbrace{n,\;n,\;\dots,\;n}_{N\ \text{φορές}}).$$

Αν ζητείται παρακολούθηση της κατανομής των χρωμάτων, οι ποσότητες $a_i$ παραμένουν τυπικές μεταβλητές (π.χ. $a_i=x_i$), οπότε η αντικατάσταση παρέχει πολυώνυμο που μετρά χρωματισμούς ως προς πλήθη ανά χρώμα.

Το Θεώρημα του Πόλια είναι βασικό εργαλείο σε συνδυαστικά προβλήματα όπου οι συμμετρικές ανακατατάξεις θεωρούνται ισοδύναμες (χρωματισμοί γραφημάτων, ισομερείς χημικών ενώσεων, μοτίβα σε δίσκους, κομβολογίες κ.ά.), καθώς μεταφράζει την επίδραση της συμμετρίας σε απλό αλγεβρικό υπολογισμό μέσω του δείκτη κύκλων.