Closed-form expression for the number of $k$-permutations of length $n$. Duplicates allowed! Given $n$ symbols and an integer $k > 0~(k \leq n)$, find the number of all distinct strings of length $n$, formed by any $k$-out-of-$n$ symbols, i.e., the target strings consist of exactly $k$ distinct symbols out of the given $n$ symbols. There are no restrictions on the number of repetitions allowed for each symbol.
Given $n$ and $k$, the goal is the derive a closed-form expression or upper and lower bounds on the count of all such (distinct) $k$-permutations.
Eg. Let S={a,b,c} be a set of n=3 elements. For k=2, the distinct 2-permutations of length 3 are: aab, aba, abb, baa, bab, bba, aac, aca, acc, caa, cac, cca, bbc, bcb, bcc, cbb, cbc, ccb. Hence, 18 distinct strings of length 3 are formed by 2-out-of-3 symbols.
Thanks for your help!
 A: Like joriki, I will denote the alphabet size with $m$ and the string length with $n$.
Choose $k$ distinct symbols $c_1,\ldots,c_k$
from the available $m$ symbols. The labels shall matter, so there are
$m\,(m-1)\cdots(m-k+1) = k!\binom{m}{k}$ ways to do this.
Independently, partition the set $\{1,2,\ldots,n\}$ of indices into a
length-$n$ string into exactly $k$ nonempty subsets $S_1,\ldots,S_k$
where the labels (i.e. permutations of the $S_j$) do not matter.
Therefore, we can prescribe some ordering of the $S_i$, e.g. by their
minimal elements, that is, $\min(S_i) < \min(S_j) \iff i<j$.
There are exactly $\left\{n\atop k\right\}$ ways to do that
where $\left\{n\atop k\right\}$ is a Stirling number of the second kind.
For every $i\in\{1,\ldots,k\}$, put the symbol $c_i$ at the string
position(s) listed in $S_i$. This approach gives every valid string exactly
once, and we get
$$k!\binom{m}{k}\left\{n\atop k\right\}$$
ways in total.
Note that this matches @joriki's answer because
$$\sum_{j=0}^k(-1)^j\binom{k}{j}(k-j)^n = k!\left\{n\atop k\right\}$$
[Graham/Knuth/Patashnik: Concrete Mathematics, 2nd ed., eq. (6.19);
also given in the Wikipedia entry]
In your example, $(k,m,n) = (2,3,3)$, and we get indeed
$$k!\binom{m}{k}\left\{n\atop k\right\} = 2!\binom{3}{2}\left\{3\atop 2\right\}
= 2\cdot 3\cdot 3 = 18$$
A: There are $j^n$ strings of length $n$ that contain at most $j$ particular symbols. Then by inclusion–exclusion the number of strings of length $n$ with exactly $k$ distinct symbols chosen from $m$ symbols is
$$
\binom mk\sum_{j=0}^k(-1)^j\binom kj(k-j)^n\;.
$$
You can set $m=n$ to obtain your special case in which the string length coincides with the size of the alphabet.
In your example, $m=n=3$ and $k=2$, so this becomes
$$
\binom32\sum_{j=0}^2(-1)^j\binom2j(2-j)^3=3\left(2^3-2\cdot1^3+0\right)=18\;.
$$
