# Senthilkumar Gopal

Musings of a machine learning researcher, engineer and leader

# Review of Combinatorics

In the study of combinatorics, there are three different structures - permutations, variations and combinations which are variations with subtle differences.

## Permutation

A typical question for permutation is “How many ways to arrange the three characters a,b and c?”. Note that the position and order matters for permutation and to fill all the positions. A permutation defines the numbers of different possible ways we can arrange a set of elements and can always arrange the entire set of elements in the sample space. Example: For a relay race, we can arrange 4-runners already chosen in 4-positions using permutations.

Permutations are arrangements of objects (with or without repetition), the order does matter.

Permutations without repetition if all elements are added and order does matter with no repetition of elements.

Pn = n!

Permutations with repetition if all elements are added and order does matter with repetition of elements being allowed.

$$P^{a,b,c...}_{n} = \frac{n!}{(a! \cdot b! \cdot c! ...)}$$

### Examples of Permutations

• Ways to put N items in a specific order.
• Different strings that can be built using the 26 alphabets such that each letter is used only once in a single string.
• Order in which N people can enter a door

## Variations (extension of permutation)

Variations can be considered an extension of permutation where variations determines the total number of ways we can pick and arrange some elements of a given set, with or without repetitions. Using the relay race example from above, if we had to choose 4-runners out of 6-runners in the team (6-runners | 4-positions), and then decide who runs in which lap (**pick & arrange), we would require using Variations.

Variations are arrangements of selections of objects, where the order of the selected objects matters.

Variations without repetition if not all the elements are added and order does matter with no repetition of elements.

$$V^n_{m} = \frac{m!}{(m - n)!}$$

Variations with repetition if not all elements are added if 𝑚 > 𝑛 and order does matter with repetition of elements being allowed. All elements can be added if 𝑚 ≤ 𝑛.

Vmn = mn

### Examples of Variations

• Ways, in which 3 out of 10 sports people can win a medal in a competition, the first winning gold, the next silver, and the third bronze.
• Possibilities to choose 2 representatives out of 100 students, one as the “president” and the other as the “vice-president”.
• Different results when rolling 3 dice which are distinguishable by color, e.g. white, red, and black dice.

## Combinations

The number of different ways we can pick a specific element of a set where the order in which the elements needs to be selected is also not important. Using the example of the relay race, if we only care about which 4-runners out of 6-runners made it into the team (pick) without any dependency on their position, we would be dealing with combinations and order is not relevant.

Combinations are selections of objects, with or without repetition, the order does not matter.

Combinations without repetition if not all elements are added and order does not matter where elements are not repeated.

$$C^n_{𝑚} = \frac{𝑚!}{𝑛! \cdot (𝑚−𝑛)!}$$

Combinations with repetition if not all elements are added and order does not matter where elements are repeated.

$$C^n_{𝑚} = \frac{(𝑚 + n -1)!}{𝑛! \cdot (𝑚−1)!}$$

### Examples of Combinations

• Ways, in which 3 out of 10 sports people can win a medal in a competition (no matter whether gold, silver, or bronze).
• Possibilities to choose 2 representatives out of 100 students, irrespective of the role.
• Different results when rolling 3 identical dice, irrespective of the order.