Combination in symmetry

657 Views Asked by At

Let's assume we have the six identical vertices connected with two different lines colored as green and black.

enter image description here

I want to count how many unique ways we can make a partition in this system. For example, if I want to make 1x5 partitions,

enter image description here

The easiest way we can think of is 6C1=6 cases. However, the system has rotational symmetry with a 60-degree angle. So we will have only 2 unique partitions. If we further ignore the ordering of the color, we only have one unique partition. The partition can only hold one green and one black.

For 3x3 partitions, it becomes a little more complicated. First, we can find there are a total of 6C3=20 partitions that exist. Once we get rid of the double-counting, we only have 10 cases.

However, we need to take account of the symmetry. I know the answer by doing it by hand, we only have 4 unique cases. we have (1(3green and 3 black)+3(Green+Black)+3(3black and one green)+3(3 green and one black).

enter image description here

Using this rule, I was able to count unique solutions as followed

(4 choose 1) we have 1 unique case

(4 choose 2) we have 3 unique case

(6 choose 1) we have 1 unique case

(6 choose 2) we have 4 unique case

(6 choose 3) we have 4 unique case

Is there any way that I can find the generalized combination solution with the symmetry of the system?

1

There are 1 best solutions below

5
On BEST ANSWER

You are asking for the number of partitions of a set (here, a hexagon) which are different with respect to some symmetries (in this case, rotational symmetry). In general this is an important and well-studied question in mathematics. It's great that you've come across this material by studying this example in depth.

The very general way to solve this problem is to use something called Burnside's lemma. If you want to learn more, you should seek out a textbook about group theory.


To solve this specific example systematically, we can use the ideas from Burnside's lemma without explicitly needing the group theory background. For example, let's rephrase your proof that there are $4$ distinct partitions of the hexagon into two sets of three points each.

You correctly pointed out that there are $\binom{6}{3} = 20$ possible subsets of size $3$, so there are $\binom{6}{3} / 2 = 10$ possible partitions. For a partition $P$, let $f(P)$ denote the number of ways of different rotated copies of $P$.

For example, in your image (copied below), let $P$ be the top left partition and $P'$ be the top right partition. Then $f(P) = 3$ and $f(P') = 1$.

Your image

Consider the list of all $10$ partitions $P_1, \dots, P_{10}$. Each partition $P$, it is "overcounted" exactly $f(P)$ times. In order to have each partition that is different with respect to rotation be counted once, we do the following trick. We consider the sum

$$ \sum_{i=1}^{10} \frac{1}{f(P_i)} .$$

In the case where we are looking for partitions of the hexagon into two sets of size three, this becomes the sum

$$ \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + 1 = 4,$$

which is exactly what you counted!

This formula also works for the case where we are splitting the hexagon into a set of size $1$ and a set of size $5$. There, there are $6$ total partitions, and for each partition we have $f(P) = 6$ (because each partition is a rotation of every other). So the sum is

$$ \sum_{i=1}^6 \frac{1}{f(P)} = \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = 1.$$

Try this formula out on some other cases if you're confused how it works. It also works if you replace the hexagon by a different $n$-gon, for example. The hard part becomes calculating $f(P)$ for each partition $P$ (and enumerating all possible partitions). I hope this answers your question.