# number of strings formed of k characters and length n

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.

• Use Inclusion/Exclusion. For more details, please see Stirling numbers of the second kind, and the Twelvefold Way (onto functions from an $n$-element set to a $k$-element set). – André Nicolas Dec 26 '14 at 21:05

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$).
• Hi, those are functions $f:X\longrightarrow Y$ such that for every single $y\in Y$ there is an $x\in X$ such that $f(x)=y$. In other words, the function $f$ goes to every possible element of $Y$. – Phicar Dec 26 '14 at 21:11