Combinatorics

This is the branch of mathematics that deals with permutations and combinations. In this page, I only try to build mental models such that the concepts are 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 is permutation is enough to build a strong mental model. Here, this means the order of things matter. Any change of order will mutate the arrangement.

The formula of permutation also reflects the same. If there are N available choices and we need to build permutations of size K. In this case, for first position, we've N options, for second position we've N-1 and then N-2, until 1.

So the number of permutations possible is, $N \times N-1 \times N-2 ...$ until K positions are filled. The formula exactly does this. Takes the full factorial of the available choices and removes all unused positions by dividing it. It means, when the problem statement only asks for K permutations(positions) from N available choices, the remaining N-K positions are simply removed from the result.

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

Permutations with repetition

Even though permutation always speaks about order of items and also formula doesn't allow repeating items, this isn't always true.

Permutations with repetitions is an important use case. For example, when we've a 3 digit number lock, the numbers can be repeated. This means, the above formula isn't valid for finding the number of permutations possible. So every position has all options to chose from. This means, if you have 10 choices to fill in 3 positions then we've $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 in day-to-day life that it's easy to remember based on examples.

• 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.

Combination formula is same as permutation one but additionally it removes the possible duplicates since order doesn't matter here.

$$\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 important topic that sounds similar to this is the subset. This confuses since the concepts are very similar. Subsets are similar to combination but only difference is the size. A subset can have no elements to all elements.

Size of possible subsets - Power set

For a given set of elements with size N, the possible subsets is always $2^N$.

This is also called a power set since it contains the original set as well as 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).$