Matematyka dyskretna 2/Ćwiczenia 5: Zastosowania teorii grup w zliczaniu

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zastosowania teorii grup w zliczaniu

Ćwiczenie 1

Pokaż, że dla G-zbioru oraz , stabilizator elementu wraz z składaniem, tzn. jest podgrupą grupy .

Wskazówka
Rozwiązanie

Ćwiczenie 2

Niech będzie zbiorem indeksów wierzchołków dwudziestościanu foremnego. Ponadto niech będzie grupą obrotów (w ) tego dwudziestościanu. Przedstaw stabilizator wierzchołka w działaniu grupy permutacji na zbiorze i rozłóż permutacje z tego stabilizatora na cykle.

Wskazówka
Rozwiązanie

Ćwiczenie 3

Pokaż, że dla G-zbioru zachodzi



gdzie .

Wskazówka
Rozwiązanie

Ćwiczenie 4

Przedstaw indeks grupy obrotów sześciokąta.

Wskazówka
Rozwiązanie

Ćwiczenie 5

Policz na ile różnych sposobów można pokolorować szachownicę dwoma kolorami. Szachownica nie ma wyróżnionych boków, więc dwu kolorowań nie można rozróżnić poprzez jej obrót względem osi do niej prostopadłej.

Wskazówka
Rozwiązanie

Ćwiczenie 6

Niech , i . Policz liczbę kolorowań zbioru spełniających warunki:

  • elementy zbioru są jednobarwne,
  • elementy są pokolorowane na czerwono, elementy są pokolorowane na zielono, elementy są pokolorowane na niebiesko.
Wskazówka
Rozwiązanie

Ćwiczenie 7

Na ile sposobów można spiąć w naszyjnik korale czerwone i zielone.

Wskazówka
Rozwiązanie