Closed-form expression for the number of $k$-permutations of length $n$. Duplicates allowed!

Question

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!

Answer 1

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$$

Answer 2

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\;. $$