Cykelindex

Från Wikipedia
Hoppa till: navigering, sök

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[redigera | redigera wikitext]

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 jk(σ) ä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[redigera | redigera wikitext]

Om X är en mängd och permutationsgruppen G är en delgrupp till den symmetriska gruppen över X och p(x1, ..., xn) ä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[redigera | redigera wikitext]

Grupp med tre element[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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