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!