Counting

Fundamental Counting

Sum Rule
- or = +
Product Rule
- and = $\cdot$
- with replacement = $8^{3}$
- without replacement = $8 \cdot 7 \cdot 6$

Lists

An ordered arrangement of the elements of some set S

S =
all possible lists are: anp, apn, nap, npa, pna, pan $6 = 3!$

Permutations

A list containing the elements of a set

A permutation $P_{n} : a_{1} a_{2} . . . a_{n}$ can be interpreted as a function

$P_{n} : {1, 2, . . ., n} ⟶ {1, 2, . . ., n}, P_{n} (i) = a_{i}$ :
a mapping from a set to a specific list

$L = 1, 2, 3. . .$ = identity permutation (the order doesn't change)

Number of full permutations of a set S = $| S |!$

|S| = number of elements of S (cardinality)

Permutations of size $k$

a partial list of size 3 from a set with 5 elements = $5 \cdot 4 \cdot 3 = \frac{n!}{(n - k)!} =_{n} P_{k}$

Circle Permutations (starting positions don't matter)

$n!$ possible permutations with n different starting positions = $\frac{n!}{n} = (n - 1)!$

Permutations where k of the n elements are indistinguishable

$n!$ total permutations, number of possible orderings of the k elements = $k!$ $\to \frac{n!}{k!}$

Combinations

Combinations with sets of distinct elements

i.e. how many subsets of size n can we make from S

\frac{n!}{(n - k)! k!} = (\begin{matrix} n \\ k \end{matrix}) =_{n} C_{k} = \frac{_{n} P_{k}}{k!}

If we have k groups $\to \frac{n!}{n_{1}! n_{2}! \dots n_{k}!} = (\begin{matrix} n \\ n_{1} \end{matrix}) (\begin{matrix} n - n_{1} \\ n_{2} \end{matrix}) \dots (\begin{matrix} n - n_{1} - \dots - n_{k - 1} \\ n_{k} \end{matrix})$

$n_{i} =$ number of elements in the $i$ th group ( $n_{1} + n_{2} + \dots + n_{k} = n$ )
when $k = 2$ , we get the binomial coefficient $\frac{n!}{k_{1}! k_{2}!}_{n} C_{k} = \frac{n!}{(n - k)! k!}$
both sides represent the same (Bijection)

Division Rule

if B is a finite set and $f : A ⟶ B$ maps precisely k items of A to every item of B then A has k times as many items as B
- $| A | = k | B |$

Multisets

a sequence of non-negative integers with k-different element types
$(a_{1}, a_{2}, . . ., a_{k}) ⟶$ all different types of elements
$a_{1} + a_{2} + . . . + a_{k} = n ⟶$ n = total elements in the multiset
number of n-element multisets of k types
- $(\begin{matrix} n + k - 1 \\ k - 1 \end{matrix})$

Counting Theorems