8.6 An Application to Combinatorics
1. Let H act on G by h · x = hx for x 
G, h H. Then the orbits H · x = Hx are right cosets. Given
G, h H. Then the orbits H · x = Hx are right cosets. Given
Thus the Cauchy-Frobenius lemma gives the number of cosets as 
3. a. If the vertices are labeled as shown, the group G ⊆ S3 of motions is G = {ε, (23)}. Hence |F(ε)| = q3 and |F((23))| = q2, so the number of orbits is 
by Theorem 2.
by Theorem 2.
4. a. By Example 3 §2.7, the group of motions of the tetrahedron is A4. Now |A4| = 12 and A4 consists of ε, eight 3-cycles, and (1 2)(3 4), (1 3)(2 4) and (1 4)(2 3). Hence |F(σ)| = q2 for all σ A4 except σ = ε. Hence the number of colorings is 
by Theorem 2.
A4 except σ = ε. Hence the number of colorings is by Theorem 2.
5. a Label the top and bottom as 1, 2, and the sides 3, 4, 5, 6 as shown. The group of motions is
Here cyc ε = 6, cyc(3456) = 3, cyc(35)(46) = 4 and cyc (12)(34)(56) = 3. Hence Theorem 2 gives 
as the number of colorings.
as the number of colorings.
6. a. The tetrahedron has 4 vertices so the number is 
as in Exercise 4.
as in Exercise 4.
7. Label the faces 1–6 as shown. Then a typical permutation σ in each category in the hint is
Hence the number of orbits is
8. a. Number the sections 1-6 in order. Then G =
σ 
where σ = (123456). Hence
σ where σ = (123456). Hence
By Theorem 2, the number of orbits is
9. If n = 2m then 
Number the strips 1, 2, . . ., n. Then G = {ε, (1 n)(2 n − 1) 
(m m + 1)} so the number of orbits is 
, as required. If n = 2m − 1 then
(m m + 1)} so the number of orbits is , as required. If n = 2m − 1 then
Now G = {ε, (1 n)(2 n − 1) (m − 1 m + 1)} so the number is 
, again as required.
(m − 1 m + 1)} so the number is , again as required.
11. If the vertices and edges are labeled as shown, the group of (vertex) motions is G = {ε, (13), (24), (13)(24)}. Each σ G induces an edge permutation σe in S5 as follows:
G induces an edge permutation σe in S5 as follows:
As in the preceding exercise, colorings are pairs (λ, μ) when 
and μ : {1, 2, 3, 4, 5} → Ce. Hence
and μ : {1, 2, 3, 4, 5} → Ce. Hence
Thus the number of orbits is
12. a. If X = {(a, b) G × G 
ab = ba} then p(G) = |X||G × G| = |X||G|2. Now
G × G ab = ba} then p(G) = |X||G × G| = |X||G|2. Now
Hence |X| = ∑ aG|N(a)| = |G|k(G) by the Corollary to the Cauchy-Frobenius lemma, and the result follows.
G|N(a)| = |G|k(G) by the Corollary to the Cauchy-Frobenius lemma, and the result follows.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.