Given an alphabet of size $n$, how many strings of length $c$ contain every single letter of the alphabet at least once?
I first attempted to use a recurrence relation to work it out:
$$ T(c) = \left\{ \begin{array}{cr} 0 &\mbox{ if $c<n$} \\ n! &\mbox{ if $c = n$} \\ T(c-1) \cdot n \cdot c &\mbox{ if $c > n$} \end{array} \right. $$
As there's no strings that contain every letter if c < n, and if c = n then it's just all permutations. When c > n you can take any string of size (c-1) that contains all letters (of which there are $T(c-1)$ to choose from), you choose which letter to add (of which there are $n$ choices) and there are $c$ different positions to put it. However, this gives out results that are larger than $n^c$ (the total number of strings), so it can't be right, and I realised it was because you could count some strings multiple times, as you can make them taking different inserting steps.
Then I thought about being simpler: you choose n positions in the string, put each letter of the alphabet in one of those positions, then let the rest of the string be anything:
$$ {c\choose{n}} \cdot n! \cdot n^{c-n} $$
But again this counts strings multiple times.
I've also considered using multinomial coefficients, but as we don't know how many times each letter appears in the string it seems unlikely they would be much help. I've also tried several other methods, some complicated and some simple, but none of them seem to work.
How would you go about working out a formula for this? I'm sure there's something simple that I'm missing.