0
$\begingroup$

The wikipedia entry on Permutations has this section on Permutations With Repetition:

Ordered arrangements of the elements of a set S of length n where repetition is allowed are called n-tuples, but have sometimes been referred to as permutations with repetition although they are not permutations in general. They are also called words over the alphabet S in some contexts. If the set S has k elements, the number of n-tuples over S is:

$${\displaystyle k^{n}}$$ There is no restriction on how often an element can appear in an n-tuple

That seems simple enough. But to make sure I understood, I wanted to go through a small example by hand. Consider S = {a,b} (so k=2) and n=3. So the number of ordered permutations should be 2^3 = 8. But it seems to me I can come up with >8:

  • a,a,a
  • a,a,b
  • a,a,c
  • a,b,a
  • a,b,b
  • a,b,c
  • a,c,a
  • a,c,b
  • a,c,c

...That's already 9 and I haven't started on anything starting with b or c yet. I'm sure I'm missing something obvious in my misinterpretation of this but not sure what it is. Any helpful explanation would be much appreciated!

$\endgroup$

1 Answer 1

2
$\begingroup$

You start with $S=\{a, b\}$ but then use $c$.

If $S=\{a, b, c\}$, then you should expect $3^3=27$ "permutations with repetition".

(I personally would not call something with repetitions a "permutation", rather a "sample with replacement" or similar.)

$\endgroup$
1
  • $\begingroup$ wow what a dumb mistake on my part. Thanks for the quick answer and suggestion on better nomenclature. $\endgroup$
    – Max Power
    Mar 11, 2020 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.