1

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?

mathematics2x2life
  • 13,322
friartuck
  • 145

1 Answers1

2

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.

Alexander Gruber
  • 26,963
  • yeah i was just coming on to post the formula is simply |S|^n after I realised one way to get them is to 'count up' like you would in binary or decimal. Despite having an engineering degree with a fair amount of math I don't think it ever clicked between {} meaning set vs () for ordered tuple. That is what you were getting at in your last point right? – friartuck May 12 '20 at 04:23
  • 2
    Yes. For example, $(1,2)$ is different from $(2,1)$, but ${1,2}$ is the same thing as ${2,1}$. With parenthesis, order matters; with set brackets, it doesn't. – Alexander Gruber May 12 '20 at 04:26
  • thanks for your input. consider question answered. thanks again – friartuck May 12 '20 at 18:25