Circular permutations of identical objects of two kinds.

Question

A necklace is made up of $3$ beads of one sort and $6n$ of another, those of each sort being similar. Show that the number of arrangement of the beads is $3n^2+3n +1$.

My attempt:

There are total $6n+3$ beads. Also, it is a necklace, so their clockwise and anticlockwise arrangements are same. Hence, no. of their cyclic arrangements are given by, $$\frac{1}{2}\frac{(6n+2)!}{3!\times 6n!}$$

This is obviously not what we want to prove. Where am I going wrong?

I found few questions on MSE related to this topic Q.1, Q.2, Q.3 (I doubt this solutions are wrong) . But it didn't address my concern. Also, I'm a high school student and Burnside Lemma is out of my scope. Please help me with an alternate method.

Answer 1

Let us say there are $3$ white beads and $6n$ black beads. A necklace is determined by the lengths of the three sections of black beads comprising the necklace. Call these lenghts $a,b$ and $c$, then the number of ways to choose three nonnegative integers $a,b,c$ which satisfy $a+b+c=6n$ is given by stars and bars to be $$ \#\{(a,b,c):a+b+c=6n, \;\;a,b,c\in \mathbb Z_{\ge 0}\}=\binom{6n+3-1}{2} $$ However, this is overcounting the number of distinct necklaces, because rotation and reflection shows that the the necklaces $(a,b,c),(b,c,a),(a,c,b)$ are all the same, and same for the other three permtuations. To correct for this over counting, we have to count the number of all possible patterns of $(a,b,c)$ separately$^*$:

• The number of neckalces like $(a,a,a)$, where all three lenghts are equal, is just $\boxed{1}$, as you need $a=2n$.

• The number of necklaces like $(a,a,b)$, where $a\neq b$, is the number of solutions to $2a+b=6n$. Here, $a$ can be any number between $0$ and $3n$ inclusive, except for $2n$, because this was counted in the previous case. Therefore, there are $3n$ necklaces in this case.

• The number of necklaces like $(a,b,c)$, where $a\neq b\neq c\neq a$, is given by taking all $\binom{6n+2}{2}$ tuples $(a,b,c)$, subtracting the $1+3\cdot 3n$ tuples counted in previous cases, and then dividing by $6$ to account for the fact that all permutations are the same. The number is$$ \frac16\Big(\binom{6n+2}{2}-1-3\cdot 3n\Big) $$

Adding all three of these together, you get $3n^2+3n+1$.

$^*$ A better way is to use Burnside's Lemma, but you said in the comments you wanted to avoid this.

Answer 2

This is open to interpretation, but I understand the statement that "it is a necklace" to mean that rotating the beads cyclically yield equivalent arrangements (but not flipping the necklace). I assume this in what follows.

Observe that in a given arrangement, the $3$ beads of the first sort (I will call them red) separate the $6n$ (blue) beads of the second sort into three (possibly empty) groups. We can represent the arrangement without loss of information as an ordered triplet of the three group sizes in clockwise order. Obviously the three numbers in this triplet must be nonnegative and must sum to $6n$. However, some such triplets represent the same necklace; any cyclic permutation of a triplet is a representation of the same necklace, e.g.:

• $(3n,3n,0) \sim (3n,0,3n) \sim (0,3n,3n)$
• $(3n-1,3n-1,2) \sim (3n-1,2,3n-1) \sim (2,3n-1,3n-1)$
• ...

Careful! Even if we had the number of nonnegative triplets summing to $6n$, we could not simply divide that by $3$. Triplets like $(2n,2n,2n)$ are counted only once, not three times.*

Here we are saved from having to use Burnside's lemma or similar results because there are only three numbers. Consider a triplet representing some fixed, arbitrary arrangement. Since it sums to $6n = 3 \times 2n$, at least one of its values must be $\ge 2n$, and one must be $\le 2n$. The largest value in the triplet must then be at least $2n$. If it appears only once, we can rotate our triplet so that it appears first. If it appears more than once, we choose the rotation that places the smallest value first. Thus we can represent each necklace as a triplet $(a,b,c)$ where $a+b+c=6n$ and exactly one of the following holds:

• $a \gt b,c$ and $a \ge 2n$
• $a \le b = c$

For each necklace we have one and only one such triplet, and vice-versa; this correspondence is a bijection. So we just have to count the number of such triplets. Try it!

*This observation is what is behind Burnside's lemma. Later I might add a small explanation of the lemma as problems like this are much more cleanly solved using it.

---

A note on the lemma

Let's try to make the problem description a little more formal. First consider the simpler situation of $n$ beads on a straight piece of string, each of a different color (I will label them $a$, $b$, ..., $z$, but there can be any number). Any necklace arrangement with these same beads can be obtained from one such string arrangement by tying the string ends together, but more than one string arrangement produces the given necklace arrangement in this way. The precise loss of identity we introduce among the string arrangements by tying ends is the following:

The string arrangement $abc\dotso xyz$ becomes the same necklace arrangement as any of $bc\dotso xyza$, $c\dotso xyzab$, etc., as well as $zabc\dotso xy$, $yzabc\dotso x$, etc.

These "rotations" of strings of beads are commonly called cyclic permutations. There are exactly $n$. With this terminology, a string gives the same necklace as any cyclic permutation of itself. A cyclic permutation really is the operation of taking off a certain number of beads from one end of the string and putting them back on the other end in the same order; formally this operation is seen as a function from strings to strings. This view draws attention to three important properties of cyclic permutations:

• They can be chained together. We say composed.
• One of them does nothing, namely moving 0 beads from one end to the other. We call this one the identity, as it sends every string to itself.
• Each can be undone. More formally, each cyclic permutation can be composed with its inverse permutation to give the identity. (The inverse is unique for a given permutation).

These three properties are the group axioms. The cyclic permutations form a group, and it is such a common one that it is given a name: the cyclic group of order $n$, written $C_n$.

With these permutations we can do more than just rotate the particular strings we have been considering. We can also use them to rotate strings with other, less varied beads, non coincidentally the ones in the original problem for example, with 3 beads of one color and a multiple of 6 of another; this set of strings will be called $X$. This action of sending elements of $X$ to other elements of $X$ through $C_n$ is called exactly that, an action of $C_n$ on $X$.

Burnside's lemma relates the number of strings in $X$ to the sizes of special substructures of $C_n$. These substructures are identified by the way they act on strings in $X$. Their sizes are relatively easy to determine, and because the number of these substructures is very closely related to the number of distinct necklaces obtained from strings in $X$, the lemma allows us to calculate this number.

I will complete this fly-over tomorrow. I'll probably add links to Wikipedia for the various objects mentioned.