ob曾出过许多challenging的题目，包括数学的。有的尚未有答案。这里代他重贴一题：
红宝石、蓝宝石、绿宝石各6个，穿成1条项链，请问共有几种穿法 ?
穿法总数=18!/(2*6!*6!*6!)=8576568 |
如果把同一项链平放在桌上转一个角度，你的式子可能算了两次。 |
The necklace needs to form a circle, right? |
But I do not know the details. I do not think your solution downstairs is correct. Basically, we want to study how many straight-line stone chains one necklace can form. For different necklaces, the numbers vary. |
formed with straight-line chains (#=18!/6!6!6!) into many subsets, such that rotation and flipping are closed in each subset. I think it is a good problem. And it is hard. I would be very happy if one can give a simple solution. I |
Straight line should be easy. (18!/(2*6!6!6!) + 9!/(2*3!3!3!).) It is the circular ones that cause problem. |
This problem is very hard for me. However, I think it is just an easy exercise for combinatorics experts.
| ||||||||||||
I tried with 6 stones (2 each) and got 11. It basicaaly excluded any simple formula. Looks like it requires a free weekend (which I do not have now) to study the Polya Enumeration Theorem. |
but never have time. |
problem can really be solved by Polya's Theorems. The exercises in that book are easier than this one, but already very hard. Polya's Theorems is one chapter of the book. |
= (18!/(6!6!6!) + 2*3! + 2*6!/(2!2!2!) + 19*9!/(3!3!3!))/36. I will post the details when I find a little more time. |
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. 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. 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. (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.) |
"G consists of 18 rotations and 18 reflections" But this G does not seem to be a group. |
rotation x rotation = rotation rotation x reflection = reflection reflection x reflection = rotation rotation^-1 = rotation reflection^-1 = reflection Actually no proof is needed: If the orbits are well defined (as equivalence classes), the permutations must form a group. |
you are right. I didn't realize that rotation x reflection = reflectionat first. |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |