Matematyka dyskretna 2/Test 5: Zastosowania teorii grup w zliczaniu

From Studia Informatyczne

Orbita \displaystyle Gx w G-zbiorze \displaystyle \left( G, X \right)

to zbiór elementów zbioru \displaystyle X postaci \displaystyle g\!\left( x \right) , gdzie \displaystyle g\in G .

jest równa \displaystyle Gy jeśli tylko istnieje \displaystyle g\in G takie, że \displaystyle g\!\left( x \right)=y .

jest równa \displaystyle Gy dla dowolnego \displaystyle y\in X .

jest równa \displaystyle Gy jeśli tylko \displaystyle x \circ y = id .


Stabilizator \displaystyle G_x w G-zbiorze \displaystyle \left( G, X \right)

to szczególny przypadek orbity.

jest równoliczny z orbitą \displaystyle Gx .

spełnia warunek \displaystyle \left\vert G_x \right\vert\cdot\left\vert Gx \right\vert=\left\vert G \right\vert .

to zbiór permutacji \displaystyle g \in G takich, że \displaystyle g\!\left( x \right)=x .


W G-zbiorze \displaystyle \left( G, X \right) zachodzi:

\displaystyle \left\vert \left\lbrace Gx :x \in G \right\rbrace \right\vert=\frac{1}{\left\vert G \right\vert}\sum_{g\in G} \left\vert {\sf F}\left( g \right) \right\vert .

\displaystyle \bigcup_{x\in X} Gx = X .

\displaystyle \left\vert Gx_1 \right\vert = \left\vert Gx_2 \right\vert dla wszystkich \displaystyle x_1,x_2 \in X .

\displaystyle Gx_1 = Gx_2 dla wszystkich \displaystyle x_1,x_2 \in X .


Dla G-zbioru \displaystyle \left( G, X \right) dwa kolorowania \displaystyle \omega_{1}, \omega_{2} są izomorficzne wtedy i tylko wtedy, gdy:

istnieje permutacja \displaystyle g\in G taka, że \displaystyle \omega_{1}\!\left( g\!\left( x \right) \right)=\omega_{2}\!\left( x \right) dla dowolnych \displaystyle x\in X .

istnieje permutacja \displaystyle g zbioru \displaystyle X taka, że \displaystyle \omega_{1}\!\left( g\!\left( x \right) \right)=\omega_{2}\!\left( x \right) dla dowolnych \displaystyle x\in X

istnieje permutacja \displaystyle g\in G taka, że \displaystyle \hat{g}\!\left( \omega_{1} \right)=\omega_{2} .

\displaystyle \omega_1 = \omega_2 .


Indeks grupy permutacji wszystkich możliwych obrotów \displaystyle 3 -wymiarowej kostki to:

\displaystyle \frac{1}{21}\left( x_1^8+8x_1^2x_3^2+6x_2^4+6x_4^2 \right)

\displaystyle \frac{1}{12}\left( x_1^8+8x_1^2x_3^2+9x_2^4+6x_4^2 \right)

\displaystyle \frac{1}{24}\left( x_1^8+8x_1^2x_3^2+9x_2^4+6x_4^2 \right)

żadna z pozostałych.


Liczba nieizomorficznych kolorowań trzema barwami ścianek sześcianu foremnego to:

54

57

1368

żadna z pozostałych.


Liczba nieizomorficznych kolorowań ścian sześcianu takich, że \displaystyle 4 ściany są białe, a \displaystyle 2 czarne to:

1

2

24

48