Combinatorics

When we want to study the possible combinations of objects selected from a group we use $\color{#ff4f4f} combinatorics$.

🔴🟠🟡🟢🔵🟣

As an example, we can say we select two colors from this arrangement. We can start with any of the available colors, therefor we have 6 options 🔴,🟠,🟡,🟢,🔵,🟣.

Let's say we select the red color 🔴, then we have any of the next options 🟠🟡🟢🔵🟣, which makes 5 different options. 🔴🟠, 🔴🟡, 🔴🟢, 🔴🔵, 🔴🟣. This is the case had we chosen any of the first colors.

We see then that first, we choose from the 6 colors available, so 6 options. For the next step we only choose out of 5 options, so it is 6·5 = 30 options we could have chosen at this point. This pattern continues if we follow these steps any further.

Choosing $k$ among $n$ items without considering the order in which they are chosen is called $\color{#ff4f4f} combination$.

We represent this using the $\color{#ff6f49} binomial$ $\color{#ff6f49}coefficient$ notation:

\color{#ff8b48}
 \binom{n}{k} = \prod_{i=[0,k[} n-i = \underbrace{n(n-1)(n-2)...}_{k\;  factors}

which we read " $n$ $choose$ $k$".

In our case $\binom{6}{2}$

Arrangement

Now we want to know in how many ways can we order our 6 colors. 🔴🟠🟡🟢🔵🟣,🔴🟡🟢🔵🟠🟣,🟢🔴🟡🔵🟠🟣, etc..

We start with any color as our first, this is 6 options. Then we have one fewer color to choose from, so we have 5 options. We then have 4 options, then 3, two, and only one option left for our last color.

This gives us 6·5·4·3·2·1 = 720 different possibilities.

We represent this with Factorial Notation

\color{#ffa54e}
n! = \prod_{i=1}^{n} i = n(n-1)(n-2)...(3)(2)(1)

Ordered selection: Permutation

An ordered selection is when we select a number of elements from a group in a particular order.

The best example of this is a race. When, let's say, 10 kids race and we select gold, silver, and bronze. We ask ourselves, how many different ways can the podium turn out?

Well, the different possible patterns in the podium is divided into two parts:

• How many ways can we choose 3 kids from 10?
  • We have seen this with $\binom{n}{k}$ combinations.
• How many ways can we arrange these 3 kids on the podium?
  • We have seen this with $p!$ arrangements

We can see that working together these concepts show that we can select $k$ ordered elements from any group of $n$ elements by calculating the options as $\binom{n}{k}k!$

The answer, then, is $\binom{10}{3} · 3!$ = 120·6 = 720

With the colors above we can make palettes of colors that show 4 colors in a certain order. How many different palettes can we make?

The answer is $\binom{6}{4} · 4!$ = 15·24 = 360 different palettes we can make.

Choosing elements in a certain order creates a $\color{#ffbe5a}Permutation$.

The number of possible Permutations of $k$ objects chosen among $n$ objects is written as

\color{#fcd56d}
_nP_k

\color{#f9ea85}
_nP_k = \binom{n}{k} · k!

We also can express the binomial coefficient as follows:

\color{#f6ffa1}
\binom{n}{k} = \frac{n!}{k!·(n-k)!}

therefor

\color{#ff6bc9}
_nP_k = \frac{n!}{(n-k)!}