Combinatorics

This is the branch of mathematics that deals with permutations and combinations. On this page, I just build mental models to make the concepts easier to remember.

position vs choice - important terms

• position - Assigning items to different positions.
• choices - Which items are available for assigning items.

Permutations

Permutation is an arrangement of objects where the order does matter. Every order is a different permutation.

Mental model using the name

The word mutation in permutation is enough to build a strong model. It means the order matters. Any change of order mutates the arrangement.

The formula shows the same. Say there are N choices and you build permutations of size K. For the first position, you have N options. For the second, N-1. Then N-2, down to 1.

The number of permutations is $N \times N-1 \times N-2 ...$ until K positions are filled. The formula does just this. It takes the full factorial of the choices. Then it divides out the unused positions. When you want only K positions from N choices, the remaining N-K positions are removed from the result.

$$_n P_k = \frac{n!}{(n-k)!}$$

Permutations with repetition

Permutation is about order, and the formula doesn't allow repeats. That isn't always true, though.

Permutations with repeats is an important case. For example, a 3 digit number lock can repeat numbers. The formula above doesn't apply here. Every position has all the options. With 10 choices for 3 positions, you have $10 \times 10 \times 10$ permutations.

$$_n P_r = n^r$$

Combinations

Combination is a selection of objects where the order doesn't matter. Every order is the same combination.

Mental model using the name

The word combination is used so much daily that examples make it easy to remember.

• Color combination - we just say the same colors in any order make the same combination.
• Food combination - again, the same food items in any order make the same combination.
• Clothing combination - same clothes in any order make the same combination.

The combination formula is the same as the permutation one. It also removes the duplicates, since order doesn't matter.

$$\begin{aligned} _n C_k = \frac{n!}{k!(n-k)!} \text{ - this is same as permutation with extra division to group all permutations of same combination into one.}\\ _n C_k = \frac{permutations}{\text {Number Of Permutations Per Combination}} \text{ - The above formula is just same this.}\\ \end{aligned}$$

Combination is permutations with grouping

We group all permutations into groups, where each group corresponds to one unique combination of the items.

Division is nothing but grouping. This is exactly what happens here.

Subsets

Another topic that sounds similar is the subset. It confuses because the ideas are close. A subset is like a combination. The only difference is the size. A subset can have from no elements to all elements.

Size of possible subsets - Power set

For a set of size N, the number of subsets is always $2^N$.

This is also called a power set. It contains the original set and an empty set.

Let the set be $S = \{a, b, c\}.$

1. Subsets (all sizes): $\emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}.$

2. Combinations (size 2):$\{a,b\}, \{a,c\}, \{b,c\}.$

3. Permutations (size 2):$(a,b), (b,a), (a,c), (c,a), (b,c), (c,b).$