number of strings formed of k characters and length n

Question

You have been given a set of characters of size $k$ and you have to make strings of length $n$. How many strings are possible. A constraint is that every character must be used at least once in each such strings. For $n = k$ the answer is $k!$ I wanted it to generalize it for $k\leq n$, but i havent come up with any solution to it yet.

Answer 1

Hi, you can treat a word $x=x_1x_2\ldots x_n$ as a function $f:[n]\longrightarrow [k]$ where $x_i=f(i)$. So if you want that at least $1$ character, say $x_j$, to be equal to a symbol $a\in [k]$ for every symbol $a$, then you are looking for surjective functions. As a hint try to calculate all functions between $[n]=\{1,2,\ldots ,n\}$ and $[k]=\{1,2,\ldots ,k\}$and take out the ones that are not surjective (i.e. there exists $a\in [k]$ such that there is no $i\in [n]$ with $f(i)=a$).
Hope it helps.