## PROBABILITIES Course

# Counting techniques / Combinatorics

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)$}).