10
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

24
$\begingroup$

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

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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .