1
$\begingroup$

The original problem has been discussed here, which involves a necklace of $p$ beads each of which can be one of $a$ colors and shows that $a^p - a$ must be a multiple of $p$ by classifying the necklaces which are cyclic permutations of each other as indistinguishable and a necklace of length $p$ has $p$ cyclic permutations leading to $\frac{a^p - a}{p}$ distinct necklaces. Please see the original posting for details.

Follow-up question: Since there are $a!$ ways to permute the $a$ colors, is $\frac{a^p - a}{p}$ divisible by $a!$ ?

Clarification: We should assume $a < p$ if not use $a \bmod p$. This will lead to such necklaces where all $a$ colors used.

$\endgroup$
  • $\begingroup$ No. If you try to partition necklaces according to permuted colors, not all classes will have the same number of elements -- some necklaces have fewer recolorings, e.g. if the necklace has only one color, it has $a$ recolorings. $\endgroup$ – Wojowu Sep 15 '17 at 16:08
  • $\begingroup$ Not all colors are used in any necklace, so you don't get equivalence classes all of sizes $n!$. $\endgroup$ – Thomas Andrews Sep 15 '17 at 16:10
  • $\begingroup$ @ThomasAndrews: Thanks for the response, please see the clarification I added to the question $\endgroup$ – Vectorizer Sep 15 '17 at 17:02
  • $\begingroup$ No, some necklaces still only use, say, $2$ colors, no matter what $a$ is. So, for example, when you have $a=4$ and $p=5$, you could use $2$ colors in a necklace $RRBBB$. Then permuting the colors (and rotating the necklace) gives only $4\times 3\times 5=120$ arrangements, which is not divisible by $5\cdot 4!=240$. $\endgroup$ – Thomas Andrews Sep 15 '17 at 17:13
2
$\begingroup$

Suppose $a=4\,,p=3\,$ $$\frac{4^3-4}{3×4×3×2}$$ $$\frac{64-4}{4×3×3×2}$$ $$\frac{60}{4×3^2×2}$$ $$\frac{5}{6}$$ Hence disproved

The thing is, the necklaces you got may have such combinations where 1 color might have repeated less than $p$ times, $$$$(as you only discarded the ones which had 1 colour repeated $p$ times specifically)$$$$multiplying by $a!$ doesn't count those permutations

$\endgroup$
1
$\begingroup$

Your mistake is assuming that just because $a<p$ it means every color is used in every necklace.

That's not true. $a^p-a$ counts necklaces that use more than one color, and less than or equal to $a$ colors.

For example, if you take $p=5$, $a=4$, with colors Red, Blue, Green, Purple, then: "Red, Red, Blue, Blue, Blue" is counted in the $4^5-4$ necklaces.

Under permutation of colors and rotating the necklace, this necklace is equivalent to $5\cdot 4\cdot 3$ other necklaces.

But $5\cdot 4\cdot 3=60\neq p\cdot a!=120$. And we see that $\frac{4^5-4}{5}=204$ is not divisible by $a!=24$.


Of course, when $a\geq p$ you also get the problem - if you use $p$ distinct colors, you get that any rotation is also a color permutation. So there are just $a(a-1)\cdots(a-p+1)$ elements in the equivalence class of all necklaces using $p$ distinct colors.

We can prove combinatorially that $a(a-1)$ is a divisor of $a^p-a$.

$\endgroup$

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.