While working with algorithm, you may have to calculate on the fly the number of possibilities created by some subset of data. Particularly when debugging with your rr elements from nn dynamic objects. Let’s take a refresh our memories!

Permutations and combination are part of the Combinatorics which is an area of mathematics about counting. A permutation is an arrangement of selected ordered items, while a combination only concerns the selection of item.

Basics refresher

Let’s review the fundamental, just to be sure we are on the same line when reviewing the following formulas. See math can be useful, to do … more math, ahem, let’s get started. 🙉

Factorial

The factorial function is noted n!n! which represent the multiplication of all whole numbers in N\N starting from 1,2,3,...n1, 2, 3, ... n.

For example, factorial of 4 would be calculated such as:

4!=4×3×2×1=24\begin{equation} \begin{split} 4! &= 4 \times 3 \times 2 \times 1 \\ &= 24 \nonumber \end{split} \end{equation}

The special case with 0!=10! = 1 😲:

  • You can write factorial such as n!=n×(n1)!n! = n \times (n-1)!
  • Meaning 1!=1×0!1! = 1 \times 0! so it means that 0!=10!=1 to stay consistent.

Exponentiation

There’s also the exponentiation, sometimes called power function which is noted bnb^n for bb raised to the power of nn.

For positive numbers, when nn is in N\N, we have bnb^n corresponding to multiplication of nn times the base bb. For example 22 raised to the power of 44 would be calculated such as:

24=2×2×2×2=16\begin{equation} \begin{split} 2^4 &= 2 \times 2 \times 2 \times 2 \\ &= 16 \nonumber \end{split} \end{equation}

Notes about exponents:

  • Noticeable cases for one; b1=bb^1 = b and zero; b0=1b^0 = 1
  • Using negative exponents; b1=1bb^{-1} = \frac{1}{b}
  • Arithmetic operations; bx+by=bx+yb^x + b^y = b^{x+y}

Combinatorics

Now that we have our bases refreshed to the power of knowledge, we can factor it to our next three topics! Let’s “Q.E.D.” (_quod erat demonstrandum) those formulas and feel smart about it. 🤓

Permutation

Introduction

When the order does matter you want to calculate the possible permutations. Let’s say you have a set of nn objects, and you choose kk times from it.

(A,B,C)n=3(A,B),(A,C)k=2,(B,A),(B,C),(C,A),(C,B)6 permutations\overbrace{(\textcolor{#ea008e}{A}, \textcolor{#007cdb}{B}, \textcolor{#00d9c2}{C})}^{\text{n=3}} \Rightarrow \underbrace{(\textcolor{#ea008e}{A}, \textcolor{#007cdb}{B}), \overbrace{(\textcolor{#ea008e}{A}, \textcolor{#00d9c2}{C})}^{\text{k=2}}, (\textcolor{#007cdb}{B}, \textcolor{#ea008e}{A}), (\textcolor{#007cdb}{B}, \textcolor{#00d9c2}{C}), (\textcolor{#00d9c2}{C}, \textcolor{#ea008e}{A}), (\textcolor{#00d9c2}{C}, \textcolor{#007cdb}{B})}_{\text{6 permutations}}

There is nn, then n1n-1, … items to choose from, until you have kk items selected. In the end you end up with nkn-k items that are not selected.

Calculation

This looks like a factorial, so choosing kk different items out of the nn possible, is the same as having the kk factorial from nn to nkn-k. Which can be written as:

n!=n×n1×...×n(k1)×nk×...×1=n×n1×...×n(k1)number of permutations×(nk)!\begin{equation} \begin{split} n! &= n \times n-1 \times ... \times n-(k-1) \times n-k \times ... \times 1 \\ &= \underbrace{n \times n-1 \times ... \times n-(k-1)}_{\text{number of permutations}} \times (n-k)! \nonumber \end{split} \end{equation}

Let’s isolate the amount of permutations on one side of the equation 🤔
dividing by (nk)!(n-k)! to get:

n!(nk)!=n×n1×...×n(k1)×(nk)!(nk)!=n×n1×...×n(k1)×(nk)!(nk)!=n×n1×...×n(k1)number of permutations\begin{equation} \begin{split} \frac{n!}{(n-k)!} &= \frac{n \times n-1 \times ... \times n-(k-1) \times (n-k)!}{(n-k)!} \\ &= \frac{n \times n-1 \times ... \times n-(k-1) \times \cancel{(n-k)!}}{ \cancel{(n-k)!}} \\ &= \underbrace{n \times n-1 \times ... \times n-(k-1)}_{\text{number of permutations}} \nonumber \end{split} \end{equation}

So now we can write the formula to find the amount of permutation PknP_k^n for kk selection in nn objects such as:

Pkn=n!(nk)!P_k^n=\frac{n!}{(n-k)!}

We can see that in the case where k=nk=n we have a division by 0!0! and Pnn=n!P_n^n=n!

For an example where n=5n=5 and k=3k=3, we can use it such as 5!(53)!=60\frac{5!}{(5-3)!}=60. With repetition (picking the same object more than once in your set), you have nkn^k possible permutations.

Combination

Introduction

When the order does not matter you want to calculate possible combinations. There will be fewer combinations possible for a given kk selections in nn items than the permutation.

Let’s have an example for n,k=3n,k=3, we’d have one combination but six permutations:

(A,B,C)1 combination(A,B,C)(B,C,A),(C,A,B),(A,C,B),(C,B,A),(B,A,C)6 permutations\underbrace{(\textcolor{#ea008e}{A}, \textcolor{#007cdb}{B}, \textcolor{#00d9c2}{C})}_{\text{1 combination}} \Leftrightarrow \underbrace{(\textcolor{#ea008e}{A}, \textcolor{#007cdb}{B}, \textcolor{#00d9c2}{C}) (\textcolor{#007cdb}{B}, \textcolor{#00d9c2}{C}, \textcolor{#ea008e}{A}), (\textcolor{#00d9c2}{C}, \textcolor{#ea008e}{A}, \textcolor{#007cdb}{B}), (\textcolor{#ea008e}{A}, \textcolor{#00d9c2}{C}, \textcolor{#007cdb}{B}), (\textcolor{#00d9c2}{C}, \textcolor{#007cdb}{B}, \textcolor{#ea008e}{A}), (\textcolor{#007cdb}{B}, \textcolor{#ea008e}{A}, \textcolor{#00d9c2}{C})}_{\text{6 permutations}}

The combination is usually noted (nk)\binom{n}{k} or CknC_k^n.

Calculation

To remember the formula, there’s a little trick. In our example for k=nk=n there are 6 times more permutations than combination. This corresponds to the number of possible arrangement, i.e. the factorial of the number of selection.

Which can be extrapolated into k!k! more permutations than combinations.
So the combination formula can be written such as:

Ckn=n!k!(nk)!C_k^n=\frac{n!}{k!(n-k)!}

Combinations’ properties:

  • Special value of kk with C0n=Cnn=1C_0^n=C_n^n=1 and C1n=Cn1n=nC_1^n=C_{n-1}^n=n
  • Pascal’s rule: Ckn+Ck1n=Ckn+1C_k^n+C_{k-1}^n=C_k^{n+1}

For repetitions, it means you can pick the same item three times like in (A,A,A)(\textcolor{#ea008e}{A}, \textcolor{#ea008e}{A}, \textcolor{#ea008e}{A}) or two times like in (B,B,C)(\textcolor{#007cdb}{B}, \textcolor{#007cdb}{B}, \textcolor{#00d9c2}{C}).

To find the amount of combination possible with repetition, there are multiple tricks to remember it:

  • One way: It’s to count the amount of time you pick an item kk and the amount of time you skip an item n1n-1 (because at least one item must be picked which will be used for all kk selections).
  • Another way: It’s to sum possible items nn with the possible amount of time they can be repeated in the selection k1k-1.

Meaning it’s like doing the combination for (k+n1k)=(k+n1)!k!(n1)!\binom{k+n-1}{k}=\frac{(k+n-1)!}{k!(n-1)!}.

Multiplication

Introduction

Let’s figure out the possibilities from these three sets:

(A1,A2)A,(B1,B2,B3)B,(C1,C2,C3)C\overbrace{(A1, A2)}^{\text{\textcolor{#ea008e}{A}}}, \overbrace{(B1, B2, B3)}^{\text{\textcolor{#007cdb}{B}}}, \overbrace{(C1, C2, C3)}^{\text{\textcolor{#00d9c2}{C}}}

The number of element of one set is also called cardinalilty noted as A|A| or card(A)card(A), they differ between each set. Meaning we have 3 choice and each one have respectively 2, 3, 3 possible options such as each possibility can be noted as a set of one element from A\textcolor{#ea008e}{A}, B\textcolor{#007cdb}{B} and C\textcolor{#00d9c2}{C} such as:

(A2,B1,C3)one possible arrangement\underbrace{(A2, B1, C3)}_{\text{one possible arrangement}}

In this case there’s no need to try to apply the previous permutation or combination formula.

Calculation

The simplest way to calculate the possibility between asymmetric subsets is called the rule of product. I like the Cartesian product notation:

{A×B={(a,b)  aA,bB}\{ A\times B = \{ (a,b)~|~a \in A, b \in B \}

The product of two set AA and BB is another set composed of pairs (a,b)(a, b) where aa is an element of AA and bb one of BB. So for our three disjointed sets presented earlier, there’s A×B×C|\textcolor{#ea008e}{A}| \times |\textcolor{#007cdb}{B}| \times |\textcolor{#00d9c2}{C}| possible permutations, in our case it amounts to 1818.

Words of wisdom

That’s it! Let’s use our new-found knowledge soon when working with multiple datasets, arrays or any other type of weird data structures.

As a side note, I would prefer saying combinatronics 🤖 instead of combinatorics, it sounds way better in my opinion. Feeling like we’re in some sci-fi 80’s scientific cliché.