Share
Explore BrainMass

Combinatorial problems with counting principles

1. Use the theorem below to determine the number of nonequivalent colorings of the corners of a rectangle that is not a square with the colors red and blue. Do the same with p colors.

(the answer is (p^4+3p^2)/4...i just dont know how to get there)

Theorem: Let G be a group of permutations of X and let C be a set of colorings of X such that f * c is in C for all f in G and all c in C. Then the number N(G,C) of nonequivalent colorings in C is given by
N(G,C) = (1/absG)∑(abs(C(f)), (in words the number of nonequivalent colorings in C equals the average of the number of colorings fixed by the permutations in G)

2. A two-sided marked domino is a piece consisting of two squares joined along an edge where each square on both sides of the piece is marked with 0,1,2,3,4,5 or 6 dots.

a. use the theorem above to determine the number of different two sided marked dominoes.
b. how many different two sided marked dominoes are there if we are allowed to mark the squares with 0,1,...p-1 or p dots?

( the answer to 2a the group of permutation now consists of four permutations of the four squares to be marked. This gives (7^4+3*7^2)/4=637...i just dont know how to get there)

Solution Preview

1. For 2 colors, we can easily list all the choices.

Filling it with just reds or blues can be done in only 1 way. So, this gives 2.

Filling with 3 reds and 1 blue or 3 blues and 1 red can also be done only 1 way. This gives 2.

With 2 reds and 2 blues, we have only 3 ways to do it.

1. Both reds and both blues on the longer side of the rectangle.
2. Both reds and both blues on the shorter side of the rectangle.
3. Reds and blues that are diagonally opposite to one another.

This counts to 3.

Thus, total = 2 + 2 +3 = 7.

We first determine the number of different permutations of the vertices of the ...

Solution Summary

1. How to calculate the number of non-equivalent colorings of a rectangle?

2. How to calculate the number of non-equivalent markings of a domino?

$2.19