Coloring Hats on Cats Imagine I have $n$ indistinguishable cats and $k$ designs to color the hats on
those cats. Consider the case where $k \leq n.$ I want to figure out the
number of ways I can color the hats on these indistinguishable cats such that
each design shows up at least once.
I've been having some funky problems with trying to get this counting problem
right. I originally imagined that, given that the cats are indistinguishable,
We can first assign $k$ designs to $k$ of these cats 1 way and then
choose among the $k$ designs for each of the other $n-k$ indistinguishable
cats $k^{n-k}$. I assumed that we should divide this by the number of ways
we could permute those $n-k$ cats, since the order of assignment doesn't matter.
Thus, my original hypothesis for the counting proof was
$$\frac{k^{n-k}}{n-k}.$$
However, this hypothesis has failed on a number of inputs. Namely, when
$n=4$ and $k=2$, the number of ways should be 3, but this hypothesis says it
should be $2$. Does anyone have recommendations on how to go about this kind of
problem?
 A: Think of the hats as boxes. Now pick $k$ of the cats at random and place one into each box. That satisfies the requirement that each hat type be used at least once. Now how many ways can you arrange the remaining cats into the boxes? (Hint: "stars and bars").
A: Another  possible  approach  to  this  problem is  to  use  Burnside's
lemma. We have $n$ slots with the symmetric group $S_n$ acting on them
and color them with one of  $k$ colors where each color must appear at
least  once. This  means a  term from  the cycle  index  $Z(S_n)$ that
represents the product of $q$ cycles fixes
$${q\brace k} \times k!$$
assignments. Now the  number of permutations with $q$  cycles is given
by
$$\left[n\atop q\right].$$
It follows that the desired count has the closed form
$$\frac{1}{n!} \sum_{q=1}^n \left[n\atop q\right]
{q\brace k} \times k!.$$
Observe that
$${q\brace k} = q! [z^q] \frac{(\exp(z)-1)^k}{k!}$$
which yields for the sum
$$\frac{1}{n!} \sum_{q=1}^n \left[n\atop q\right]
q! [z^q] (\exp(z)-1)^k.$$
Observe furthermore that
$$\left[n\atop q\right] = 
n! [w^n] \frac{1}{q!} \left(\log\frac{1}{1-w}\right)^q$$
so we obtain
$$[w^n] \sum_{q=1}^n \left(\log\frac{1}{1-w}\right)^q
[z^q] (\exp(z)-1)^k.$$
Now the power of the logarithm starts at $w^q$ so we may extend $q$ to
infinity since  the values  beyond $n$ do  not contribute  to $[w^n]$,
getting
$$[w^n] \sum_{q\ge 1} \left(\log\frac{1}{1-w}\right)^q
[z^q] (\exp(z)-1)^k
= [w^n] \left(\exp\log\frac{1}{1-w}-1\right)^k
\\ = [w^n] \left(\frac{1}{1-w}-1\right)^k
= [w^n] \frac{w^k}{(1-w)^k}
\\ = [w^{n-k}] \frac{1}{(1-w)^k}
= {n-k+k-1\choose k-1} = {n-1\choose k-1}.$$
This is  of course the  same as what  we had in the  companion answer,
where   the  designs   are   $k$   boxes  and   we   place  a   single
indistinguishable cat  in each box and distribute  the remaining $n-k$
cats  into the $k$  boxes according  to stars  and bars,  getting with
$n-k$ stars and $k-1$ bars
$${n-k+k-1\choose k-1} = {n-1\choose k-1}$$
the same as before.
This   method  (Burnside)   also   appeared  at   this  MSE   link
I.   The first step
of  the   central  simplification  was   an  annihilated  coefficient
extractor. There are several more examples of this technique (ACE) at
this  MSE  link  II
and             at              this             MSE             link
III  and  also here
at                   this                   MSE                  link
IV.
A: Firstly, the problem with your calculation is that you're assuming that every different permutation of cats will have been counted separately in the original count, but this is only true if all the designs are different. For example, a case where all the cats were given the same design would only have been counted once to start with. 
Here's another approach. As the cats are indistinguishable, you might as well arrange them in a line with all the design 1s at one end, followed by the design 2s etc, where the designs are ordered in some predetermined sequence.  The allocation is defined simply by the places in the line where the design transitions from one design to the next. There need to be $k-1$ such changes of design and there are $n-1$ places where it can happen.
