Combinatorics Cheat Sheet

Question

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.

Answer 1

Permutations, Derangements, Combinations, Pigeonhole-principle, inclusion exclusion, etc.

Answer 2

The case you wish to add is combinations with repetition, the number of ways of distributing $n$ identical objects into $k$ distinct boxes. The number of ways the objects can be distributed to the boxes is the number of solutions of the equation $$x_1 + x_2 + x_3 + \cdots + x_k = n$$ in the nonnegative integers. A particular solution corresponds to the placement of $k - 1$ addition signs in a row of $n$ ones. For instance, if $n = 9$ and $k = 4$, $$1 1 + 1 1 1 1 + + 1 1 1$$ corresponds to the solution $x_1 = 2$, $x_2 = 4$, $x_3 = 0$, and $x_4 = 3$. Therefore, the number of such solutions is the number of ways we can select which $k - 1$ of the $n - k + 1$ positions (for $n$ ones and $k - 1$ addition signs) will be filled with addition signs, which is $$\binom{n + k - 1}{k - 1}$$
This number also counts the number of ways of selecting $n$ objects from $k$ types of objects when there are at least $n$ objects available of each type.