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
    :) sorry you lost the efforth you put on it – Makogan May 27 at 6:54
up vote 22 down vote accepted

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$$

  • Your reply was much better before, all you managed to do with the last edit is occlude meaning – Makogan May 27 at 20:38
  • @Makogan Ok I thiught it could be more clear in that way, I will roll back! – gimusi May 27 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}.$

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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