Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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$$
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}.$
