If I have a set of numbers $\{1,2\}$ the permutations are $\{1,2\}$ and $\{2,1\}$. We can calculate the number of permutations using $\dfrac{n!}{(n-r)!} = \dfrac{2!}{0!} = 2$.
However, if I instead say I want to find all permutations of the set $\{1,2\}$ for a size $2$ with replacement (not sure if there is a more terse/less ambiguous name for this), then we get
$\{1,1\}, \{1,2\}, \{2,1\}, \{2,2\}$. The count is $4$. Is there a formula for calculating this?
Now imagine my set of numbers is $\{1,2,3\}$. If I want to find all permutations of the set $\{1,2,3\}$ for a size $2$ with replacement, I get
$\{1,1\}$
$\{1,2\}$
$\{1,3\}$
$\{2,2\}$
$\{2,1\}$
$\{2,3\}$
$\{3,3\}$
$\{3,1\}$
$\{3,2\}$
and the count is $9$.
Further, is there a simple derivation of the formula?
Best Answer
I've seen these called the $n$-tuples of $S$. The number of them is $|S|^n$, because there are $|S|$ options for each of the $n$ positions.
For example, $(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)$ are the $2$-tuples of $\{1,2,3\}$. Notice that there are $3^2=9$ of them.
Also, notice that I used (parenthesis) on these instead of $\{$set brackets$\}$, because we want the pairs to be ordered.