0
$\begingroup$

Could you help me, please, to Compute the number of different ways there are to put jewels of $k$ different kinds on a crown with $p$ identical places for jewels, with $p$ a prime?

  • 0
    @AndréNicolas: True for most crowns, but not always: e.g., [the Iron Crown of Lombardy](http://en.wikipedia.org/wiki/Iron_Crown_of_Lombardy). – 2011-11-26

1 Answers 1

4

First, assume the jewels are placed on a strip rather than a crown.

You are placing jewels in $p$ slots, repetitions allowed, order matters. There are $k$ possibilities for the first slot, $k$ possibilities for the second slot, etc. That gives $k^p$ ways to arrange the jewels in a strip.

Now you are going to take that strip, and fold it into a loop so that you get a circular crown. However, there are many different strip-arrangements that lead to the same circular crown arrangement. For example, if you have a diamond followed by $p-1$ rubies, you get the same crown as if you have one ruby followed by a diamond, followed by $p-2$ rubies; and the same as if you have two rubies, a diamond, and then $p-3$ rubies, etc. Basically, you can "cyclically shift" the jewels along the strip (push every jewel one slot forward, then take the last jewel and place it first) and get the same crown in the end.

So we need to figure out how many times we counted each "final arrangement."

If all the jewels are the same, we just counted it once: all cyclical shifts just give the same arrangement again. What if not all jewels are the same?

Now the fact that $p$ is prime is important: suppose that not all jewels are the same; can you start with one arrangement, shift it cyclically (say, by $\ell$ slots), and end up with an arrangement that is identical to the one you started with? If yes, you are going to have to be careful again in counting. If "not", then how many times did you count each such arrangement?