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.
Best Answer
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.:
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:
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:
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:
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.