Discrete Mathematics formula sheet

Use it to remove $\to$ before any manipulation; it holds for all truth values.

True exactly when $p$ and $q$ have the same truth value; $p\oplus q\equiv \neg (p\leftrightarrow q)$.

For a finite set A; each element is either in or out of a subset.

Finite sets. A relation from A to B is any subset of A × B, so there are $2^{|A||B|}$ of them.

A binary operation on a set of $n$ elements is a filled $n\times n$ table, each of its $n^2$ entries chosen from the $n$ elements. A commutative one is fixed by the $n(n+1)/2$ entries on and above the main diagonal. For $n=2$: $16$ in all, $8$ commutative.

Holds in every group; note the reversed order. If the group is abelian the order does not matter. Also $(a^{-1}{)}^{-1}=a$.

Holds for every undirected graph (loops count 2). So the number of odd-degree vertices is always even.

Attained exactly by the complete graph $K_n$. A $k$-regular simple graph on $n$ vertices has $m=nk/2$ edges, so it can exist only if $nk$ is even and $0\le k\le n-1$.

Ordered arrangements, no repetition, $0\le r\le n$. Also the number of injective functions from an $r$-set to an $n$-set.

Unordered selections of $r$ from $n$ distinct objects, no repetition, $0\le r\le n$. Symmetry: choosing the ones taken is the same as choosing the ones left.

For $n\ge 0$; for example $C_3=\frac{1}{4}\left(\genfrac{}{}{0ex}{}{6}{3}\right)=5$ and $D_4=24\left(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}\right)=9$.

For $a_n=c_1{a}_{n-1}+\cdots +c_k{a}_{n-k}$; it has degree $k$, so $k$ roots over the complex numbers counted with multiplicity. Since $c_k\ne 0$, no root is 0.