Counting techniques / Combinatorics

Go back

It's Dénombrement in French. We are using the cardinal a lot, so we must be able to count of many elements we got in a set.

Let's say we have

  • a set E having k elements
  • we are picking n elements in E

Note: no repetition/replacement means that's you once you picked a value in E, you are not putting it back. The size of E keeps decreasing.

Ordered: means that (0,1) and (1,0) are two different results while unordered means that they are the same issue. When writing an ordered set, we write {$(0,1), (1,0)$} while we would do { {$0,1$} } for the same set but unordered.

We are distinguishing

  • Permutations: shuffle of your set
  • Arrangement $A^k_n$: randomly picking elements, order matter
  • Combination $C^k_n$: randomly picking elements, order do not matter

Ordered distribution (no repetition/replacement)

Since k is decreasing by 1, it's a factorial ($5!=5*4*3*2*1$).

@ A^k_n = \frac{k!}{(k-n)!} @

When $k = n$, $A^k_n = k!$ and we are calling these permutations. When the ordered elements are presents multiples times inside the set, you can't simply use $k!$, and you need to divides by the number of occurrences ($o_i$) of each value ($i$)

@ \frac{n!}{\prod_i o_i!} @

The most used example is "how many words can we create with the letters of Mississippi?".

  • we got 1 M ($o_1$)
  • we got 4 I ($o_2$)
  • we got 4 S ($o_3$)
  • we got 2 P ($o_4$)
  • we got 11 letters

@ \frac{11!}{1! * 4! * 4! * 2!} @

Ordered distribution (with repetition/replacement)

@ k^n @

Each value can be picked $n$ times. You must make sure that you are not inverting $k$ and $n$.

unordered distribution (no repetition/replacement)

@ \frac{k!}{(k-n)!} * n! \Leftrightarrow A^k_n * n! @

It's the same as "Ordered distribution (no repetition/replacement)" but we multiply by $n!$.

unordered distribution (with repetition/replacement)

@ C^{k-1}_{n+k-1} = \frac{(n+k-1)!}{(k-1)! * n!} @

If we have $n=2$ having $[1,5,7]$ so $k=3$ then we have

@ C^{3-1}_{2+3-1} = 6 @

The 6 results are {$1,5$}, {$1,7$} and {$5,7$} (remember that {$1,5$} is the same as {$(1,5),(5,1)$}).