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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.