There are 4 basic combinatoric formulas when picking $k$ elements among $n$

We have repetition is allowed or not allowed, and order matters or does not matter.

When order matters and repetition is not allowed we call it a permutation.

When order does not matter and repetition is not allowed we call it a combination.

What are the names of the missing two and what are the formulas for each?

  • 1
    $\begingroup$ :) sorry you lost the efforth you put on it $\endgroup$ – Makogan May 27 '18 at 6:54

We have the following cases for the number of subsets of size $k$ chosen from a set of $n$ distinct elements:

  • replacement and ordered, "permutation with repetition" $$n^k$$

  • no replacement and ordered, "k-permutations of n" $$\frac{n!}{(n-k)!}$$

  • no replacement and unordered, "combinations" $$\binom{n}k$$

  • replacement and unordered, "combination with repetitions" $$\binom{n+k-1}k$$

| cite | improve this answer | |
  • $\begingroup$ Your reply was much better before, all you managed to do with the last edit is occlude meaning $\endgroup$ – Makogan May 27 '18 at 20:38
  • $\begingroup$ @Makogan Ok I thiught it could be more clear in that way, I will roll back! $\endgroup$ – user May 27 '18 at 20:45

When order matters and repetition is allowed, you get all the functions from $\{1,2, \cdots, k\}$ to your set $S$ of $n$ elements. Every function corresponds to a unique choice, and every choice allows you to construct a function by setting $f(r)$ to be the $r^{th}$ element chosen. The formula for these is simpler, just being $n^k,$ because we have a full $n$ independent choices to make, $k$ times in a row.

Perhaps the most complicated of the four is when repetition is allowed but order does not matter. Those are called multisets. There is an explicit formula for $n$ multichoose $k$ given by $\left( {n \choose k}\right) = {n+k-1 \choose k}.$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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