How Many Distinct Patterns?

Date: 01/15/2001 at 03:51:45
From: Ralph
Subject: Discrete Mathematics - Enumeration Combinatorics

My problem is not a complete lack of understanding the material, as 
the following questions may suggest, but transferring what I do 
understand into the required mathematics.

1. Given the following structure formed by attaching four equilateral 
triangles (taking a large equilateral triangle and drawing lines from 
the midpoint of each side to the midpoint of every other side); if two 
rods are painted white and the rest are painted black, how many 
distinct patterns are possible?

* I have a basic understanding of rotational symmetry and I know that 
I only need focus on the white colorings, but could you explain in 
detail how this problem is to be solved? For example, how do you 
construct the equation and how do you work out symmetry? (I want to 
adapt this to a tetrahedron, cube, octahedron and so on.)

2. What about vertices? Say I have a floating cube and mark any two 
vertices with a pen. How many distinct patterns are possible?

Please forgive me for my ignorance in the questions above; I am 
attempting this as a self-enrichment exercise.

Yours sincerely,
Ralph

Date: 01/16/2001 at 10:33:34
From: Doctor Mitteldorf
Subject: Re: Discrete Mathematics - Enumeration Combinatorics

Dear Ralph,

In approaching problems like this, I usually do specific examples 
first, and look for patterns that lead to general formulas only after 
I've done several examples.

In question 1, are you asking about a figure like this?

         .
        / \
       .---.
      / \ / \
     .---.---.

The way I've interpreted your question is that any two of the nine 
line segments can be painted white, and the question is how many 
distinct figures there can be. The answer is that there are two kinds 
of line segments: outside and inside. If both white ones are inside, 
then there is just one possible figure. If both are outside, then the 
pair may either be adjacent or separated by one or by two segments. If 
they are adjacent, they could form a vertex or they could form a side 
of the larger triangle. If one is outside and one inside, then there 
are three possible configurations, so I count eight different choices.

Both lines on the inside:
         .
        . .
       .---.
      . \ . .
     .........

Both lines on the outside:
         .             .             .             .
        . .           / .           . \           / .
       .....         .....         .....         .....
      / . . .       / . . .       / . . .       . . . .
     .---.....     .........     .........     .....---.

One line inside, one line outside:
         .             .             .
        . .           . .           / .
       .....         .---.         .....
      . \ . .       . . . \       . . / .
     .---.....     .........     .........


In a cube, a pair of vertices may be adjacent, or they may be 
diagonally across the same face, or they may be diagonally opposite in 
three dimensions. These three possibilities are exhaustive.

It would be interesting to set about generalizing this kind of 
problem, and looking for general formulas. The process has to involve 
setting up some rules, analyzing some examples, changing the rules, 
analyzing some more examples, and gradually getting a feel for what 
rules generate interesting mathematics.

This kind of process illustrates how the best mathematics is created.

- Doctor Mitteldorf, The Math Forum
  http://mathforum.org/dr.math/   

Date: 01/16/2001 at 12:13:27
From: Doctor Anthony
Subject: Re: Discrete Mathematics - Enumeration Combinatorics

We use Burnside's lemma for this type of question. You consider the 
six symmetries of an equilateral triangle and sum all those symmetries 
that keep colors fixed. The number of non-equivalent configurations is 
then the total sum divided by the order of the group (6 in this case).

There are 9 rods forming the figure of which 2 are white and 7 are 
black.

Label the rods forming the large triangle in cyclic order a, b, c, d, 
e and f.

Group actions that keep colors fixed.

     Identity = 9!/[2!7!] = 36

2 white in same straight line on large triangle. (e.g. rods a and b)

     Reflection about perpendicular axis = 3 x 1 = 3

2 white forming apex on large triangle. (e.g. rods a and f)

     Reflection about axis through the apex = 3 x 1 = 3

2 white on different sides of large triangle and not forming an apex. 
(e.g. rods b and e) 

     Reflection about axis of symmetry between the two = 3 x 1 = 3   

Other combinations such as (a,c) will have no group actions that keep 
colors fixed.   

For the middle triangle we label the sides g, h and i with g the third 
side of triangle with sides a, g and f.

2 white in small middle triangle

     Reflection about axis of symmetry between the two = 3 x 1 = 3 

With one side from large triangle and one side from the small inner 
triangle, e.g., (a,g), (a,i) and (a,h) there will be no group actions 
that keep colors fixed.

So we now have the total of group actions that keep colors fixed

     = 36 + 4 x 3 = 48

Using Burnside, the number of non-equivalent configurations

     = 48/(order of the group)

     = 48/6

     = 8

So there are eight distinct configurations with two white and seven 
black rods.


>2. What about vertices? Say I have a floating cube and mark any 2 
>vertices with a pen. How many distinct patterns are possible?

We again use Burnside, but this time it is better to derive the cycle 
index and use purely algebraic methods. So we first find the cycle 
index of the group of vertex permutations induced by rotational 
symmetries of a cube.

You should hold a cube and follow the way the cycle index is 
calculated as described below. The notation  (1)(23)(456) = 
(x1)(x2)(x3) means that we have a permutation of 3 disjoint cycles in 
which vertex 1 remains fixed, vertex 2 moves to vertex 3 and 3 moves 
to vertex 2, vertex 4 moves to 5, 5 moves to 6 and 6 moves to 4. (This 
is not a possible permutation for our cube; it is just to illustrate 
the notation.) We now calculate the cycle index.

Looking down on the cube label the top vertices 1, 2, 3 and 4 in 
clockwise order; label the bottom vertices so that 5 is below 1, 6 is 
below 2, 7 is below 3 and 8 is below 4. The permutations composing the 
symmetry group fall into the following classes:

(i) Identity e = (1)(2)(3)(4)(5)(6)(7)(8), with index (x1)^8

(ii) The permutation (13)((24)(57)(68) corresponding to the rotation 
through 180 degrees about the line joining the midpoints of the top 
and bottom faces, plus 2 analogous permutations.  

     The net cycle index is 3(x2)^4 

(iii) The permutation (1234)(5678) corresponding to a clockwise 
rotation through 90 degrees about the line joining the midpoints of 
the top and bottom faces, plus 2 analogous permutations.

     The net cycle index is 3(x^4)^2

(iv) Same as (iii) but counterclockwise,

     Cycle index 3(x4)^2

(v) The permutation (12)(35)(46)(78), corresponding to a rotation of 
180 degrees about the line joining the midpoints of opposite sides 12 
and 78, plus five analogous permutations.

     The net cycle index is  6(x2)^4

(vi) The permutation (1)(245)(386)(7), corresponding to a clockwise 
rotation through 120 degrees about the diagonal 17, plus three 
analogous permutations.

     The net cycle index is 4(x1)^2.(x3)^2

(vii) Same as (vi) but counterclockwise;

     Cycle index 4(x1)^2.(x3)^2   

The order of the group is 1 + 3 + 3 + 3 + 6 + 4 + 4 = 24

The total cycle index is

     = (1/24)[(x1)^8 + 9(x2)^4 + 8(x1)^2.(x3)^2 + 6(x4)^2]

With say two Red and six Black vertices we shall have to find the 
coefficient of R^2.B^6 in the expansion of

   (1/24)[(R+B)^8 + 9(R^2+B^2)^4 + 8(R+B)^2.(R^3+B^3)^2 + 
6(R^4+B^4)^2]

since we are only concerned with terms up to R^2 we can ignore the 
very last term.

                (R+B)^8  gives C(8,2)R^2.B^6 
             (R^2+B^2)^4 gives C(4,1)R^2.B^6
     (R+B)^2.(R^3+B^3)^2 gives R^2.B^6

So total coefficient of

     R^2.B^6 = C(8,2) + 9 x C(4,1) + 8

             = 28 + 36 + 8

             = 72

and applying Burnside the number of non-equivalent configurations is

     = 72/order of group

     = 72/24

     = 3

So there are three distinct cubes that have two vertices painted a 
different color to the other six.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/