The whole Discrete Mathematics formula sheet, to print

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 $n$ distinct atoms; the second count is the number of different possible output columns.

Here T and F stand for the constants true and false.

Negation swaps $\wedge$ and $\vee$ and negates each part.

Each of $\wedge$ and $\vee$ distributes over the other.

Useful for quickly simplifying a formula.

An implication fails only when the hypothesis holds and the conclusion fails.

Exportation and the two combining rules; note the hypotheses combine with $\vee$ when the conclusion is shared.

Rewrite each side with $\neg a\vee b$ to check them. With a shared conclusion and $\vee$ between the implications, the hypotheses combine with $\wedge$.

To refute an argument, find one assignment making every premise true and the conclusion false.

Push $\neg$ inside by flipping each quantifier and negating the body; repeat for nested quantifiers.

$\forall$ distributes over $\wedge$ and $\exists$ distributes over $\vee$, as equivalences.

The same holds for $\forall$ with $\wedge$ and $\exists$ with $\vee$. The step $\exists x\psi \equiv \psi$ (or $\forall x\psi \equiv \psi$) used here relies on the domain being non-empty.

The quantifier flips when it leaves the antecedent. It keeps its kind when it leaves the consequent: $\forall x(\psi \to P(x))\equiv \psi \to \forall xP(x)$ and $\exists x(\psi \to P(x))\equiv \psi \to \exists xP(x)$. The $\exists$ forms need a non-empty domain.

Write the body as $\neg P(x)\vee Q(x)$, distribute $\exists$ over $\vee$, and use $\exists x\neg P(x)\equiv \neg \forall xP(x)$. By contrast, $\forall x(P(x)\to Q(x))$ only implies $\forall xP(x)\to \forall xQ(x)$.

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.

Finite sets; this is the basis of Venn-diagram counting.

Finite sets; add singles, subtract pairs, add the triple.

Finite sets.

Each of the $n^2$ ordered pairs is in or out.

The n diagonal pairs are forced; the other $n(n-1)$ are free. Irreflexive relations have the same count.

For $n\ge 1$, where no relation is both reflexive and irreflexive: subtract the reflexive and the irreflexive relations from all relations.

Choose freely for each of the $n$ diagonal pairs and each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered pairs $\{a,b\}$ with $a\ne b$.

Diagonal pairs are free ($2^n$); each unordered pair $\{a,b\}$ with $a\ne b$ has 3 choices: none, $(a,b)$ only, $(b,a)$ only.

Diagonal pairs are excluded; each unordered pair has the same 3 choices. Reflexive and antisymmetric relations have the same count (diagonal forced in instead of out).

Diagonal forced to 1; each unordered pair with $a\ne b$ is in or out. Irreflexive and symmetric relations have the same count.

Such a relation is a subset of the identity relation, so only the diagonal pairs are free.

$B_n$ (Bell number) counts partitions of an n-element set; $S(n,k)$ (Stirling number of the second kind) counts partitions into exactly $k$ non-empty blocks.

With $S(n,1)=S(n,n)=1$ for $n\ge 1$, and $S(n,n-1)=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$.

For $n\ge 2$: the number of equivalence relations on n elements with exactly two classes.

Each element of $A$ independently picks an image.

$m=|A|$, $n=|B|$, $m\le n$; when $m>n$ there are none (the product form gives 0).

$|A|=|B|=n$; this is also the number of permutations of an n-set.

$m=|A|$, $n=|B|$; zero when $m<n$.

$m=|A|$, $n=|B|$; each element of $A$ maps to one of the $n$ elements or is left undefined.

Poset $(\mathcal{P}(A),\subseteq )$ with $|A|=n$: $S$ is covered by $S\cup \{x\}$ for each $x\notin S$.

Poset of positive divisors under 'divides' ($p_i$ distinct primes); join is lcm and meet is gcd.

$N=p_1^{a_1}\cdots p_k^{a_k}$; $d$ is covered by $d{p}_i$ whenever $d{p}_i$ divides $N$. For $N=12=2^2\cdot 3$: $2\cdot 2+1\cdot 3=7$.

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

For a finite group $G$ and any subgroup $H$; $[G:H]$ is the number of distinct left cosets of $H$ in $G$.

In every finite group, by Lagrange applied to $⟨a⟩$. Also $a^k=e⟺o(a)\mid k$.

Holds in any group. In ${\mathbb{Z}}_n$ the element $k$ has order $n/\gcd (n,k)$. If $G=⟨a⟩$ has order $n$, the element $a^k$ generates $G$ exactly when $\gcd (n,k)=1$.

For a cyclic group of order $n$, where $\varphi (n)$ is Euler's totient (the count of $k$ with $1\le k\le n$ and $\gcd (k,n)=1$).

The product runs over the distinct primes $p$ dividing $n$. For a prime $p$, $\varphi (p)=p-1$ and $\varphi (p^k)=p^k-p^{k-1}$.

A cyclic group of order $n$ has exactly one subgroup for each positive divisor $d$ of $n$, so the number of subgroups equals the number of divisors of $n$. Every subgroup of a cyclic group is cyclic, and the group has exactly $\varphi (d)$ elements of order $d$ for each $d\mid n$.

In $G\times H$ with finite $o(a)$ and $o(b)$. Consequently ${\mathbb{Z}}_m\times {\mathbb{Z}}_n$ is cyclic if and only if $\gcd (m,n)=1$.

Any non-identity element has order dividing $p$, so order $p$, hence generates $G$. Every non-identity element is a generator, giving $p-1$ generators.

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

A graph with $n$ vertices and $k$ components has at least $n-k$ edges; so a connected graph has at least $n-1$ edges. Equality holds exactly for forests.

Simple graph on $n\ge 2$ vertices with at least 2 components. Attained by $K_{n-1}$ plus one isolated vertex. With exactly $k$ components the maximum is $\left(\genfrac{}{}{0ex}{}{n-k+1}{2}\right)$.

The vertex connectivity $\kappa (G)$ is the fewest vertices whose removal disconnects $G$ or leaves a single vertex; the edge connectivity $\lambda (G)$ is the fewest edges whose removal disconnects $G$. $\kappa (K_n)=\lambda (K_n)=n-1$. A connected graph on $n\ge 3$ vertices has a cut vertex exactly when $\kappa =1$, and a connected graph on $n\ge 2$ vertices has a bridge exactly when $\lambda =1$.

For a tree with $n\ge 2$ vertices. In particular every such tree has at least 2 leaves (vertices of degree 1).

Number of labelled trees on $n$ vertices, which equals the number of spanning trees of $K_n$. Also $\tau (K_{p,q})=p^{q-1}{q}^{p-1}$ and $\tau (C_n)=n$.

For a simple graph $G$, the complement $\overline{G}$ has the same vertices and exactly the non-edges of $G$. Degrees satisfy ${\mathrm{deg}}_{\overline{G}}(v)=n-1-{\mathrm{deg}}_G(v)$.

Necessary conditions on the order and size of a simple self-complementary graph. Examples: $P_4$ (4 vertices, 3 edges) and $C_5$ (5 vertices, 5 edges).

Holds for every simple (loopless) graph: a set is independent exactly when its complement is a vertex cover.

Every vertex cover needs a distinct vertex for each matching edge, so $\nu \le \beta$ always; equality is guaranteed only for bipartite graphs. (The triangle has $\nu =1$, $\beta =2$.)

A bipartite graph with parts $X,Y$ has a matching covering every vertex of $X$ if and only if this holds, where $N(S)$ is the set of neighbours of $S$. When $|X|=|Y|$, this is the condition for a perfect matching.

For every graph, where $\Delta$ is the maximum degree. By Brooks' theorem, a connected graph that is neither a complete graph nor an odd cycle has $\chi (G)\le \Delta (G)$.

$P(G,k)$ is the number of proper colourings of $G$ using at most $k$ colours, with the colours and vertices labelled. $T$ is any tree on $n$ vertices; $C_n$ needs $n\ge 3$. Check: $P(C_3,k)=k(k-1)(k-2)=P(K_3,k)$. $\chi (G)$ is the least $k$ with $P(G,k)>0$.

The chromatic index ${\chi }^{\prime }(G)$ is the fewest colours that give edges sharing a vertex different colours. The bounds hold for every simple graph (Vizing). A bipartite graph has ${\chi }^{\prime }=\Delta$. ${\chi }^{\prime }(K_n)=n-1$ for even $n$ and $n$ for odd $n$.

For a connected planar graph (drawn without crossings). With $k$ components the right side is $k+1$.

For a simple planar graph with $V\ge 3$. If the graph also has no triangle (for example, it is bipartite), $E\le 2V-4$. Reason: in a simple connected planar graph with $V\ge 3$, every face has degree at least 3 (at least 4 with no triangle), and ${\sum }_f\mathrm{deg}(f)=2E$. More generally, if every cycle has length at least $g$, then $E\le \frac{g}{g-2}(V-2)$.

Simple graph with $n\ge 3$. Ore's generalisation: if $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$ for every pair of non-adjacent $u,v$, then $G$ is Hamiltonian. Both are sufficient only.

For $n\ge 3$, labelled vertices, counting a cycle and its reverse as the same. $K_{p,q}$ is Hamiltonian exactly when $p=q\ge 2$, and $K_{n,n}$ ($n\ge 2$) has $\frac{n!(n-1)!}{2}$ Hamiltonian cycles (1 for $K_{2,2}$, 6 for $K_{3,3}$).

For the adjacency matrix $A$ of a graph (directed or undirected; in a multigraph $A_{ij}$ counts parallel edges, and a loop is entered as 1 in $A_{ii}$). Walks may repeat vertices.

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.

Unordered choice of $r$ items from $n$ kinds ($n\ge 1$) when each kind may be taken any number of times (multisets of size $r$).

Seating $n\ge 1$ distinct people round a table when rotations count as the same arrangement (reflections counted as different). If reflections are also the same and $n\ge 3$, divide by 2: $(n-1)!/2$.

Distinct arrangements of $n$ objects of which $n_i$ are alike of type $i$, $\sum n_i=n$. It is also the number of ways to split $n$ distinct objects into labelled groups of sizes $n_1,\dots ,n_k$.

Number of integer solutions ($k\ge 1$); equals the number of ways to put $n$ identical objects into $k$ distinct bins, empty bins allowed.

Every bin non-empty ($n,k\ge 1$). For a lower bound $x_i\ge a_i$, substitute $y_i=x_i-a_i$ and reduce $n$ by $\sum a_i$.

Add a slack variable $x_{k+1}=n-(x_1+\cdots +x_k)\ge 0$; the equation now has $k+1$ unknowns summing to $n$.

$S(n,k)$ = number of ways to split a set of $n$ distinct objects into $k$ non-empty unlabelled blocks. Conventions: $S(0,0)=1$, $S(n,0)=0$ for $n\ge 1$, $S(n,k)=0$ for $k>n$. Also $S(n,2)=2^{n-1}-1$. Example values: $S(4,2)=7$, $S(5,2)=15$, $S(5,3)=25$.

Number of ways to write $n$ as a sum of exactly $k$ positive integers with order ignored. Boundary values: $p(0,0)=1$; $p(n,k)=0$ if $k>n$, or if $n\ge 1$ and $k\le 0$. $p(n)$ is the total over all $k$; $p(1),\dots ,p(7)=1,2,3,5,7,11,15$.

For a non-negative integer $n$. The coefficient of $x^{n-k}{y}^k$ is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$; there are $n+1$ terms. In $(x_1+\cdots +x_k{)}^n$ the coefficient of $x_1^{n_1}\cdots x_k^{n_k}$, where $n_1+\cdots +n_k=n$, is $\frac{n!}{n_1!\cdots n_k!}$.

For $n\ge 1$ and $1\le k\le n$. Split the $k$-subsets of an $n$-set by whether they contain a chosen element.

Total number of subsets of an $n$-set; from $x=y=1$ and $x=1,y=-1$. Hence even-size subsets and odd-size subsets each number $2^{n-1}$ for $n\ge 1$.

Follows from $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ (choose a committee, then its leader).

Choose $r$ from two groups of sizes $m$ and $n$ by how many come from the first (terms with $k>m$ or $r-k>n$ are 0). The case $m=n=r$ gives ${\sum }_k{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}^2=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$.

For $0\le r\le n$. Sum down a diagonal of Pascal's triangle.

Counts elements with at least one of $m$ properties; for two sets, $|A\cup B|=|A|+|B|-|A\cap B|$. The number with none of the properties is $|U|$ minus this value.

Functions from an $n$-set onto a $k$-set; equals $k!S(n,k)$ and is $0$ if $n<k$.

Permutations of $n$ objects with no object in its original place. Convention $D_0=1$. Also $D_n=n{D}_{n-1}+(-1{)}^n$, and for $n\ge 1$, $D_n$ is the integer nearest to $n!/e$. $D_1=0,D_2=1,D_3=2,D_4=9,D_5=44,D_6=265$.

Choose which $k$ objects stay put, then derange the other $n-k$ (for $k=n$ this gives $D_0=1$, the identity).

For positive integers $n$, $k$. To guarantee at least $r$ objects in one of $k$ boxes you need $k(r-1)+1$ objects. It proves existence only; it does not construct the box.

Number of partitions of an $n$-set into non-empty blocks, which is also the number of equivalence relations on it (each relation corresponds to its set of equivalence classes).

Shortest paths from $(0,0)$ to $(m,n)$ using unit steps right and up: choose which $m$ of the $m+n$ steps are right. Forced points are handled by multiplying path counts of each leg.

Paths from $(0,0)$ to $(n,n)$ with right steps (along $x$) and up steps (along $y$) that never go above the line $y=x$ (touching allowed). Also: balanced bracket strings with $n$ pairs; unlabelled binary trees with $n$ nodes (left and right child distinguished); binary search trees on $n$ distinct keys; full binary trees with $n+1$ leaves; ways to parenthesise a product of $n+1$ factors; triangulations of a convex $(n+2)$-gon.

Condition on the end: a valid string ending in 0 is any valid string of length $n-1$ followed by 0; a valid string ending in 1 must end in 01, after any valid string of length $n-2$. Values: 2, 3, 5, 8, 13, 21, 34, 55 for $n=1,\dots ,8$; $a_n=F_{n+2}$ with $F_1=F_2=1$.

Number of $k$-element subsets of $\{1,2,\dots ,n\}$ with no two consecutive integers; equivalently binary strings of length $n$ with $k$ ones, no two adjacent (place the $k$ ones in the $n-k+1$ gaps around the $n-k$ zeros).

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.

When all $k$ roots $r_i$ are distinct (real or complex); the constants ${\alpha }_i$ come from the $k$ initial conditions.

A root $r$ of multiplicity $m$ contributes this term; add the contributions of all roots.

Roots of $r^2=r+1$; $F_0=0,F_1=1$ and $L_0=2,L_1=1$.

For $n\ge 1$ with constants $c$ and $d$. Example: $a_n=2a_{n-1}+1$, $a_0=0$ gives $2^n-1$.

Coefficients $1,1,1,\dots$ and $1,a,a^2,\dots$; so $1/(1+x)$ gives $(-1{)}^n$.

Coefficients $1,2,3,\dots$ and $0,1,2,3,\dots$.

For integer $k\ge 1$; $[x^n](1-x{)}^{-k}$ counts solutions of $y_1+\cdots +y_k=n$ in non-negative integers.

For integer $m\ge 0$; the second gives a bounded choice of $0$ to $m$ items.

With $F_0=0,F_1=1$ and $L_0=2,L_1=1$.

For $k\ge 1$; the coefficient of $x^n$ in $(1-x{)}^{-k}$, i.e. $n$ identical objects into $k$ distinct boxes. With every $y_i\ge 1$ the count is $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ (for $n\ge k$; zero if $n<k$).