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
(
geocities.com/liviozuc)