simshadows
About Me Web Apps Blog

Discrete Mathematics Cheatsheet

This cheatsheet will focus on what’s useful for computer science students and programmers.

Factorial

n!=∏k=1nk=1×2×3×⋯×(n−2)×(n−1)×n,∀n∈Z:n>0.0!=1\begin{gather*} n! = \prod_{k = 1}^n{k} = 1 \times 2 \times 3 \times \dots \times (n-2) \times (n-1) \times n, \\ \forall n \in \mathbb{Z} : n > 0. \qquad\qquad 0! = 1 \end{gather*}

Recursive definition:

0!=1n!=n(n−1)! 0! = 1 \qquad\qquad n! = n \parens{n - 1} !

TODO: Binet’s formula?

kk-Permutations of nn

nPk=n!(n−k)! \MyPermutations{n}{k} = \frac{n!}{\parens{n - k}!}

kk-Combinations of nn / Binomial Coefficient

nCk=(nk)=n!k! (n−k)! \MyCombinations{n}{k} = \binom{n}{k} = \frac{n!}{k! \, \parens{n - k}!}

TODO: Notation? I don’t think the notation I’m using here is common in mathematics.

Distributive Laws

A⋅(B+C)=(A⋅B)+(A⋅C)A+(B⋅C)=(A+B)⋅(A+C)\begin{gather*} A \cdot (B + C) = (A \cdot B) + (A \cdot C) \\ A + (B \cdot C) = (A + B) \cdot (A + C) \end{gather*}

Absorption Laws

A+(A⋅B)=AA⋅(A+B)=A(A⋅B)+(A⋅B‾)=A(A+B)⋅(A+B‾)=A\begin{gather*} A + (A \cdot B) = A \\ A \cdot (A + B) = A \\ (A \cdot B) + (A \cdot \overline{B}) = A \\ (A + B) \cdot (A + \overline{B}) = A \end{gather*}

De Morgan’s Theorem

A+B‾=A‾⋅B‾A⋅B‾=A‾+B‾\begin{gather*} \overline{A + B} = \overline{A} \cdot \overline{B} \\ \overline{A \cdot B} = \overline{A} + \overline{B} \end{gather*}

Modular Arithmetic Properties

(a+b) mod m=((a mod m)+(b mod m)) mod m(a−b) mod m=((a mod m)−(b mod m)) mod m(a×b) mod m=((a mod m)(b mod m)) mod m\begin{align*} \parens{a + b} \bmod m &= \parens{\parens{a \bmod m} + \parens{b \bmod m}} \bmod m \\ \parens{a - b} \bmod m &= \parens{\parens{a \bmod m} - \parens{b \bmod m}} \bmod m \\ \parens{a \times b} \bmod m &= \parens{\parens{a \bmod m} \parens{b \bmod m}} \bmod m \end{align*}

References