Combinatorics 2017 Fall weekl note Teaching by:Professor Xiande Zhang Reference: Extremal Combinatorics with applications in Computer Science. 2nd Edition.Stasys Jukna,Springer. 2017.9.12 Notation: &6onc艾aten的 (2)for integer n>0 [n]:={1,2.....n} (3)A vector(or string)of length n over X （x1.“,rn.x:∈X,1∈n (4)i.e.that is. 3exist. →imply. s.t.such that ！unique
Combinatorics 2017 Fall week1 note Teaching by: Professor Xiande Zhang Reference: Extremal Combinatorics with applications in Computer Science. 2nd Edition.Stasys Jukna,Springer. 2017.9.12 Notation: (1) A set X (a collection of distinct elements) |X| :=# elements of X (2) for integer n > 0 [n] := {1, 2, · · · , n} (3) A vector(or string) of length n over X (x1, ·, xn).xi ∈ X, i ∈ [n] (4) i.e. that is. ∃ exist. ⇒ imply. s.t. such that. ! unique. 1
Counting: Function.For sets a.B.a function aB is a relation between A and B.(a,f(a))s.t.for each aA,3 B satisfying b=f(a) Injection(one to one function):if a a',then f(a)f(a). Surjection(onto)∀b∈B,3a∈A,s.tf(a=b. Bijection(one to one correspondence)Injection&Surjection. Porpostion1.For sets A,B (1)if3 injection f:A→B then A≤|BL. (2)if3 surjection f:A→B then A≥lBl (3)if 3 bijection f A-B then Al Bl. proof: (1)Assume BAl since 3 functionf AB by definition a∈A,3b∈Bs.t.f(a)=b.3b∈Bs.t.there does not exist a E A satisfying f(a)=b This is contradiction with the fact that f is a surjection. (3)(1)&(2)→(3). 0 2
Counting: Function.For sets A,B. a function A → B is a relation between A and B. (a, f(a)) s.t. for each a ∈ A, ∃b ∈ B satisfying b = f(a) Injection(one to one function): if a 6= a 0 ,then f(a) 6= f(a 0 ). Surjection(onto) ∀b ∈ B, ∃a ∈ A, s.t.f(a) = b. Bijection(one to one correspondence) Injection & Surjection. Porpostion1. For sets A,B (1) if ∃ injection f : A → B then |A| ≤ |B|. (2) if ∃ surjection f : A → B then |A| ≥ |B|. (3) if ∃ bijection f : A → B then |A| = |B|. proof: (1) Assume |B| |A| since ∃ functionf : A → B by definition ∀a ∈ A, ∃!b ∈ B s.t.f(a) = b. ∃b ∈ B s.t.there does not exist a ∈ A satisfying f(a) = b This is contradiction with the fact that f is a surjection. (3) (1)&(2) ⇒ (3). 2
Porpostion2: For sets X.Y.X]=n,Y [r].Let XY :={all functions f:Y X).Then XY=n". proof:Let B=fall vectors of length r over X}.define a function 9:Xy→B.f→(f1),,f) gis a injection since f≠f→(f(1),…,f(r)≠(f'(1),…,f'(r). g is a surjection.since∀(b1,·,b,）∈B.define f：Y→X,i→ bi(i.e.f(i)=bi)That is easy to get g(f)=(b1,..,b). →g is a bijection..→lXY1=lBl=n'. 0 Porpostion3: Let Y=[r],2Y :={all subsets of Y).then 2=2 proof:Let B=fall vectors of length r over (0,1)).define function f:2Y→B,A→f(A=(b,…,br) ae={老究 claim:f is a injection. claim:f is a surjection (b,…,b,)∈B define A={b:=1} →f(A)=(d,…,br) →f is a bijection.→Y|=lB=2". If is called as indicator(characteristic function)A is called as support of f(A)=(b1,·,b小
Porpostion2: For sets X,Y.|X| = n, Y = [r]. Let XY := {all functions f : Y → X}.Then |XY | = n r . proof: Let B={all vectors of length r over X}. define a function g : X Y → B. f 7→ (f(1), · · · , f(r)) g is a injection since f 6= f 0 ⇒ (f(1), · · · , f(r)) 6= (f 0 (1), · · · , f0 (r)). g is a surjection.since ∀(b1, · · · , br) ∈ B.define f : Y → X, i 7→ bi(i.e.f(i) = bi) That is easy to get g(f) = (b1, · · · , br). ⇒ g is a bijection.⇒ |XY | = |B| = n r . Porpostion3: Let Y = [r], 2 Y :={all subsets of Y }.then |2 Y | = 2r proof: Let B ={all vectors of length r over {0,1}}. define function f : 2Y → B, A → f(A) = (b1, · · · , br) where bi = 0, if i /∈ A; 1, if i ∈ A. claim:f is a injection. ∀A 6= A0 ,⇒ ∃i ∈ [r] s.t.i ∈ A, i /∈ A0 or i /∈ A, i ∈ A0 . ⇒ f(A) 6= f(A0 ). claim:f is a surjection. ∀(b1, · · · , br) ∈ B define A = {i|bi = 1} ⇒ f(A) = (b1, · · · , br) ⇒ f is a bijection.⇒ |Y | = |B| = 2r . [f is called as indicator(characteristic function) A is called as support of f(A) = (b1, · · · , br)]. 3
Binomial Coefficient: ·(（）份-fk-ofn ·ax=n(因）=k-bodts of(-() ·nl=n(n-1)…21. (n),=n(n-1)…(m-r-1) 0!=1. (Θ-1 (份=0>n Porpoaitiond(份)=a点o proof:Let B =fall vectors of length k over [n]consisting k dif- ferent elements.} (Double Counting) Way1:just directly count the number of vectors. Way2-Thre are(（)份）ysoe-fore-abat ,there are k!ways to order it to a vector. →B=(N →（份）=
Binomial Coefficient: • n k := #k−elements subsets of an n elements set. • a|X| = n, X k :={all k−subsets of X}. X k = n k . • n! = n(n − 1)· · · 2 · 1. (n)r := n(n − 1)· · ·(n − r − 1). 0! = 1. n 0 = 1. n k = 0 if k > n. Porposition4: n k = n! k!(n−k)! . proof: Let B ={all vectors of length k over [n] consisting k different elements.} (Double Counting) Way1:just directly count the number of vectors.|B| = n! k!(n−k)! . Way2:There are n k ways to choode k−subset of X.For each k−subset ,there are k! ways to order it to a vector. ⇒ |B| = n k k! ⇒ n k = n! k!(n−k)! . 4
Porposition5: @(因-(” ()(PTne)(图-(（么-）+(（：） proof: (1)trivial.(Hint:you can construct a bijection.) ·#料ak--(-）】 ·并ak-asog小-(（片)】 Combinating the two situations.then we prove(2)
Porposition5: (1) n k = n n − k . (2) (Pascal Triangle) n k = n − 1 k − 1 + n − 1 k . proof: (1) trivial.(Hint: you can construct a bijection.) (2) Separating X k into two parts. and find a fixed element t ∈ X. • #{all k−subsets containing t}= n − 1 k − 1 . • #{all k−subsets avoiding t}= n − 1 k . Combinating the two situations.then we prove (2). 5
2017.9.15 Slections with repetition Porposition6:#{integer solutions to +...+n=k.where >0=(n-i /k-1 proof:The question is equivalent to How many ways of distribut- ing sweets to n children.Such that each child has at least one sweet. Lay out the sweets in a single row of length k,cut it into n pieces.then given yhe sweets in the ith piece to child i.So we need n-1 cuts from k-1 possibles. -(-) integer solutions tok.where n-1 罗中太-+轻5奇之 A…6w头=+ie时 (1)fis weiidefined..if(c1,…,tn)∈A then(h,…,n)∈B. (2)injection. (3)surjection. →4==(+-1 n-1/ Porposition7:X=[n],A={{a a}X,1≤a1≤2≤ ≤n,anda+1-a:≥k+l,i∈r-1 6
2017.9.15 Slections with repetition Porposition6: # {integer solutions to x1 + · · · + xn = k. where xi > 0}= k − 1 n − 1 . proof: The question is equivalent to How many ways of distributing k sweets to n children.Such that each child has at least one sweet. Lay out the sweets in a single row of length k,cut it into n pieces.then given yhe sweets in the ith piece to child i.So we need n − 1 cuts from k − 1 possibles. ⇒ k − 1 n − 1 . # {integer solutions to x1+· · ·+xn = k. where xi ≥ 0}= n + k − 1 n − 1 . proof:LetA={integer solutions x1 + · · · + xn = k, xi ≥ 0} B ={integer solutions y1 + · · · + yn = n + k, yi > 0} Define f : A → B,(x1, · · · , xn) 7→ (y1, · · · , yn) by yi = xi+1, i ∈ [n]. Show:f is a bijection. (1) f is weiidefined.if (x1, · · · , xn) ∈ A then (y1, · · · , yn) ∈ B. (2) injection. (3) surjection. ⇒ |A| = |B| = n + k − 1 n − 1 Porposition7: X = [n], A = {{a1, · · · , ar} ⊆ X, 1 ≤ a1 ≤ a2 ≤ · · · ≤ ar ≤ n, and ai+1 − ai ≥ k + 1, i ∈ [r − 1]}. 6
roof:Let B={integers set b+...+br+=n -1,where bi 2 0,≥k+1,i=2…,6+1≥0 f:A→B,(a1,…,ar)→(b1,…,br+1 By b1=a1-1≥0. b=a-a-1≥k+1,i=2,…,n 0r+1=n-a 0. Easy to check f is a bijection.And construct a function. g:B→C C={integers set c+...+c+1=n-1-(k+1)(r-1),where ci,....cr+1> 0,} andG=b,C=6-(k+1),i=2,·,r,Gr+1=br+1 Also,check g is a bijection.Hence, 4=1g=1C=（0-1-k+r)+r+)-=(（--)口 8.t.a nti omial Theorem) (1+2+…+xn)厂= +oa-alal…20.zn0 proof: (m1+x2+…+xn)y= the coefficient of n is equal to the number of vectors (veroecrtmsbproposition,weget th theorem
proof: Let B ={integers set b1 + · · · + br+1 = n − 1, where b1 ≥ 0, bi ≥ k + 1, i = 2, · · · , r, br+1 ≥ 0.} f : A → B,(a1, · · · , ar) 7→ (b1, , · · · , br+1) By b1 = a1 − 1 ≥ 0. bi = ai − ai−1 ≥ k + 1, i = 2, · · · , r. br+1 = n − ar ≥ 0. Easy to check f is a bijection.And construct a function. g : B → C C ={integers set c1+· · ·+cr+1 = n−1−(k+1)(r−1), where c1, · · · , cr+1 ≥ 0,} and c1 = b1, ci = bi − (k + 1), i = 2, · · · , r, cr+1 = br+1. Also,check g is a bijection.Hence, |A| = |B| = |C| = n − 1 − (k + 1)(r − 1) + (r + 1) − 1 r = n − k(r − 1) r . Arrangements with Repetition Propostion8:X = {x1, · · · , xn}.B ={all vectors of length r over X s.t.xi occurs ai times.} Then,|B| = r! a1!a2!···an! . proof:just double counting. Corollary:(Polynomial Theorem) (x1 + x2 + · · · + xn) r = X a1+a2+···+an=r r! a1!a2! · · · an! x1 a1 · · · xn an . proof: (x1 + x2 + · · · + xn) r = X 1≤i1,i2,··· ,ir≤n xi1 xi2 · · · xir the coefficient of x1 a1 · · · xn an is equal to the number of vectors (i1, · · · , in) over [n],s.t.i occur ai times.by proposition8,we get this theorem. 7
Remark: 0fn=2=a-6ma+r-2()w (2)if z1=2=...=In 1 then n" Propostion9:X=r,A =fordered partitions of X into n parts s.t.ith block has size a)Then proof:Let =i,..Let B=fall vectors of length r over 回crtimes,.ie网，ia,=rd definef:A→B,(h,…,Rn)→(b1,…,br).[bybh=jifi∈Rl check that is a bijection.then l Propostion9:Exercise]X=r,S ={unordered partitions of X,s.t.there arek blocks of size i,ier).Then, 1S=(2刚州kkk Stirling Number of 2nd kind. Def:Let S(r,n)be the number of partitions of [r]into n unordered non-empty sets. S(r,n)= n(1)(2）…(2…k [ExereiselS(,r.2=2（(月 Binomial Theorem n≥0，for all x and y. e+r-( k=0 8
Remark: (1) if n = 2, x1 = a, x2 = b, then (a + b) r = Pr i=0 r i a i b r−i . (2) if x1 = x2 = · · · = xn = 1 then n r = P a1+a2+···+an=r r! a1!a2!···an! . Partition:X = R1 ∪ R2 ∪ · · · ∪ Rn. there are two cases: unordered partition {R1, · · · , Rn},and ordered partition (R1, · · · , Rn). Propostion9:|X| = r, A ={ordered partitions of X into n parts s.t. ith block has size ai}. Then |A| = r! a1!a2!···an! . proof:Let X = x1, · · · , xn. Let B={all vectors of length r over [n] s.t.i occurs ai times. i ∈ [n], Pn i=1 iai = r.} define f : A → B,(R1, · · · , Rn) 7→ (b1, , · · · , br). [by bi = j if i ∈ Rj ] check that f is a bijection.then |A| = |B| = r! a1!a2!···an! . Propostion9:[Exercise] |X| = r, S ={unordered partitions of X, s.t. there are ki blocks of size i, i ∈ [r], Pr i=1 iki = r}.Then, |S| = r! (1!)k1 (2!)k2 · · ·(r!)kr k1!k2! · · · kr! . Stirling Number of 2nd kind. Def:Let S(r, n) be the number of partitions of [r] into n unordered non-empty sets. S(r, n) = X Pr i=1 P ki=n r i=1 iki=r r! (1!)k1 (2!)k2 · · ·(r!)kr k1!k2! · · · kr! . [Exercise]S(r, 2) = 1 2 rP−1 i=1 r i . Binomial Theorem n ≥ 0, for all x and y. (x + y) n = Xn k=0 n k x k y n−k . 8
Thm.(Vandermonder's Indentity)Vm,n,r20 (+）=(0()-(O) a(+）-(0) proof: 1) (1+x)m+n=(1+x)m=(1+x)" →(-0)》 compute coefficient offor both side +)-王)）-2() (2) 三(0G)-2(0(m)-王（(m）-(+) [Exercise】 含（因-(） ()）()-(C+） 同()-）-（+0-) ④（图）(）=(a)-m）≥≥m )()-(a）
Thm.(Vandermonder’s Indentity) ∀m, n, r ≥ 0 (1) m + n r = Pr i=0 n i m r − i = P i+j=r n i m j . (2) m + n r + m = P i−j=r n i m j . proof: (1) (1 + x) m+n = (1 + x) m = (1 + x) n ⇒ mX +n r=0 m + n r x r = Xn i=0 n i x iXm j=0 m j x j compute coefficient of x r for both side. m + n r = X i+j=r n i m j = Xr i=0 n i m r − i . (2) X i−j=r n i m j = X i−j=r n i m m − j = X i+(m−j)=m+r n i m m − j = m + n r + m . [Exercise] (1) Pn k=0 n k 2 = 2n n . (2) Pn k=0 m k n p + k = n + m p + m . (3) Pm k=1 m k n − 1 k − 1 = n + m − 1 n . (4) n k k m = n m n − m k − m (n ≥ k ≥ m). (5) Pn k=0 n k k m = n m 2 n−m. 9
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/19 Estimating Theorem 1 For Vn≤l,e()≤nl≤en()r Proof:consider "Inrdr, ala-p-m≤厂广mc≤2i-tm →lm(n-1)！≤nlnn-n+1≤innl. raise e to the power of each side, (n-l!≤em-n+1≤nl where enlnn-n+1 =(elmn)"e-me=e. ◇ Stirling formula:n!()".wheref(n)gn)meansm1. ()-()a Corllary斋≤(）sr Theorem2:Forl≤k≤n,()≤()≤(0)k Proof:For lower bound,,use the fact是≤g号，i≤k (r≤星岩…Ψ=(
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/19 Estimating Theorem 1 For ∀n ≤ 1, e( n e ) ≤ n! ≤ en( n e ) n . Proof: consider R n 1 lnxdx, ln(n − 1)! = Xn−1 i=1 lni ≤ Z n 1 lnx ≤ Xn i=1 lni = lnn!. =⇒ ln(n − 1)! ≤ nlnn − n + 1 ≤ lnn!. raise e to the power of each side, (n − 1)! ≤ e nlnn−n+1 ≤ n!. where e nlnn−n+1 = (e lnn) n e −n e = n n en e. Stirling formula: n! ∼ √ 2πn( n e ) n . wheref(n) ∼ g(n)means limn→∞ f(n) g(n) = 1. Fact: max{ n k : k = 0, 1, 2 · · · n} = n n 2 , if n is even; n n 2 = n n 2 , if n is odd. Corollary: 2 n n+1 ≤ n n 2 ≤ 2 n . Stirling approximation: n n 2 ∼ 2 n √ n q 2 π . Theorem 2: For1 ≤ k ≤ n,( n k ) k ≤ ( n k ) ≤ ( en k ) k . Proof: For lower bound, use the fact n k ≤ n−i k−1 , ∀i ≤ k, ( n k ) k ≤ n k · n−1 k−1 · · · · · n−k+1 1 = n k , 1