[Math] Combinatorics Cheat Sheet

combinationscombinatoricsfactorialpermutations

I want to put together a combinatorics cheat sheet and I want to get started with the basic counting formulas. After some reviewing one could easily conclude that order and repetitions of the elements in sequences of interest could be a good start to categorize counting formulas.

I have started by reviewing the basics (cf. 1):

A weaker meaning of the term "permutation" (…) designates those
ordered arrangements in which no element occurs more than once, but
without the requirement of using all the elements from a given set.
Indeed, this use often involves considering arrangements of a fixed
length $k$ of elements taken from a given set of size $n$, in other
words, these $k$-permutations of $n$ are the different ordered
arrangements of a $k$-element subset of an $n$-set (sometimes called
variations in the older literature)
. (…) The number of such is
denoted variously by such symbols as $P^n_k$, and its value is given
by the product: $$ P(n,k) = P^n_k = \frac{n!}{(n – k)!} $$

In summary, we can permute all of the elements of a set $S$ with cardinality $|S| = n$. We can also take a variation, in where we permute only $k$ elements out of the $n$ possible elements from $S$. Here, we account for order but disregard repetitions.

This usage of the term "permutation" is closely related to the term
"combination". A $k$-element combination of an $n$-set $S$ is a $k$
element subset of $S$, the elements of which are not ordered. By
taking all the $k$ element subsets of $S$ and ordering each of them in
all possible ways we obtain all the $k$-permutations of $S$. The
number of $k$-combinations of an $n$-set, $C(n,k)$, is therefore
related to the number of $k$-permutations of $n$ by:
$$ C(n,k) = \frac{P(n,k)}{P(k,k)} = \frac{n!}{(n-k)!\,k!} $$

So, for combinations we now disregard order.

Finally, we have (cf. 1):

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: $$ k^n $$

Therefore, it seems like the following preliminary version of the cheat sheet makes sense:

  • YES order, YES repetitions: $k^n$
  • YES order, NO repetitions: $P^k_n$
  • NO order, NO repetitions: $C(n,k)$

However, what about the final case? What if we want to disregard order but preserve repetitions? I am inclined to take
$$
P(n,n) = n!
$$
but I am not sure.