TITLE: All distinct k-permutations of length n, with repetitions
QUESTION [2 upvotes]: Given $n$ elements 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$ distinct symbols (i.e., $k$-permutations of length $n)$. Each symbol is equally likely to be picked and there are no restrictions on the number of repetitions for each symbol.
As a related problem, let the exact number of repetitions, $x_1, x_2, \dots, x_k$, for each of the $k$ symbols be given, such that $x_1$ gives the exact number of repetitions for the first symbol picked (which can be any of the $n$ symbols). In general, $x_i$ gives the exact number of repetitions for $i^{th}$ selected element. Hence, $x_i$ gives only the (exact) count of duplicates and it says nothing about the symbols picked. In such scenario, the answer should be given by:
\begin{equation}
  \dfrac{P_{n,k}\cdot k^{n-k}}{|x_1|\cdot |x_2| \cdot \dots \cdot |x_k|}
\end{equation}
But, the main problem in consideration does not give the count of the number of duplicates. Also, as mentioned earlier, the $k$ symbols are not fixed, and each symbol is equally likely to be picked. Thus, I am trying to figure out a formula, which given the value of $n$ and $k$, computes all distinct $k$-permutations of length $n$, without any restriction on the repetitions/duplicates or the selection. 
How I got to the aforementioned formula: First, we select $k$ out of $n$ elements. As the order matters, the number of ways to do this is given by $P_{n,k}$. For the rest of the $n-k$ empty spots, the selection is done from the same set of $k$ symbols. Hence, $k^{n-k}$ ways to do so! Finally, as we know the exact number of repetitions for each of the $k$ symbols, we use that information to avoid overcounting. I included the related problem and the equation/formula to improve the clarity on the main problem and the goal. 
Thanks for your help!

REPLY [1 votes]: Fix an amount of repetitions for each symbol $r_i \geq 1$, for each $i \in [k]$. Since we want our permutations to have exactly $k$ symbols, $r_1 + \dots+ r_k = n$. Now, given this information, how many permutations can we form? First off, we can fix $r_1$ of the $n$ elements, and place the first symbol (this way, we do not overcount swapping the order of this places). For the remaning $n - r_1$, we again pick $r_2$ of them to place the second symbol; and so on. That is, we have the following amount of possibilities: 
$$
{n \choose r_1}{n-r_1 \choose r_2}\cdots{n - r_1 - \dots r_{k-2} \choose r_{k-1}} = {n \choose r_1, \dots r_k}
$$   
so the total amount of possibilities is:
$$
\sum\limits_{r_1 + \dots + r_k = n \\ \quad r_i \geq 1 \ (\forall i)}{n \choose r_1, \dots r_k} 
$$
Perhaps this can be made more explicit by noting that
$$
\sum_{r_1 + \dots + r_k = n}{n \choose r_1, \dots r_k} = \sum_{r_1 + \dots + r_k = n}{n \choose r_1, \dots r_k}1^{r_1}\cdots1^{r_k} = (1 + \dots + 1)^n = k^n
$$
{"set_name": "stack_exchange", "score": 2, "question_id": 2838020}