Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

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

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/
```
Associated Topics:
College Discrete Math
High School Discrete Mathematics
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search