1
$\begingroup$

I came across this problem in a book called limits, sequences combinations great book for intro to combinatorics .

A rattle consists of a ring with $3$ white beads and $7$ red ones strung on it. Some rattles seemingly different can be made identical by arranging the rings and moving the beads in a suitable manner (rotation or flipping). Find the number of different rattles .

I of course thought polya enumeration on this one but was thinking it can be done case by case without being too messy . Can anyone help? Also this is essentially the same problem as a necklace with $n$ beads, $k$ colors is it not ?

$\endgroup$
  • $\begingroup$ Yes, these rattles are necklaces in the symmetries that are allowed. Most of the necklace problems I have seen do not specify the number of beads of each color, just the total number of beads and colors. $\endgroup$ – Ross Millikan Mar 7 '18 at 15:10
  • $\begingroup$ would it be as easy as taking 10 spaces, choosing 3 of these for the white beads ? ( the red ones must go around them then ) $\endgroup$ – Randin Mar 7 '18 at 15:19
  • $\begingroup$ but that would overcount? as In wwwbbbbbbb same by rotation as bbbbbbbwww $\endgroup$ – Randin Mar 7 '18 at 15:21
  • $\begingroup$ oops , I meant r not b ..same concept though $\endgroup$ – Randin Mar 7 '18 at 16:08
  • $\begingroup$ Yes, it would overcount. That is the reasoning behind my answer. $\endgroup$ – Ross Millikan Mar 7 '18 at 16:10
1
$\begingroup$

A hand count is not hard. You have to find a way to organize it so you count each configuration only once. We get one configuration for each weak partition of $7$ into $3$ parts. We get $$7,0,0\\6,1,0\\5,2,0\\5,1,1\\4,3,0\\4,2,1\\3,3,1\\3,2,2$$ for eight possibilities. Clearly these are all distinct. You need to convince yourself that there are not two configurations for a partition, but rotation and flipping give six configurations, which matches the number of orders of a partition.

$\endgroup$
  • $\begingroup$ why are we talking partitions when it's combinations? $\endgroup$ – Randin Mar 7 '18 at 15:28
  • $\begingroup$ Because you just count the red beads between each pair of whites. This gives the partitions. As I said, you have to convince yourself that any arrangement of $5,2,0$, say, can reach any other by rotation and reflection. $\endgroup$ – Ross Millikan Mar 7 '18 at 15:36
  • $\begingroup$ pair of whites? there are 3 not 4 $\endgroup$ – Randin Mar 7 '18 at 15:42
  • $\begingroup$ do u have any links that are similar problems to this? $\endgroup$ – Randin Mar 7 '18 at 15:43
  • $\begingroup$ There are three white beads. I am talking about the number of reds in each interval, so there are three pairs of whites. One of the $5,2,0$ configurations is wwrrwrrrrr for example. $\endgroup$ – Ross Millikan Mar 7 '18 at 15:54
0
$\begingroup$

Let me just observe that with $(3,10) = 1$ and $(7,10) = 1$ Polya will be very simple in this case. The OEIS uses necklace for cyclic symmetry and bracelet for dihedral, so we have a bracelet here. The cycle index is from first principles

$$Z(D_{10}) = \frac{1}{20} \sum_{d|10} \varphi(d) a_d^{10/d} + \frac{1}{4} a_2^5 + \frac{1}{4} a_1^2 a_2^4.$$

With the two colors our answer is given by

$$[W^3 R^7] \frac{1}{20} \sum_{d|10} \varphi(d) (W^d+R^d)^{10/d} \\ + [W^3 R^7] \frac{1}{4} (W^2+R^2)^5 \\ + [W^3 R^7] \frac{1}{4} (W+R)^2 (W^2+R^2)^4.$$

From the first term only $d=1$ contributes, the second does not contribute at all and from the third the first term must contribute $WR.$ We get

$$[W^3 R^7] \frac{1}{20} (W+R)^{10} + [W^2 R^6] \frac{1}{2} (W^2+R^2)^4 \\ = [W^3 R^7] \frac{1}{20} (W+R)^{10} + [W^1 R^3] \frac{1}{2} (W+R)^4.$$

The desired count is thus

$$\frac{1}{20} {10\choose 3} + \frac{1}{2} {4\choose 1} = 8.$$

$\endgroup$
  • $\begingroup$ R.Millikans solution is more appealing as it's elegant and swift to slay such an other wise tedious polya enumeration as I predicted 🤓 $\endgroup$ – Randin Mar 8 '18 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.