For upper bound,use the Taylor series of exponential function,e>1+t,<<1.Then （)）s含(（）日s2(（）日=g(ma therem) Lett=, ◇ Inclusion-exclusion Principle Let A1,A2,...,An be subset of X.Ic [n],Ar :=nerA.Ao =X Thoorom 3(P): Proof:rewrite the right hand side ∑-1)44=∑-1)∑1=∑∑-1)4 ArIA Left=∑dz,where 6r= J0,fx∈AUA2UUA; 1 otherwise Consider the contribution of to both sides. For the right hand side,.when华A4 0AU..UA,(-l网=l5 When r∈A1UA2UUAn,LetJ={i:x∈Ah, 三--多-9-2(-=0-m=0 by the binomial theorem. Theorem 4:. Proo=WI-lnsn…nA9-系-IA as desired ◇ Applications A bijection a:[n][n]is called derangement if a(i)i,Vi Proposition 1:derangement of n]is n!. Proof Ground set={permutation of,let"A={with()=i，i∈.Then Al =(n-1)!,Arl =(n-)!.The number of derangement is 盒---m-(0---空g putting i=. Definition:(n):im E [n],s.t.gcd(m,n)=1
For upper bound, use the Taylor series of exponential function, e t > 1 + t, 0 < t < 1. Then n k ≤ P k i=0 n i ≤ P k i=0 n i t i t k = (1+t) n t k (Binomial theorem). Let t = k n , (1 + t) n t k = (1 + k n ) n ( k n ) k ≤ (e k n ) n ( k n ) k . Inclusion-exclusion Principle Let A1, A2, · · · , An be subset of X. I ⊂ [n], AI := ∩i∈IAi . A∅ = X. Theorem 3(IEP): |Ac 1 ∩ Ac 2 ∩ · · · ∩ Ac n | = P I⊆[n] (−1)|I| |AI |. Proof: rewrite the right hand side X I⊆[n] (−1)|I| |AI | = X I⊆[n] (−1)|I| X x∈AI ·1 = X x∈X X I⊆[n]:x∈AI (−1)|I| . Left= P x∈X δx, where δx = ( 0, if x ∈ A1 ∪ A2 ∪ · · · ∪ An; 1, otherwise. Consider the contribution of x to both sides. For the right hand side, when x /∈ A1 ∪ A2 ∪ · · · ∪ An, P I:x∈AI (−1)|∅| = 1; When x ∈ A1 ∪ A2 ∪ · · · ∪ An, Let J = {j : x ∈ Aj}, X I:x∈AI (−1)|I| = X I⊆J (−1)|I| = X |J| i=0 |J| i (−1)i = (1 − 1)|J| = 0 by the binomial theorem. Theorem 4: |A1 ∪ A2 ∪ · · · ∪ An| = P ∅6=I⊆[n] (−1)|I|+1|AI |. Proof: Left= |X| − |Ac 1 ∩ Ac 2 ∩ · · · ∩ Ac n | = |A∅| − P I⊆[n] (−1)|I| |AI |, as desired. Applications A bijection σ : [n] −→ [n] is called derangement if σ(i) 6= i, ∀i. Proposition 1: ] derangement of [n] is n! Pn k=0 (−1)k k! . Proof: Ground set={permutation of [n]}, let Ai={permutation with σ(i) = i}, i ∈ [n]. Then |Ai | = (n − 1)!, |AI | = (n − |I|)!. The number of derangement is X I⊆[n] (−1)|I| |AI | = X I⊆[n] (−1)|I| (n − |I|)! = Xn i=0 n i (−1)i (n − i)! = n! Xn i=0 (−1)i i! putting i = |I|. Definition: ϕ(n) : ]m ∈ [n], s.t. gcd(m, n) = 1. 2
Proposition 2:If n=p"p22...p,where pi are distinct primes,then (n)=n II(1-). Proof:Ground set=[n],let Ai={m E [n]:Pilm},then A:={pi,2pi,..,"p:}.The rest of proof are left as an exercise Himt:a-)=无(-1)J Averaging Principle:Every set of numbers must contain a number>average and number<average. Proposition ansen's neuality):Id isth f∑)s∑Af). Proof:Easy induction on the number of summands n.For n=2 this is true,so assume the inequality holds for the number of summands up to n,and prove it for n+1.For this it is enough to replace the sum of the first two terms in i+++n++by the term 入1 and apply the induction hypothesis. Corollary 1(Cauchy-Schwarz inequality):0. Corollary2:a,≥0,1∑a:≥(ia,) Proof:f(r)=25,=，=log2a ◇ 3
Proposition 2: If n = p a1 1 p a2 2 · · · p at t , where pi are distinct primes, then ϕ(n) = n Q t i=1 (1 − 1 pi ). Proof: Ground set= [n], let Ai = {m ∈ [n] : pi |m}, then Ai = {pi , 2pi , · · · , n pi pi}. The rest of proof are left as an exercise. [Hint: Q t i=1 (1 − 1 pi ) = P I⊆[n] (−1)|I| Q 1 pi .] Averaging Principle: Every set of numbers must contain a number≥average and number≤average. Proposition 3(Jensen’s Inequality): If 0 ≤ λi ≤ 1, Pn i=1 λi = 1 and f is convex , then f( Xn i=1 λixi) ≤ Xn i=1 λif(xi). Proof: Easy induction on the number of summands n. For n = 2 this is true, so assume the inequality holds for the number of summands up to n, and prove it for n+ 1. For this it is enough to replace the sum of the first two terms in λ1x1 + λ2x2 + · · · + λn+1xn+1 by the term (λ1 + λ2)( λ1 λ1 + λ2 x1 + λ2 λ1 + λ2 x), and apply the induction hypothesis. Corollary 1(Cauchy-Schwarz inequality): Pn i=1 a 2 i ≥ 1 n ( Pn i=1 ai) 2 , ai ≥ 0. Corollary 2:ai ≥ 0, 1 n Pn i=1 ai ≥ ( Qn i=1 ai) 1 n . Proof: f(x) = 2x , λi = 1 n , xi = log2ai . 3
Combinatorics 2017 Fall week2 note Teaching by:Professor Xiande Zhang Reference: Extremal Combinatorics with applications in Computer Science.2nd Edition.Stasys Jukna,Springer 2011109/22 Generating function(GF) Definition:The ordinary GF of an infinity sequence aoa...is a power seriesf(r)= (1)When converges(i.a radius R0 of convergence).View GF as a function of r,and we can do operations of calculus on it including differentiation and integration.For example:an=(o). (2)Not sure about the comvergence,view formlbthande) and)b a()+b()=>(an+bn)z", n>0 o-on where c A key GF:the GF of {,1,1,…}isr"=点，四<1 Consequences: -GFof{a,a,a2,…}is∑ax"=a -GFof{1,-1,1,-1…}is(-1r=+
Combinatorics 2017 Fall week2 note Teaching by: Professor Xiande Zhang Reference: Extremal Combinatorics with applications in Computer Science. 2nd Edition.Stasys Jukna,Springer. 2017/09/22 Generating function(GF) Definition: The ordinary GF of an infinity sequence a0a1 · · · is a power seriesf(x) = P n≥0 anx n . (1) When P n≥0 anx n converges(i.e.∃ a radius R > 0 of convergence). View GF as a function of x, and we can do operations of calculus on it including differentiation and integration. For example: an = f n(0) n! . (2) Not sure about the convergence, view GF as a formal object with + and ·. Let a(x) = P n≥0 anx n and b(x) = P n≥0 bnx n . a(x) + b(x) = X n≥0 (an + bn)x n , a(x)b(x) = X n≥0 cnx n , where cn = P n≥0 aibn−i . A key GF: the GF of {1, 1, 1, · · · } is P∞ n=0 x n = 1 1−x , |x| < 1. Consequences: – GF of {a 0 , a1 , a2 , · · · } is P∞ n=0 a nx n = 1 1−ax . – GF of {1, −1, 1, −1 · · · } is P∞ n≥0 (−1)nx n = 1 1+x . 1
-Gfaf010,10-…}s三产= -Deeiae玄r=古eg群宫-=高=2u+ir,GF =1 of{1,2,3… -Tke the kth deritie of言产=高，eg群套aa-小…a-k+rt= mi加-复r-含()户 Rpek+1防太高-空（大：产ihs wGFda恤)烂hea is the integer solutions to1+x2+…+xk=n,≥0. Problem 1:Let do=1,an 2an-1,n>1.Find an. Sol:Let f()be GF.Then ∑anr-∑2an-1r=2r∑an-1w-1=2r∑an =1 n=0 1 →f@=1+2f@→国)=1-2z-∑2→a=2” ◇ Useful Trick:In a recurrence problem,first find GF,then expand GF to find an. Problem 2:Let An ={strings of length n over fa,b,c}s.t.No "aa"occuring }Find an=lAnl,n≥1. Sol:Observe that a1=3,a2=8.Forn≥2， An={strings with prefir a{strings with prefir b{strings with prefir ch ={prefir ab or acy Uprefix bor c ={abs,acls:s∈An-2}U{bls,cs:s∈An-1h. So an 2an-2+2an-1.Set do 1,Then an"=2 n+2 an-1".Let f(r)= 三rw+ar+x空a+2- n20 →f0)=1+3x+2x2f+2x-)→f)=1-2-2z 1+x By Partial Fraction Decomposition 1+31 2w3V3+1+2x2w3V3-1-2x
– GF of {1, 0, 1, 0, 1, 0 · · · } is P∞ n≥0 x 2n = 1 1−x2 . – Differentiate both sides of P∞ n=0 x n = 1 1−x . We get P∞ n=1 nxn−1 = 1 (1−x) 2 = P∞ n=0 (n + 1)x n , GF of {1, 2, 3, · · · }. – Take the k-th derivative of P∞ n=0 x n = 1 1−x , we get P∞ n=k n(n − 1)· · ·(n − k + 1)x n−k = k! 1 (1−x) k+1 . i.e. 1 (1−x) k+1 = P∞ n0=0 (n 0+k)···(n 0+1) k! x n 0 = P∞ n=0 n + k k x n . Replace k + 1 by k, 1 (1−x) k = P∞ n=0 n + k − 1 k − 1 x n , which is the GF of {an} ∞ n=0, where an is the ]integer solutions to x1 + x2 + · · · + xk = n, xi ≥ 0. Problem 1: Let a0 = 1, an = 2an−1, n ≥ 1. Find an. Sol: Let f(x) = P n≥0 anx n be GF. Then X∞ n=1 anx n = X∞ n=1 2an−1x n = 2x X∞ n=1 an−1x n−1 = 2x X n=0 anx n . =⇒ f(x) = 1 + 2xf(x) =⇒ f(x) = 1 1 − 2x = X∞ n=0 2 nx n =⇒ an = 2n . Useful Trick: In a recurrence problem, first find GF, then expand GF to find an. Problem 2: Let An = {strings of length n over {a, b, c} s.t. No ”aa” occuring }. Find an = |An|, n ≥ 1. Sol: Observe that a1 = 3, a2 = 8. For n ≥ 2, An = {strings with pref ix a} ∪ {strings with pref ix b} ∪ {strings with pref ix c} = {pref ix ab or ac} ∪ {pref ix b or c} = {ab|s, ac|s : s ∈ An−2} ∪ {b|s, c|s : s ∈ An−1}. So an = 2an−2 + 2an−1. Set a0 = 1, Then P∞ n=2 anx n = 2 P∞ n=2 an−2x n + 2 P∞ n=2 an−1x n . Let f(x) = P∞ n≥0 anx n , X∞ n=0 anx n = a0 + a1x + 2x 2X∞ n=0 anx n + 2x( X∞ n≥0 anx n − a0). =⇒ f(x) = 1 + 3x + 2x 2 f(x) + 2x(f(x) − 1) =⇒ f(x) = 1 + x 1 − 2x − 2x 2 . By Partial Fraction Decomposition f(x) = 1 − √ 3 2 √ 3 1 √ 3 + 1 + 2x + 1 + √ 3 2 √ 3 1 √ 3 − 1 − 2x . 2
Expand f(r),we get 1 f(x)= 1-311.1+31 2W83+11++z2V8V3-11+7石2 =-31 2W3+a++1+哈 235-1 ◇ Defnition:Pr之0，H(份=业--学-w Newton's Binomial Theorem:For any real'r, +-20 holds for r(-1,1). Problem3:Cmpate(月 sol: (月---2-+ -学g9 ---35…em-到 =-0-112.345…2n-2到 2n nl(m-1)1.2m-1 --1-12m-21 22m-1n(n-1可 =-1-12m-2) 22m-1nn-1/ 4n Catalan Scquence:cc1 Problem 4:Given a product aaa of n letters,how many ways can we calculate the product by multiplying two factors at a time? Sol:Denote the solution by cn.Suppose at the last step of multiplication,we have be,where b=aa2…ak,c=ak+iak+2…an,1≤k≤n-l.Notice that there are c ways to put brackets in b,andc-ways to put brackets in c.Thus for a given j,there are cecn-ways.Then c9n=》cgen-k,n≥2
Expand f(x), we get f(x) = 1 − √ 3 2 √ 3 1 √ 3 + 1 1 1 + √ 2 3+1x + 1 + √ 3 2 √ 3 1 √ 3 − 1 1 1 + √ 2 3−1 x = X n≥0 [ 1 − √ 3 2 √ 3 1 √ 3 + 1 ( −2 √ 3 + 1 ) n + 1 + √ 3 2 √ 3 1 √ 3 − 1 ( 2 √ 3 − 1 ) n ]x n Definition: For real r and integer k ≥ 0, let r k = r(r−1)(r−2)···(r−k+1) k! . Newton’s Binomial Theorem: For any real r, (1 + x) r = X∞ k=0 r k x k holds for x ∈ (−1, 1). Problem 3: Compute 1 2 n . sol: 1 2 n = ( 1 2 )( 1 2 − 1)( 1 2 − 2)· · ·( 1 2 − n + 1) n! = 1 2 · −1 2 · −3 2 · · · −(2n−3) 2 n! = (−1)n−1 2 n 1 · 3 · 5 · · ·(2n − 3) n! = (−1)n−1 2 n 1 · 2 · 3 · 4 · 5 · · ·(2n − 2) n!(n − 1)! · 2 n−1 = (−1)n−1 2 2n−1 (2n − 2)! n!(n − 1)! = (−1)n−1 2 2n−1 1 n 2n − 2 n − 1 = (−1)n−1 · 2 4 n 2n − 2 n − 1 . Catalan Sequence: c0 = 0, c1 = 1, cn = nP−1 k=0 ckcn−k. Problem 4: Given a product a1a2 · · · an of n letters, how many ways can we calculate the product by multiplying two factors at a time? Sol: Denote the solution by cn. Suppose at the last step of multiplication, we have bc, where b = a1a2 · · · ak, c = ak+1ak+2 · · · an, 1 ≤ k ≤ n − 1. Notice that there are ck ways to put brackets in b, andcn−k ways to put brackets in c. Thus for a given j, there are ckcn−k ways. Then cn = Xn−1 k=1 ckcn−k, n ≥ 2. 3