Cykelindex

Cykelindex är inom matematik som används vid kombinatorisk enumeration när man tar hänsyn till symmetrier.

En permutation kan faktoriseras i disjunkta cykler, permutationens cykelindexmonom beskriver denna strukturen hos denna faktorisering. En permutationsgrupps cykelindexpolynom är medelvärdet av elementens cykelindexmonom.

Definition

En permutation σ:s cykelindexmonom är monomet

$\prod_{k=1}^n x_k^{j_k(\sigma)} = x_1^{j_1(\sigma)} x_2^{j_2(\sigma)} \cdots x_n^{j_n(\sigma)}$

där j_k(σ) är hur många cykler av längd k det finns i den fullständiga faktoriseringen av σ.

En permutationsgrupp G:s cykelindexpolynom Z(G) är medelvärdet av cykelindexmonomen av permutationerna i gruppen:

$Z(G) = \frac{1}{|G|} \sum_{\sigma \in G} \prod_{k=1}^n x_k^{j_k(\sigma)}$

Följder

Om X är en mängd och permutationsgruppen G är en delgrupp till den symmetriska gruppen över X och p(x₁, ..., x_n) är G:s cykelindexpolynom så kan X färgläggas med q färger, med hänsyn till symmetrierna i G, på p(q, q, ..., q) sätt. Detta är en följd av Burnsides lemma.

En generalisering av detta är Polyas enumerationssats.

Exempel

Grupp med tre element

Ta gruppen G = { e, (1 2 3), (1 3 2)}, som består av identitetsavbildning och två tre-cykler. Cykelindexpolynomet för G är:

$Z(G) = \frac{1}{3} \left( x_1^3 + 2x_3 \right)$

Gruppen G kan tolkas som rotationssymmetrier på en triangel där sidorna är numrerade 1, 2, 3. Om man vill färga triangelns sidor med två färger finns det då

$\frac{1}{3} \left( 2^3 + 2 \cdot 2 \right) = 4$

sätt att göra det på. Dessa är att alla sidor har färg 1, alla sidor har färg 2, en sida har färg 1 och de andra färg 2 samt en sida har färg 2 och de andra färg 1.

Referenser

• Rotman, Joseph (1995). An Introduction to the Theory of Groups. Springer Verlag. ISBN 0-387-94286-8