I have found some time to read the first couple of pages of the Pólya theory, not up to the real Pólya enumeration theorem (PET) yet, but learned just enough to solve this problem.www.ddhw.com Let X be a finite set and G a permutation group on S. Define the orbits of S under G as the G-equivalence classes (s is equivalent to s' if there is g in G such that g(s) = s'). For g in G, define the set Sg of the fixed points of g as {s in S : g(s) = s}. Theorem. The number of orbits of S under G = (1/|G|) ∑(g in G) |Sg|. This theorem is a simplified version of the PET, and also know as Burnside's lemma. Now let's see how it applies to the necklace problem.www.ddhw.com Here S is the set of all straight line arrangement of the 18 stones. (|S| = 18!/(6!6!6!).) G consists of 18 rotations and 18 reflections. Each orbit corresponds to one real necklace. For each reflection, a fixed point is a (somewhat) symetric element in S, and there are 9!/(3!3!3!) of them.
Now consider the rotations. Let's call them r0 to r17, for how much it rotates. Only r0, r3, r6, r9, r12, and r15 have fixed points. For r0 (no move), Sg = S. For the others, Sg is the set of periodic patterns with period 3, 6, 9, 6, and 3, respectively, and |Sg| = 3!, 6!/(2!2!2!), or 9!/(3!3!3!). Now we apply the theorem, and the total number of different necklaces is (18!/(6!6!6!) + 2*3! + 2*6!/(2!2!2!) + 19*9!/(3!3!3!))/36 = 477386. A straight application of the theorem works for the cube problem (or any regular polyhedron coloring problem) too. I would like to see some one try it. The key is to find all permutations. (If you don't, the division very often produces fractions.) www.ddhw.com
| 
哈哈哈哈 O(∩_∩)O哈哈~ 好久不来了，不小心看了一眼自己主页，发现自动关联了自己以往发过的帖，点进这个看了一眼，笑个半死。。。敢情我当初还发过这么搞笑的东西啊，我自己完全不记得了 
雷达卡
发表于 2005-2-14 10:56:11
收藏
分享
支持
反对
置顶卡
千斤顶
楼主
发表于 2005-2-14 17:07:36