To: livzucca@tin.it Subject: sexehexes, etc. Hi Livio, I've been enjoying your page on sexehexes and the frequent updates. Thought I'd complete your table at the end of polysexes for you. (Look up Polya counting in a combinatorics book, it will explain how I got these. I'll write up an explanation myself soon, explaining a small generalization that will count the number of pieces when you have what you call "COMPLEX" (such as Xominoes) pieces. Nr. Triangle Square Hexagon edge-forms 1-side 2-side 1-side 2-side 1-side 2-side 1 1 1 1 1 1 1 2 4 4 6 6 14 13 3 11 10 25 21 130 92 4 24 20 73 55 700 430 5 45 35 170 120 2635 1505 6 76 56 343 231 7826 4291 7 119 84 626 406 19684 10528 8 176 120 1058 666 43800 23052 9 249 165 1683 1035 88725 46185 10 340 220 2552 1540 166870 86185 These are polynomials: Let x represent the number of different edge forms. For Triangle 1-side # piece: (x^3+2x)/3 Triangle 2-side # piece: (x^3+3x^2+2x)/6 Square 1-side: (x^4+x^2+2x)/4 Square 2-side: (x^4+2x^3+3x^2+2x)/8 Hex 1-side: (x^6+x^3+2x^2+2x)/6 Hex 2-side: (x^6+3x^4+4x^3+2x^2+2x)/12 Here is an even longer table, without headings, since I typed the above formulas into a short program: 1 1 1 1 1 1 1 2 4 4 6 6 14 13 3 11 10 25 21 130 92 4 24 20 73 55 700 430 5 45 35 170 120 2635 1505 6 76 56 343 231 7826 4291 7 119 84 626 406 19684 10528 8 176 120 1058 666 43800 23052 9 249 165 1683 1035 88725 46185 10 340 220 2552 1540 166870 86185 11 451 286 3723 2211 295526 151756 12 584 364 5259 3081 498004 254618 13 741 455 7228 4186 804895 410137 14 924 560 9705 5565 1255450 638015 15 1135 680 12772 7260 1899080 963040 16 1376 816 16516 9316 2796976 1415896 17 1649 969 21029 11781 4023849 2034033 18 1956 1140 26410 14706 5669790 2862597 19 2299 1330 32765 18145 7842250 3955420 20 2680 1540 40205 22155 10668140 5376070 21 3101 1771 48846 26796 14296051 7198961 22 3564 2024 58811 32131 18898594 9510523 23 4071 2300 70230 38226 24674860 12410432 24 4624 2600 83238 45150 31853000 16012900 25 5225 2925 97975 52975 40692925 20448025 26 5876 3276 114588 61776 51489126 25863201 27 6579 3654 133231 71631 64573614 32424588 28 7336 4060 154063 82621 80318980 40318642 29 8149 4495 177248 94830 99141575 49753705 30 9020 4960 202957 108345 121504810 60961655 31 9951 5456 231368 123256 147922576 74199616 32 10944 5984 262664 139656 178962784 89751728 33 12001 6545 297033 157641 215251025 107930977 34 13124 7140 334670 177310 257474350 129081085 35 14315 7770 375777 198765 306385170 153578460 36 15576 8436 420561 222111 362805276 181834206 37 16909 9139 469234 247456 427629979 214296193 38 18316 9880 522015 274911 501832370 251451187 39 19799 10660 579130 304590 586467700 293827040 40 21360 11480 640810 336610 682677880 341994940 Just in case you are curious, the reason there are 100 Xominoes boils down to the following: ( 5^4 + 2(5*3^2) + 3(5^2)+2(5) ) / 8 = 100. Note that the term that was 5^3 if you had "SIMPLE" pieces (as above) has become 5*3^2. More later, gotta teach. -Chris -------------------------------------------------- To: "livzucca@tin.it" Subject: Addendum - more sexehexes etc. Just wanted to add the following for you, I'll explain later: If you have x edge-forms but only s (for "symmetric" or "simple") are the same when flipped (and the remaining x-s edge forms come in pairs where one is the "flip" of the other), then the polynomials are Triangle 2-side # piece: (x^3+3xs+2x)/6 Square 2-side: (x^4+2xs^2+3x^2+2x)/8 Hex 2-side: (x^6+3x^2s^2+4x^3+2x^2+2x)/12 For squares x=5 s=3 is Xominoes. x=5 s=1 is your "Faces puzzle". (I think. You didn't really describe it.) For Hexes, x=5 s=1 is Zucca's Puzzle. Note that there is more than one "puzzle" with the same number of pieces, for both one-sided and two-sided cases. For instance, making an edge-form like your "S" in one-sided Xominoes matches with itself. If you make instead an "M" you need an "F" to match it. Is Sexehexes with the 130 one-sided set easier or harder if you use -SZ instead of -MF as your three edge forms? Same question for two-sided. -Chris -- Prof. Chris Hartman http://tigger.cs.uaf.edu/hartman hartman@arsc.edu University of Alaska, Fairbanks and Arctic Region Supercomputing Center -------------------------------------------------------- To: Livio Zucca Subject: Re: sexehexes etc. References: <1.5.4.32.20000415101147.006644ec@box.clubnet.tin.it> Livio Zucca wrote: > Thank you very much for yours material. > I'm not able to extract your polynomials. Do you mean you couldn't read what I wrote, or that you weren't able to find them on your own? > I want to learn it. They are very powerful. I'll try to explain it below, but you may wish to look it up if you can find a book on combinatorics that is fairly readable. Look under Polya theory, or Poly enumeration. Unfortunately, most books I've found are hard unless you study combinatorics. (My Ph.D. is in combinatorics and graph theory...) > I want to publish your email on my page, if you agree. Yes, go ahead. You may also put my explanation (and anything else from this email) that you like. > I'm working to a 3-D puzzle: SexCube. > Do you confirm me that I generate 800 pieces exactly if I use cubes with 5 > "simple" side-forms? Yes. The polynomial for cubes is (x^6 + 3x^4 + 12x^3 + 8x^2) / 24. An Attempt at a Simple Explanation of Basic Polya Enumeration. We wish to count the number of different ways to color some shape. If we use x colors on a shape with y sides, then at first glance we might think there are x^y ways to color it. (For instance, using x=2 colors to color a domino (y=2 ends) there are 2^2=4 colorings: RR RB BR BB.) But wait! Some of these colorings are the same. (In the domino example RB and BR are the same: we can turn the domino around) How do we keep from counting these multiple times? The answer is to count all of the colorings multiple times, and then divide by the number of times we counted them. For a domino colored with x colors, the number x^2 counts almost all colorings twice, except for those that use only one color. Those are counted only once. So: count them again. There are x of them. The total number of different ways to color a domino with two colors is (x^2 + x)/2. How can we generalize this? The basic idea is to consider the "symmetries" of the object we are trying to color. Consider a more complicated example, say, a square (a one-sided square - that is, one that can _not_ be flipped over.) If we color the (y=4) corners of a square with x=5 colors the term x^y counts most colorings four times, like the ones here (each coloring in each column is the same): AB AB CD DC CD EE BC BD DE AD AC CE CD DC EE BA BA DC DA CA EC CB DB ED But some colorings have not been counted four times, like these: AA AB AA BA BA AB The first has only been counted once, the second has been counted twice. There are 5 (x) colorings like the first one, and 20 like the second one. [5 choices for A, (5-1) choices for B]. To count every coloring four times, we would need the first type three more times and the second type two more times. The equation is (5^4 + 3*5 + 2*5(5-1))/4 = (5^4 + 5 + 2*5^2)/4 The key observation is found by examining the symmetries of our square. It can be rotated by 0 degrees, 90 degrees, 180 degrees, or 270 degrees. By careful thought or mathematical proof, one can convince oneself that we fail to count a coloring in the term x^y only when some symmetry of the object leaves that coloring totally unchanged. (For instance, the square AB BA is left unchanged if we rotate it 180 degrees). This means we can turn our counting around (Burnside's Lemma): For each symmetry of our object, we count the number of colorings that are left unchanged by that symmetry. We add these all up and divide by the number of symmetries, the result is the number of different colorings. The number of colorings left unchanged by a symmetry is x^c where c is the number of cycles in the permutation representation of the symmetry. For instance, in the case of a two-sided square (one we _can_ flip over) the symmetry "reflect about the line from upper left to lower right) has three cycles (if we are coloring the corners.) The upper left corner maps to itself. The lower right corner maps to itself. The upper right corner maps to the lower left corner, which maps back to the upper right. That's three. On the other hand, that same symmetry has only two cycles if we are talking about coloring the edges of the square: The top goes to the left which goes back to the top, and the right goes to the bottom which goes back to the right. To work out a couple of examples in full, consider coloring the edges of one-sided triangles. We have have three symmetries: Rotate by 0 degrees (R0), R120 and R240. There are x^3 colorings left unchanged by R0. (three cycles: each edge goes to itself). There are x colorings left unchanged by R120 (one cycle: each edge maps to the next). There are x left unchanged by R240 (again, one cycle.) The total number of colorings is (x^3 + 2x)/3. If we instead do two-sided triangles, we must add three reflections, each has two cycles (because a reflection of a triangle swaps two edges [the first cycle] and leaves the third unchanged [the second cycle]. Thus, for coloring the edges of two-sided triangles, we have (x^3 + 3x^2 + 2x)/6 colorings. What you call "complex" edges work out automatically: If you look at the Xominoes which have 5 edge "colors" MFSZ-. How many colorings are left unchanged (for example) by flipping a square around it's vertical axis? Well, we can put anything on the left edge that we like [and put it's reflection on the right]. For the top and the bottom, we can use M, F, or -, but not S or Z (since M, F, and - stay the same if we reflect them through the middle, but S and Z aren't). Thus, there are 5*3*3 colorings that aren't changed by that reflection. If you work it out, you'll find each term in the polynomials that I sent you before comes from one of the symmetries of the object. One more example: The cube polynomial listed above: (x^6 + 3x^4 + 12x^3 + 8x^2) / 24 The cube has 24 symmetries (6 choices for the top face, 4 for the front). If you look for them all, you find that they are all rotations. R0, the identity rotation accounts for the term x^6. There are three rotations of 180 degrees around axis through the center of the faces. Each of these has 4 cycles. [For instance, rotation 180 degrees about the axis through the center of the top and bottom faces has the following cycles: (top) (bottom) (left,right) (front, back).] That's the term 3x^4. There are six rotations of 90 or 270 degrees about those same axis, each of these has three cycles. [Example, 90 degrees about axis through center of top to center of bottom. (top) (bottom) (front,left,back,right)] That's 6x^3. There are 8 rotations around axis through diagonally opposite vertices of the cube [4 axis, rotation by 120 or 240]. Each of these has two cycles, which is the term 8x^2. There are 6 axis through midpoints of opposite edges, rotation by 180 degrees about such an axis gives three cycles, which is another 6x^3. Putting them all together, we get the above polynomial. Polya enumeration goes much further, actually, but I'm not going to explain it in detail. By putting in a little more information about the cycles each symmetry has, you can come up with a polynomial that [when expanded] will let you look up (for example) the number of 5-colorings of the faces of a cube that use red twice, blue once, and green three times. Hope this was helpful. -Chris -- Prof. Chris Hartman http://tigger.cs.uaf.edu/hartman hartman@arsc.edu University of Alaska, Fairbanks and Arctic Region Supercomputing Center