Combinatorics- wheel of fortune

Question

In how may different ways can you color a wheel of fortune with five different colors, if it has 60 fields each containing a different value? Each color needs to be used at least once.

My answer is : $$\frac{60 \cdot 59 \cdot 58 \cdot 57 \cdot 56}{5!} \cdot 5! \cdot 5^{55}$$ First I chose $5$ fields out of $60$ to color with $5$ different colors then I paired the colors and the fields by multiplying by $5!$, and then for the $55$ remaining fields I can choose any of the $5$ colors so that is $5^{55}$. Not sure if that's correct.

Answer 1

You are over-counting because you may arrive at the same colouring in different ways (i.e., the picking of five fields in the first step is not unique).

Instead, there are $5^{60}$ colourings without the restriction. We have to subtract the cases where at last one colour is ignored, so we subtract $5\cdot 4^{60}$. But now we subtract all 3-colouring twice, hence add back ${5\choose 2}\cdot 3^{60}$. This is still wrong: 2-colourings were first counted, then subtracted threefold, then added back threefold, hence still need to be subtracted. So we subtract ${5\choose 2}\cdot 2^{60}$. Can you see, what correction you have to make regarding the ${5\choose 1}\cdot 1^{60}$ monochromatic colourings?

---

Alternatively, let $f(n,c,p)$ denote the number of ways to colour an $n$-set using exactly $c$ colours out of a $p$ colour palette. We are interested in $f(60,5,5)$. We have the recursion $$f(n+1,c,p)=f(n,c,p)\cdot c+ f(n,c-1,p)\cdot (p+1-c) $$ and the obvious boundary conditions $f(n,1,p)=1$. You can use this to obtain (or at least verify) a formula for $f(n,5,5)$.

Answer 2

If there were no restrictions, we could color the wheel in $5^{60}$ ways since there are five choices of color for each of the $60$ fields. From these, we must subtract those choices in which fewer than five colors are used.

There are $\binom{5}{k}$ ways to exclude exactly $k$ of the colors and $(5 - k)^{60}$ ways to color the wheel of fortune with the remaining $5 - k$ colors. By the Inclusion-Exclusion Principle, the number of ways to color the wheel with five colors so that each color is used at least once is \begin{align*} \sum_{k = 0}^{5} (-1)^k\binom{5}{k}(5 - k)^{60} & = \binom{5}{0}5^k - \binom{5}{1}4^{60} + \binom{5}{2}3^{60} - \binom{5}{3}2^{60} + \binom{5}{4}1^{60} - \binom{5}{5}0^{60}\\ & = 5^{60} - 5 \cdot 4^{60} + 10 \cdot 3^{60} - 10 \cdot 2^{60} + 5 \cdot 1^{60} - 0^{60} \end{align*} Your answer is larger than the $5^{60}$ possible ways to color the wheel. The problem is that you designated five particular fields to be of different colors. However, if red appears exactly $56$ times and each of the other colors appears once, there are $56$ ways to designate which of those $56$ fields is the designated red field, so you have counted that particular arrangement $56$ times. If each of the five colors appears $12$ times, there are $12$ ways to designate a particular field as the field of that color for each of the five colors, so you count such arrangements $12^5$ times.