Final Exam Revision
Proof 1
\(\forall n\geq 1\) and any \(k=1,...,n-1\) we have \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\)
Proof
Consider \(X=\{a_1,...,a_n\}\), we need to count all possible \(k\)-element subsets of \(X\)
Proof 2 Inclusion-exclusion principle
Let \(A_1,...,A_n\) be finite sets, then \(|A_{1}\cup\ldots\cup A_{n}|=\sum\limits_{J\subset\left\lbrace1,\ldots,n\right\rbrace\atop J\neq\emptyset}(-1)^{|J|+1}\left|\bigcap\limits_{j\in J}A_{j}\right |\)
Proof(Important)
Let \(S=\{(x,J)\in (A_{1}\cup...\cup A_{n})\times \{\text{non-empty subsets of }\{1,.. .,n\}\}|x\in \bigcap_{j\in J}A_{j}\}\) recall that \(\bigcap\limits_{j\in\left\lbrace1\right\rbrace}A_{j}=A_{1}\)
e.g. if \(x\in A_1\cap A_2\) it contributes \((x,\{1\}),(x,\{2\})\) and \((x,\{1,2\})\) to \(S\)
Notices \(\sum\limits_{J\subset\left\lbrace1,\ldots,n\right\rbrace\atop J\neq\emptyset}(-1 )^{|J|+1}\left|\bigcap\limits_{j\in J}A_{j}\right|=\sum\limits_{J\subset\left\lbrace1,\ldots,n\right\rbrace\atop J\neq\emptyset}(-1)^{|J|+1}\left|\left\lbrace\left(y,K\right)\in S:K=J\right\rbrace \right|\) (fix K, where \(y\in\bigcap_{j\in J}A_{j}\) )
Since \(y\in A_1\cup...\cup A_n\) as well, then we can partition that set according to the value of \(y\)
\(=\)\(\sum\limits_{J\subset\left\lbrace1,\ldots,n\right\rbrace\atop J\neq\emptyset}(-1 )^{|J|+1}\sum\limits_{x\in A_1\cup...\cup A_{n}}\left|\left\lbrace\left(y,K\right )\in S: K=J,y=x\right\rbrace\right|\)
\(=\sum\limits_{x\in A_1\cup...\cup A_{n}}\sum\limits_{J\subset\left\lbrace1,\ldots,n\right\rbrace\atop J\neq\emptyset}(-1)^{|J|+1}\left|\left\lbrace\left(y,K\right)\in S:K=J,y=x\right\rbrace \right|\)
Let's analyze\(\sum\limits_{J\subset\left\lbrace1,\ldots,n\right\rbrace\atop J\neq\emptyset}(-1 )^{|J|+1}\left|\left\lbrace\left(x,K\right)\in S:K=J\right\rbrace\right|\)
Suppose that \(x\in A_{j1}\cap ...\cap A_{jk}\) but \(\forall j\notin\left\lbrace j1,\ldots,jk\right\rbrace\). Then \(x\notin A_{j}\cap(A_{j1}\cap ...\cap A_{jk})\)
In this case, the pairs, that contribute to this formula are indexed by all possible non-empty subsets of \(\{j1,...,jk\}\)
What about signs?
\((-1)^{0+1}\binom{k}{0}+ (-1)^{1+1}\binom{k}{1}+ (-1)^{2+1}\binom{k}{2}+ (-1)^{3+1} \binom{k}{3}+ \dots + (-1)^{k+1}\binom{k}{k}= 1.\)
\((-1)(1-1)^k = 0\)
- Contribution from singletons
- Contribution from 2-element sets
- Contribution from \(K=\{j_{1},j_{2},...j_{k}\}\)
Thus \(\sum\limits_{x\in A_1\cup...\cup A_{n}}\sum\limits_{J\subset\left\lbrace1,\ldots,n\right\rbrace\atop J\neq\emptyset}(-1)^{|J|+1}\left|\left\lbrace\left(y,K\right)\in S:K=J,y=x\right\rbrace \right|=\sum\limits_{x\in A_1\cup...\cup A_{n}}1=\left|A_{1}\cup...\cup A_{n}\right |\)
Now we want to remove the condition of \(J\neq \empty\), then another way to write the inclusion-exclusion formula
Suppose \(\exists A\), such that \(A_1, \dots, A_n \subseteq A\) .
Convention: We say that \(\bigcap_{j \in \emptyset} A_j = A\)
\(\left|A\setminus(A_{1}\cup\dots\cup A_{n})\right|=\sum\limits_{J\subseteq\{1,\dots,n\}} (-1)^{\left|J\right|}\left|\bigcap_{j\in J}A_{j}\right|\)
Proof 3 Definition, recursion, generating function and an explicit formula for the Catalan numbers
Definition
\(Cat_n\) is the number of paths of a square \(n\times n\) lattice such that they do not go above the main diagonal
Recursion
Paths still can touch the diagonal, but can not pierce it
Let \(Cat^k_{n+1}\) be the set of paths such that they touch the diagonal at the \((0,0),(k,k)\) but not in any intermedia points where \(k=1,...,n+1\)
Fix k: All the paths from \(Cat^{k}_{n+1}\) do not go above the diagonal \(y=x-1\) in the square \((k-1)\times(k-1)\)
By the product principle, \(Cat_{n+1}^{k}=Cat_{k-1}Cat_{n-k+1}\). By addition principle, \(Cat_{n+1}=\sum_{k=1}^{n+1}Cat_{k-1}Cat_{n-k+1}=\sum_{j=0}^{n}Cat_{j}Cat_{n-j}\)
Generating function
Introduce: \(Cat(s)=Cat_0+Cat_1s+Cat_2s^2+...=\sum^\infty_{n=0}Cat_ns^n\)
Explicit formula
A Taylor expansion of a criterium function
What equation should \(Cat(s)\) satisfy to enjoy the recursion we have?
Let's compute \(Cat^2(s)=Cat_0Cat_0+(Cat_1Cat_0+Cat_0Cat_1)s+(Cat_2Cat_0+Cat_1Cat_1+Cat_0Cat_2)s^2+...=Cat_1+Cat_2s+Cat_3s^2+...\)
Then \(sCat^{2}(s)=Cat_{1}s+Cat_{2}s^2+Cat_{3}s^{3}+...\)
Then \(sCat^{2}(s)+Cat_{0}=Cat_{0}+Cat_{1}s+Cat_{2}s2+Cat_{3}s^{3}+...=Cat\left(s\right )\)
\(sCat^2(s)+1=Cat(s)\)
Then \(s^2Cat^2(s)-sCat(S)+s=0\), then \((sCat(s)-\frac{1}{2})^2+s-\frac{1}{4}=0\)
Then \(sCat(s)=\frac{1}{2}\pm\sqrt{\frac{1}{4}-s}\)
We know there are possible square roots of \(\frac{1}{4}-s\)
They differ by multiplication by \(-1\)
We need to choose one of them, from tutorial we know \(\sqrt{\frac{1}{4}-s}=\frac{1}{2}+...\) or \(-\frac{1}{2}+...\)
Since in the left hand side of (*), there is \(s\), thus the right hand side should be divisible by \(s\), thus we choose \(\frac{1}{2}+...\)
Recall: \((1+s)^{n}=\sum_{k=0}^{\infty}\binom{n}{k}s^{k}=\sum_{k=0}^{\infty}\frac{\left(n\right)_{k}}{k!} s^{k}\) when \(n\in\mathbb{C}\)
E.g.: \((1+s)^{\frac{1}{2}}(1+s)^{\frac{1}{2}}=(1+s)^1\) where \((1+s)^{\frac{1}{2}}\) is a square root of \(1+s\)
\((1+s)^{\frac{1}{2}}=1+\frac{1}{1!}s + \frac{(\frac{1}{2})(-\frac{1}{2})}{2!}s^{2} + \frac{(\frac{1}{2})(-\frac{1}{2})(-\frac{3}{2})}{3!}s^{3} + \frac{(\frac{1}{2})(-\frac{1}{2})(-\frac{3}{2})(-\frac{5}{2})}{4!} s^{4} + ... + (-1)^{n+1}\frac{(2n-3)!!}{2^{n} \cdot n!}s^{n}\)
where \((2n)!! = (2n)(2n-2)(2n-4)...2\). \(\leftarrow\) even factors only
And \((2n+1)!! = (2n+1)(2n-1)(2n-3)...3\cdot 1\). \(\leftarrow\) odd factors only.
Here, \(Cat(s)=\frac{1-\sqrt{1-4s}}{2s}\), by the proposition, we know that
Then we get \(Cat_n=\frac{\frac12\frac12\frac32...\frac{2n-1}{2}\cdot4^{n+1}}{2(n+1)!}\cdot\frac{n!}{n!}\) \(=\frac{1}{n+1}\binom{2n}{n}\) using \((2n-1)!!=\frac{2n!}{2^n\cdot n！}\)
This \(Cat_n\) is the coefficients of \(s^n\)
Proof 4 The rationality of the generating function of a sequence defined by a linear recursion with constant coefficients
\(k\in \N\), fix \(f_{0},f_{1},...,f_{k-1}\) are fixed numbers (just numbers)
Another collection \(c_1,...,c_k\) of fixed numbers
And a sequence defined by the recurrences
\(f_{n+k}=c_1f_{n+k-1}+c_2f_{n+k-2}+...+c_kf_n\) for all \(n>0\)
Here we can take Fibonacci numbers as an example (\(c_{1}=c_{2}=1\))
Then the generating function \(F(s)=\sum^\infty_{n=0}f_ns^n\) is rational. \(F(s)=\frac{P(s)}{Q(s)}\) where \(\deg Q(s)=k,\deg P(s)\leq k-1\)
\(\,\,\,\,\,+F(s) = f_{0}+f_{1}s + f_{2}s^{2}+ ... + f_{k}s^{k}+ ...\)
\(-c_{1}s F(s) = c_{1}f_{0}s + c_{1}f_{1}s^{2}+ ... + c_{1}f_{k-1}s^{k}+ . ..\)
\(-c_{2} s^{2} F(s) = \quad \quad \,\,\,\,\,\,c_{2} f_{0} s^{2} + ... + c_{2} f_{k-2}s^{k} + ...\)
\(...\)
\(-c_{k}s^{k}F(s)=\quad\quad\quad\quad\quad\quad\quad\,\,\,...+c_{k}f_{0}s^{k}\)
\(\Rightarrow (1 - c_1 s - ... - c_k s^k) F(s) = P(s) \Rightarrow F(s) = \frac{P(s)}{1 - c_1 s - c_2 s^2 - ... - c_k s^k}\) where \(P(s)=f_{0}+(f_{1}-c_{1}f_{0})s+(f_{2}-c_{1}f_{1}-c_{2}f_{0})s^{2}+\cdots\) plus until \(k-1\)
Proof5
Let \(q_1,...,q_m\in \N\), \(A\) is a set with \(q_1+q_2+...+q_m-m+1\) elements. \(B\) is a set with \(m\) elements such that \(B=\{1,2,...,m\}\)
Then \(\exists i\in B\) s.t. \(\#f^{-1}(i)\geq q_i\)
Proof
Suppose \(\forall i=1,\ldots,m,\#f^{-1}(i)<q_i\), then \(\sum^m_{i=1}f^{-1}(i)\leq (q_1-1)+(q_2-1)+...+(q_m-1)=q_1+...+q_m-m\) which is a contradiction
Proof6
Theorem(Ramsey)
Let \(p,q\in \N\). Then there exists a certain \(N_{(p,q)}\in \N\) such that any graph on \(N_{(p,q)}\) vertices either a p-clique or a q-anticlique
We are going to show that \(\forall p,q\geq 2\), we have \(R(p,q)\leq R(p-1,q)+R(p,q-1)\)
Proof
Set \(N=R(p-1,q)+R(p,q-1)\). Consider a graph that has \(N\) vertices
Fix one of the vertices of the graph and notice by generalized pigeonhole principle, either this vertex is incident to at least \(R(p-1,q)\) edges, or there are at least \(R(p,q-1)\) other vertices not adjacent to it
Suppose that there are at least \(R(p-1,q)\) other vertices adjacent to the chosen one
In the subgraph induced by adjacent vertices either there is a p-1 clique or a q anticlique
So either there is a p-clique (added chosen one) or a q-anticlique in the original graph
The symmetric case is considered in a similar way
Proof7
Theorem(Hall's marriage theorem)
Let \(G\) be a bipartite graph and \(V=V_0\sqcup V_1\), then \(G\) admits a saturating matching if and only if \(\forall S\subseteq V_{0}\) we have \(\#S\leq \#N(S)\) (the hall's condition)
Proof(Important)
\(\Rightarrow\)) Trivial
\(\Leftarrow\)) Induction by \(\#V_0\)
Base case: \(\#V_0=1\), then there exists a matching
Induction step: Suppose Hall's condition\(\implies\)existence of a saturating matching for any bipartite graph \(\#V_0\leq k\)
Take a bipartite graph \(G\) with \(\#V_0=k+1\) and \(G\) satisfies the Hall's condition
Case 1: \(\forall S\subsetneq V_0,S\neq \empty\), we have \(\#N(S)\geq \#S+1\)
Consider an edge \(\{uv\}\) \(u\in V_0,v\in V_1\), try to include this edge to a matching
Consider \(G-\{u\}-\{v\}=G'\), claim: \(G'\) still satisfies the Hall's condition
Let \(V_0'=V_0-\{u\}\) and \(V_1'=V_1-\{v\}\), take \(S\subseteq V_0'\)
\(\#N_{G'}(S)\geq\#N_G(S)-1\geq( \#S+1)-1=\#S\), the
Thus Hall's condition holds for \(G'\)
Case 2: \(\exists S\subsetneq V_{0},S\neq \empty\) s.t. \(\#N_G(S)=\#S\)
Consider \(G[S\cup N_{G}(S)]\) graph. It satisfy the Hall's condition.
Then the saturating matching exists in \(G[S\cup N_{G}(S)]\)
Consider \(V_0'=V_0-S\), \(V_1'=V_1-N_G(S)\), let \(G'=G[V_0'\cup V_1']\). Claim: \(G'\) satisfy the Hall's condition
Suppose the Hall's condition doesn't hold true for \(G'\), then \(\exists T\subseteq V_0'\) s.t. \(\#N_{G'}(T)<\#T\)
Compute \(\#N_{G}(S\cup T)=\#(N_{G}(S)\cup N_{G'}(T))\overset{\text{since they are disjoint}} {=}\#N_{G}(S)+\#N_{G'}(T)<\#S+\#T\)
Note \(S\cup T\) are also disjoint, then \(\#(S\cup T)=\#S+\#T\), thus \(\#N_{G}(S\cup T)<\#(S\cup T)\)
Then contradiction to the Hall's condition