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!

• Think of the strings as functions from $[n]=\{1,2,3,...,n\}$ to $[k]$ – saulspatz Jul 4 '18 at 13:08
• @joriki I added equally likely portion just to add more clarity to the question. And there is not particular reason for the length of the strings and the total number of symbols being the same. They may be different! – Novice Geek Jul 4 '18 at 13:33
• In my view, talking about likelihood when there's in fact no randomness reduces rather than increases the clarity of the question. If you want to allow the string length and the alphabet size to differ, you shouldn't use the same variable name for them. – joriki Jul 4 '18 at 13:35
• – Xander Henderson Jul 17 '18 at 20:15
• @XanderHenderson: It seems to me that there may be a difference between this Question and the proposed duplicate, turning on whether exactly $k$ letters must appear in those "permutations with repetitions". Not having to account for all $k$ letters appearing really makes the problem easier, and I have no doubt that another duplicate exists in the Math.SE corpus. – hardmath Jul 18 '18 at 2:03

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

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

• The sum can be expressed in terms of a Stirling number of the second kind. That has made me wonder about a combinatorial interpretation. Found it. – ccorn Jul 4 '18 at 15:08