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
    In the question is not specified but I think that we have an inexhaustible supply and the crown is circular2011-11-26
  • 0
    Make a little scratch on the crown just above a place for a jewel. Then there are $k^p$ ways to place the jewels on the scratched crown, including $k$ where the $p$ jewels are identical. Forget temporarily about those, and think of the remaining $k^p-k$. Now cover the scratch and rotate the crown.2011-11-26
  • 3
    Please include these details in your question so that others do not have to read deep into the comments to understand it.2011-11-26
  • 1
    @Austin Mohr: Crowns have spiky things on top, and must be quite uncomfortable worn upside down. Is there a King or Queen on Stack Exchange who can clarify things?2011-11-26
  • 0
    @AndréNicolas I suppose what I was thinking of is properly called a circlet: http://www.wulflund.com/images_items/medieval-gothic-circlet---brass-obsidian_3.jpg2011-11-26
  • 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?