Counting theory tries to answer the question “How many?” without actually enumerating all the choices.

The rule of sum

the number of ways to choose one element from one of two disjoint sets is the sum of the cardinalities of the sets.

The rule of product

the number of ways to choose an ordered pair is the number of ways to choose the first element times the number of ways to choose the second element.

Permutations

A permutation of a finite set S is an ordered sequence of all the elements of S, with each element appearing exactly once.

$$n!$$ permutations of a set of $$n$$ elements

$$k$$-permutation

$$k$$-permutation of $$S$$ is an ordered sequence of $$k$$ elements of S, with no element appearing more than once in the sequence.

$$n(n-1)(n-2)...(n-k+1) = \frac{n!}{(n-k)!}$$

$$k$$-combination

$$k$$-combination means choosing $$k$$ distinct (different) elements from the $$n$$-set. The order in which we select the elements does not matter.

$$k$$-combination of an $$n$$-set $$S$$ is simply a $$k$$-subset of $$S$$

• EX: 4-set {a, b, c, d} has six 2-combinations: {ab, ac, ad, bc, bd, cd} if we shorthand denoting the 2-subset {a,b} by ab

Since every $$k$$-combination has exactly $$k!$$ permutations of its elements, each of which is a distinct $k$-permutation of the n-set. the number of $$k$$-combinations of an $$n$$-set is the number of k-permutations divided by $$k!$$.

$${n \choose k} = \frac{n!}{k!(n-k)!} = {n \choose n-k}$$