Combinatorics

Product Rule: finite set $|S\times T|=|S||T|$ Sum Rule: finite disjoint set $|S\cup T|=|S|+|T|$ Bijection Rule: finite set $\exists\phi:S\rightarrow T$ onto and 1 1 then $|S|=|T|$...

ordinary generating function(OGF) define by $a n$: $G(x)=\sum {n\geq0}a nx^n$ coefficient: $[x^k]G(x)$ $\mathbb{C}[[x]]$: ring of formal power series with complex coefficient Combi...

PIE PIE(Priciple of Inclusion Exclusion) $A I=\bigcap {i\in I}A i$ $|\bigcup {i=1}^nA i|=\sum {I\subseteq\{1,\cdots,n\},|I|\geq 1}( 1)^{|I| 1}|A I|$ $|\bigcap {i=1}^n\overline{A i}...

Graph Isomorphism (GI) Input: two undirected graphs $G$ and $H$ Output: $[G\cong H]$ String Isomorphism (SI) Input: two strings $x,y$: $[n]\rightarrow[m]$ and a permutation group $...

Cayley's formula: There are $n^{n 2}$ different trees on $n$ distinct vertices Double Counting Count: # of sequences of adding directed edges to an empty graph to form a rooted tre...

Existence by Counting Shannon 1949: There is a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$ which cannot be computed by any circuit with $\frac{2^n}{3n}$ gates $f$ computable b...

Existence by Probability $$\exists x,A(x)\Leftarrow P(A(x)) 0$$ $$\exists x,A(x)\Leftarrow P(\neg A(x))<1$$ $$P(A)=P(\wedge {i=1}^n\overline{A} i) 0\Leftarrow P(\vee {i=1}^nA i)<1\...

How many edges that a graph $G$ can have if $G$ has some property Triangle free graph contains no triangle as subgraph Mantel's Theorem (1907): if $G(V,E)$ has $|V|=n$ and is trian...

How large or how small a collection of finite objects can be, if it has to satisfy certain restrictions Sunflower set system $\mathcal{F}\subset 2^{[n]}$ with ground set $[n]$ a su...

2 color Ramsey $R(k,l)$ is the smallest integer satisfying: if $n\geq R(k,l),\forall$ 2 coloring $K n$, there exists a red $K k$ or a blue $K l$ Remsey Theorem (In graph theory): $...

Hall Theorem SDR: system of Distinct Representives distinct $x 1,x 2,\cdots,x m,x i\in S i,i=1,2,\cdots,m$ Hall's Theorem (marriage theorem): $S 1,S 2,\cdots,S m$ have a SDR $\iff...